N'th Fibonacci sequence function fails to output result when n > 35

[partylikeits1983]

Describe the bug When running the fib.bend program with an input value larger than 30, the time to generate an output becomes unusably slow.

In contrast, running the same program in Rust produces a near-instant output. This might be due to the fib.bend program not being parallelizable.

fib.bend (very slow):

add = λa λb (+ a b)

fib = λx switch x {
  0: 1
  _: let p = x-1; switch p {
    0: 1
    _: (+ (fib p) (fib p-1))
  }
}

main = (fib 30)

fibonacci in rust (near instant)

fn fibonacci(n: u32) -> u64 {
  if n == 0 {
      return 0;
  }
  let mut prev = 0;
  let mut curr = 1;
  for _ in 1..n {
      let next = prev + curr;
      prev = curr;
      curr = next;
  }
  curr
}

fn main() {
  let n = 31;
  let fib_n = fibonacci(n);
  println!("{}", fib_n);
}

To Reproduce

Run fib.bend with a value larger than 30.

Expected behavior Similar output speed to Rust.

Desktop (please complete the following information): OS: macOS CPU: M2 Pro

Additional context Just wondering why it is slow. Does the program need to be compiled into HVM first and then executed to run fast?

[partylikeits1983]

I am running fib.bend with bend run fib.bend and bend run-c fib.bend

[developedby]

Your fibonacci function creates a tree of addition operators of size ~2^n. It fails at large numbers because you run out of memory (maximum of 2^29 nodes at once) and it is slow because your implementation is exponentially slow. Here's a sequential implementation that scales linearly

fib x =
  bend x a=1 b=1 {
     when (!= x 0): (fork (- x 1) b (+ a b))
     else: a
  }

bend run-c fib.bend -s show a runtime 0f 0.00s If you implemented the rust function like you did you bend one it would have the same issue (and it would stack overflow, but that can be fixed)

[partylikeits1983]

Your fibonacci function creates a tree of addition operators of size ~2^n. It fails at large numbers because you run out of memory (maximum of 2^29 nodes at once) and it is slow because your implementation is exponentially slow. Here's a sequential implementation that scales linearly

fib x =
  bend x a=1 b=1 {
     when (!= x 0): (fork (- x 1) b (+ a b))
     else: a
  }

bend run-c fib.bend -s show a runtime 0f 0.00s If you implemented the rust function like you did you bend one it would have the same issue (and it would stack overflow, but that can be fixed)

Thank you, this implementation is super fast. I opened a PR with your implementation.

[raybellwaves]

Sorry for the stupid question here. How would I modify the code below to return 0 if fib(0)?

fib x =
  bend x a=1 b=1 {
     when (!= x 0): (fork (- x 1) b (+ a b))
     else: a
  }

[developedby]

start with a=0

[developedby]

Your fibonacci function creates a tree of addition operators of size ~2^n. It fails at large numbers because you run out of memory (maximum of 2^29 nodes at once) and it is slow because your implementation is exponentially slow. Here's a sequential implementation that scales linearly

fib x =
  bend x a=1 b=1 {
     when (!= x 0): (fork (- x 1) b (+ a b))
     else: a
  }

bend run-c fib.bend -s show a runtime 0f 0.00s If you implemented the rust function like you did you bend one it would have the same issue (and it would stack overflow, but that can be fixed)

Thank you, this implementation is super fast. I opened a PR with your implementation.

I'll update the example later to explain the difference between the two