Calculating big fibonacci numbers real fast

1

I browsed old threads and found this. Choosing better algorithm for calculating Fibonacci numbers can make a lot bigger difference than choosing better optimizing compiler.

Here is an example using 8th programming language that calculates Fibonacci(4784969) using fast doubling with result of million digits. Luckily 8th can calculate using big numbers with ease…

\
\ Fibonacci with million digits
\
: bits?  \ n -- nbits-1
  n:ln 2 n:ln n:/ n:int ;

: fibo-loop
  -rot  2dup 2 n:*
  over n:- n:* -rot
  n:sqr swap n:sqr n:+
  rot r@ swap n:shr 1 n:band if
    dup rot n:+
  then ;

: fibo  \  n -- fibo(n)
  >r F0 F1
  ' fibo-loop 1 r@ bits? loop-
  r> 1 n:band if
    n:sqr swap n:sqr n:+
  else
    2 n:* over n:- n:*
  then ;

: app:main  
  1m n#
  d:msec
  4784969 fibo
  d:msec rot  n:- swap
  "%.f" strfmt
  s:len "digits: %d\n" s:strfmt .
  dup 40 s:lsub "%s first 40 digits.\n" s:strfmt . 
  40 s:rsub "%s last 40 digits.\n" s:strfmt .
  "Took: %d msecs\n" s:strfmt . ;

What about speed? It’s not bad:

C:\temp>8th fibo.8th
digits: 1000000
1072739564180047722936481359622500432190 first 40 digits.
3407167474856539211500699706378405156269 last 40 digits.
Took: 107 msecs
2

without any comparison your speedtest is quite unuseable.
What about a cough XOJO cough counterpart cough speed cough test?

:slight_smile:

1 Like
3

I’m not sure what Garry was benchmarking though, the Fibonnaci number calculation or just causing a lot of recursion and timing that.

Just take the Python algorithm for example:

import time

# Garry's implementation
def fib(n):
  if n < 2: return n
  return fib(n - 1) + fib(n - 2)

# alternative without recursion
def fib_alt(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def run_fib(n, v=0):
    start = time.time()
    if v == 0:
        r = fib(n)
    else:
        r = fib_alt(n)
    end = time.time()
    print(r)
    elapsed = end - start
    print(f'{elapsed:.20f}\n')    

print("Garry's")
run_fib(35)
print("Alternative")
run_fib(35, 1)

fib_result

4

Iterative version is not always faster than recursive as fibonacci calculation can be written to be tail recursive and most compilers then optimize simply by replacing a call with jump.

5

I was benchmarking deep recursion.

The point of that rant was comparing the same inefficient methods between different programming languages.

I know very well there are better ways to compute a Fibonacci sequence.