# Math problem. How to code `Xn+1 = Xn + Xn * S`

I’m trying to generate a list of numbers, where each number is a percentage smaller than the previous. Starting with 1. In the end I’ll need 10 (or whatever amount) of items from the end of it.

The math formula I came up with for a single number looks pretty simple:

``````Xn+1 = Xn - Xn * S
S = 0.008
X0 = 1
``````

But the function I came up with is totally bonkers. While this works, it’s big and slow. My intuition says it’s possible to just make a calculation for each number, but I suck at math and don’t even know what to search for.

Ugly 20 lines of Enum.reduce
``````  @doc """
Make a grid of prices around initial price.

iex> price_grid("0.123", "0.001", 2, "0.001")
[
%{price: D.new("0.125"), side: "ask"},
%{price: D.new("0.124"), side: "ask"},
%{price: D.new("0.122"), side: "bid"},
%{price: D.new("0.121"), side: "bid"}
]
"""
def price_grid(price, spread, levels, tick_size) do
starting_point = "1"
levels_total = levels * 2 + 1
min_mid_price = D.div(spread, "2") |> D.mult(price) |> then(&D.sub(price, &1))
max_iterations = 100_000

Enum.reduce_while(0..max_iterations, {starting_point, []}, fn i, {curr_price, grid} ->
new_price = D.sub(curr_price, D.mult(curr_price, spread))
grid = Enum.take(grid ++ [new_price], -levels_total)
mid_price = Enum.slice(grid, levels, 1) |> List.first()

if i == max_iterations or (not is_nil(mid_price) and D.lt?(mid_price, min_mid_price)) do
IO.inspect(i, label: "HALT")
grid = Enum.map(grid, &round_tick(&1, tick_size))
{:halt, grid}
else
{:cont, {new_price, grid}}
end
end)
end
``````
1 Like Not sure if that’s what you are looking for, but I think the formula for `x_n` is `x_n = x_0 * (1 - S)^n`:

``````x_1 = (1 - S) * x_0
x_2 = (1 - S) * x_1 = (1 - S) * (1 - S) * x_0
x_3 = (1 - S) * x_2 = (1 - S) * (1 - S) * x_1 =  (1 - S) * (1 - S) * (1 - S) * x_0
...etc
``````

And ignoring math, generating the numbers could be done like this:

``````defmodule Series do
def generate(x, s, count) when count > 0, do: [x | generate(x * s, s, count - 1)]
def generate(_, _, _), do: []
end

Series.generate(10, 0.5, 10)
# [10, 5.0, 2.5, 1.25, 0.625, 0.3125, 0.15625, 0.078125, 0.0390625, 0.01953125]
``````

Again, not sure if this is indeed what you need. I don’t quite understand the code in your snippet …

1 Like

Hey @KristerV .
You can use Stream.iterate/2 here.

``````iex> x0 = 1.0
iex> s = 0.008
iex> stream = Stream.iterate(x0, &Float.round(&1 * (1 - s), 3))
iex> Enum.take(stream, 3)
[1.0, 0.992, 0.984]
``````
1 Like

This would certainly benefit from a better explanation of your goal(s) with this.

Though the code you did post can (for the most part) be written with higher level primitives.

``````min_mid_price = Decimal.div("0.001", "2") |> Decimal.mult("0.123") |> then(&Decimal.sub("0.123", &1))
levels_total = 2 * 2 + 1
mid = div(levels_total, 2)

Decimal.new("1")
|> Stream.iterate(&Decimal.sub(&1, Decimal.mult(&1, "0.001")))
|> Stream.take(100_000)
|> Stream.chunk_every(levels_total, 1)
|> Enum.find(fn list ->
list |> Enum.at(mid) |> Decimal.lt?(min_mid_price)
end)
``````

awesome @ruslandoga that’s it! does it have a name? very useful.

@freevova and @LostKobrakai the Stream.iterate i wasn’t aware of, will provide useful for sure.

4 Likes

Hello ! I tried the solution

``````defmodule Series do
def generate(x, s, count) when count > 0, do: [x | generate(x * s, s, count - 1)]
def generate(_, _, _), do: []
end
``````

and was expecting to blow the stack since it isn’t tail optimized when run with a big count (like 100000); however it worked fine! Can anybody explain to me why it works ? How it’s even possible?

i.e this works fine:

``````defmodule Series do
def generate(x, s, count) when count > 0, do: [x | generate(x * s, s, count - 1)]
def generate(_, _, _), do: []
end

for s <- Series.generate(101111111111, 0.999, 110000)  do
IO.puts(s)
end
``````

There’s some discussion about this in the Erlang Efficiency Guide; short short version tail recursion isn’t necessarily faster or more memory-efficient.

1 Like

Yes but since this is not a tail-recursive function should it blow the stack ? Is the erlang stack unlimited ? I tried it with really big numbers and I have a memory consumption of like 4 GB for that program but it seems to be working without breaking (!)

The BEAM doesn’t pass everything via the stack, it has registers as well. The BEAM book has a good introduction to the situation.

You can go down this rabbithole further with compiler options - add `@compile :S` inside the `Series` module definition and then run `elixirc` on the file. You’ll get an error message:

``````== Compilation error in file foo2.ex ==
** (CompileError) foo2.ex: could not compile module Series. We expected the compiler to return a .beam binary but got something else. This usually happens because ERL_COMPILER_OPTIONS or @compile was set to change the compilation outcome in a way that is incompatible with Elixir
``````

but you’ll ALSO get a file with `.S` on the end of the name with a BEAM assembly dump in it!

Here’s what `Series.generate` compiled to with Elixir 1.13 / OTP 24:

``````{function, generate, 3, 12}.
{label,11}.
{line,[{location,"foo2.ex",4}]}.
{func_info,{atom,'Elixir.Series'},{atom,generate},3}.
{label,12}.
{test,is_lt,{f,13},[{integer,0},{x,2}]}.
{gc_bif,'*',{f,0},3,[{x,0},{x,1}],{x,3}}.
{gc_bif,'-',{f,0},4,[{x,2},{integer,1}],{x,2}}.
{allocate,1,4}.
{move,{x,0},{y,0}}.
{move,{x,3},{x,0}}.
{call,3,{f,12}}.
{'%',{var_info,{x,0},[{type,{t_list,number,nil}}]}}.
{test_heap,2,1}.
{put_list,{y,0},{x,0},{x,0}}.
{deallocate,1}.
return.
{label,13}.
{move,nil,{x,0}}.
return.
``````

`{label, 12}` is the main entry point.

It checks the `when` clause on the third argument (arguments are passed in `x` registers starting with `{x, 0}`) and bails out to label 13 for the base case: put `[]` (Erlang spells it `nil`) into register `{x, 0}` (the register used for the return value) and return.

The next two instructions do the actual computation, putting `x * s` into register `{x,3}` and `count - 1` into `{x,2}`. Note that the compiler has determined that the original value of `count` that was passed in via `{x,2}` is no longer “live” (visible to code) so it can reuse the register to store `count - 1`.

`allocate` creates space on the stack for the return address and one saved register - the stack is read via the `y` registers, again starting with `{y,0}`.

The next two instructions shuffle registers around: `{x,0}` is saved in `{y,0}` (preserving the original value of `x`) and then `x * s` is copied from `{x,3}` into `{x,0}`.

That lines everything up for a new call to `generate`: the three needed arguments are in `{x,0}` through `{x,2}` (`s` is unchanged from one iteration to the next).

`test_heap2` verifies there’s enough space on the heap for the new cons cell we’re about to construct (and triggers GC if needed).

`put_list` combines `x` (from `{y,0}`) and the return value from `generate` (in `{x,0}`) into a new cons cell and puts a pointer to it into `{x,0}`

`deallocate` cleans up the two stack slots, and then `generate` returns.

Every time `generate` recurses, it grows the stack by two slots (the return address and `{y,0}`).

Every time it returns from a recursion, it shrinks the stack by two slots and creates a cons cell which takes two slots on the heap.

Overall, the body-recursive function allocates a maximum of `2 * count + 2` slots - first all from the stack until the recursion hits bottom, and then trading stack for heap until completion.

What about the tail-recursive version?

This is a fairly standard body → tail recursion conversion:

``````  def generate2(x, s, count), do: do_generate2(x, s, count, [])

defp do_generate2(_, _, 0, acc), do: Enum.reverse(acc)
defp do_generate2(x, s, count, acc) do
do_generate2(x * s, s, count - 1, [x | acc])
end
``````

and the assembly shows the tail-recursion we wanted to see:

``````{function, generate2, 3, 15}.
{label,14}.
{line,[{location,"foo2.ex",7}]}.
{func_info,{atom,'Elixir.Series'},{atom,generate2},3}.
{label,15}.
{move,nil,{x,3}}.
{call_only,4,{f,9}}.

{function, do_generate2, 4, 9}.
{label,8}.
{line,[{location,"foo2.ex",9}]}.
{func_info,{atom,'Elixir.Series'},{atom,do_generate2},4}.
{label,9}.
{'%',{var_info,{x,3},[{type,{t_list,number,nil}}]}}.
{test,is_eq_exact,{f,10},[{x,2},{integer,0}]}.
{move,{x,3},{x,0}}.
{call_ext_only,1,{extfunc,'Elixir.Enum',reverse,1}}.
{label,10}.
{line,[{location,"foo2.ex",11}]}.
{gc_bif,'*',{f,0},4,[{x,0},{x,1}],{x,4}}.
{gc_bif,'-',{f,0},5,[{x,2},{integer,1}],{x,2}}.
{test_heap,2,5}.
{put_list,{x,0},{x,3},{x,3}}.
{move,{x,4},{x,0}}.
{call_only,4,{f,9}}.
``````

`call_only` is the indication that the compiler has successfully detected tail-recursion.

Some other important differences:

• no `allocate` instructions at all, so no stack usage
• same amount of heap space checked for as in the body-recursive version (2 slots)

No stack usage, that’s good, right? There’s a tradeoff: in principle, constructing the reversed list at the end doesn’t need to take `2 * count` memory (all that “reverse a linked list in-place” drilling is actually useful for once!) but it does take time.

4 Likes