1. ## Fun with Fibonacci

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.

2. 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
>
```

3. 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.

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

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

6. No time now, guys, later.

There are no members to list at the moment.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•