Ask HN: Why is this Racket code so fast?

Doesn't Racket run on Chez Scheme now? I'd read up on that. It's a famously performance-oriented Scheme implementation.

I believe racket/stream uses memoization. So it should be as fast as any memoized fibbonaci function.

    racket make filename.rkt

     racket filename.rkt

racket/stream is lazy, so you only ever generate values when they're directly asked for, and in this case they get discarded almost immediately. This means that the two sequences (fibonacci-sequence and even-fibonacci-sequence) use very little memory at any one point in time. If you switched from a lazy stream approach to a naive approach generating every single Fibonacci number below the threshold and then filtering and then summing, you'd see much worse performance. By using a lazy stream approach you end up with something that should be roughly comparable to this C-ish pseudocode, but still has the appearance of the functional map/filter/reduce style:

  threshold = whatever;
  accum = 0;
  for (a = 0, b = 0; a <= threshold; a, b = b, a + b) { // parallel assignment invalid in C, thus pseudocode
    if (a % 2 == 0) accum += a;
  }
  return accum;

Untested, so assuming no errors in my pseudocode. Note how this only ever has two values of the Fibonacci sequence in memory at any one point in time. The lazy stream version should be equivalent to this since it's only when you actually ask for an element of the even Fibonacci numbers that anything should be generated at all from either sequence.

Also, there is a shortcut to generate only the even Fibonacci numbers. Should reduce your execution time by a bit. Since the even Fibonacci numbers are every 3rd entry, this means you can cut out 2/3rds of the generated values and the conditional checking if a value is even or not.

  (defun new-fib-sequence ()
    (let ((a 0) (b 1))
      (lambda ()
        (shiftf a b (+ a b))))) ;; CL detail, permits parallel assignment and returns the value of the first item *before* assignment

  > (let ((fib (new-fib-sequence))
    (loop repeat 3 do (print (funcall fib))))
  0
  1
  1

  EF(N) = Nth Even Fibonacci Numbers

  EF(N) = 4 * EF(N-1) + EF(N)
  EF(0) = 0, EF(1) = 2

  F(0) = 0
  F(1) = 1
  F(2) = 1 + 0
  F(3) = 1 + 1 = 2 (2 additions to get here)
  F(4) = 2 + 1 = 3
  F(5) = 3 + 2 = 5
  F(6) = 5 + 3 = 8 (3 more additions to get here, and 3 for each subsequent one)

  EF(0) = 0
  EF(1) = 2
  EF(2) = 4 * 2 + 0 = 8 (1 mul, 1 add)
  EF(3) = 4 * 8 + 2 = 34 (1 mul, 1 add)

  lim = 10**1000000
  a, b = 1, 2
  acc = 0
  while a < lim:
      if not a & 1:
          acc += a
      a, b = b, (a + b)
  print("done", flush=True)
  print(acc)

For a baseline this trivial python implementation does it in 34 ms for 10^10000 and 2m55 for 10^1,000,000 on a ryzen 5. Because the fibonacci sequence is increasing roughly exponentially, the iteration count scales roughly linearly to the number of digits. Then it just goes down to the number crunching speed of the bignum implementation? (Calculating the exponent also takes multiple seconds, as well formatting the number to a string takes around 10 seconds as well.)

10^10000 is a large number, but it is surpassed only by the 47,852th Fibonacci number -- a small number of iterations for a computer.

I often suppose as a rule of thumb that a C program can perform ~10 million for-loop additions per second (assuming the accumulator fits in a register). So to do 500,000 bignum additions/second, each bignum addition would only require on average the time of 20 normal additions+iterations.

Also note that the functions provided are all tail recursive. Racket performs tail-call optimizations which would make these similarly performant to a for loop.