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

Questions / Help
,
1

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
2

:wave:

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
3

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
4

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)
5

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.

6
4 Likes
7

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
8

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
9

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 (!)

10

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