Fun with Fibonacci

[Johannes]

If F(n) is the nth number in the Fibonacci sequence and F(0)=0, F(1)=1 and F(n)=F(n-2)+F(n-1) then...

If n is a multiple of 3 then F(n) is even.
If n is a multiple of 15 then the last digit of F(n) is a zero.

F(n) and F(n+60) have the same last digit.
F(n) and F(n+300) have the same last two digits.
F(n) and F(n+1500) have the same last three digits.
F(n) and F(n+15000) have the same last four digits.
F(n) and F(n+150000) have the same last five digits.
F(n) and F(n+1500000) have the same last six digits.

If you allow negative values for n then F(-n)=-F(n) if n is even and F(-n)=F(n) if n is odd.

For large values of n the number of (decimal) digits in F(n) is approximately 0.209 n - 0.35, eg. F(1,000,000,000) has 208,987,640 digits. The exact formula is CEILING(n * log10(PHI) - log10(SQRT(5))) for larger n.

[danbaron]

I made some Fibonacci definitions using Racket (<-- descendant of Scheme <-- dialect of Lisp).
I ran the definitions from within DrRacket (the Racket IDE).
(I think that running the definitions, compiles and loads them.)

Then, I used the definitions from the Racket REPL (read-eval-print loop).

Below, you can see the definitions, and the REPL interactions.

First, I tested, fib, to determine if it functioned correctly.

Next, I timed it for, (fib 100000), 1.739 seconds.

Then, I timed it for, (fib 1000000), 306.756 seconds.

Finally, I calculated the number of digits in, (fib 1000000), 208988.

; code -----------------------------------------------------------------

#lang racket

(define big-fib 0)

(define (fib-time n)
  (let ([t1 (current-milliseconds)])
    (set! big-fib (fib n))
    (let ([t2 (current-milliseconds)])
      (/ (- t2 t1) 1000.0))))

(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

; REPL interactions ----------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket; memory limit: 128 MB.
> (fib 0)
0
> (fib 1)
1
> (fib 2)
1
> (fib 3)
2
> (fib 4)
3
> (fib 5)
5
> (fib 6)
8
> (fib 7)
13
> (fib-time 100000)
1.739
> (fib-time 1000000)
306.756
> (define big-fib-string (number->string big-fib))
> (define big-fib-list (string->list big-fib-string))
> (define big-fib-digits (length big-fib-list))
> big-fib-digits
208988
>

[Johannes]

Dan,

Between fib(100,000) and fib(1,000,000) you have a time factor of 176. When I do the same with BigInt I get a factor of 107. I'm very impressed with Racket since that's an all-purpose language and you wrote the "driving" algorithm in Racket itself, while I did my utmost to optimise big-integer processing and wrote the driving algorithm in PowerBASIC.

BigInt agrees: fib(1,000,000) has 208,988 decimals.

[jack]

Dan, have tried making an executable to see if the time is about the same?

[jack]

Dan, here's fib implementation that uses the indendity fib(3*n)=5*fib(n)^3+3*(-1)^n*fib(n) if n is odd otherwise it uses the indentity fib(3*n+1)=fib(n+1)^3+3*fib(n+1)*fib(n)^2-fib(n)^3, (I embedded your fib function.)
if you substitute fib3n in your benchmark it's about four times faster

(define (fib3n n)
  (define (fib-iter a b count) 
    (if (= count 0) 
        b 
        (fib-iter (+ a b) a (- count 1)))) 
  (if (< n 77)
      (fib-iter 1 0 n)
      (let ([m (quotient n 3)])
        (let ([f (fib-iter 1 0 m)])
          (if (< (* 3 m) n)
              (let ([f1 (fib-iter 1 0 (+ 1 m))])
                (- (+ (* f1 f1 f1) (* 3 f1 f f)) (* f f f)))
              (+ (* 5 f f f) (* 3 (expt -1 m) f)))))))

[danbaron]

No time now, guys, later.