# Thread: Fun with Fibonacci

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.  Reply With Quote

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
>
```  Reply With Quote

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.   Reply With Quote

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

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)))))))
```  Reply With Quote

6. No time now, guys, later.   Reply With Quote

7. ## n^n

I had an idea I wanted to try as soon as I got home, before I looked at anything else.

So, I worked on this.

Basically, I wanted to see if I could get Racket to do a calculation that would produce a 5 million digit number.

Why, 5 million?

If you assume that each line on a page can display 100 digits, and a page has 50 lines, then, 5 million digits corresponds to 1000 pages.

So, I wanted to see if Racket could calculate a number that would be 1000 pages long.

By default, DrRacket uses 128 MB. I found in the "Racket" menu, how to change the memory to be unlimited, and, I did that.

I decided to use as my function, n^n.

The number of digits in n^n, is, --> ceiling(n * log10(n)).

In order to get 5 million digits, I figured out that I needed n to be approximately, 844,000.

So, I used 844,123, --> so that Racket would not have a lot of zero multiplications.

For, 844,123, ceiling(n * log10(n)) = 5,002,616.

Below, is the code, and the REPL interactions.

It took Racket less than 22 seconds on my mediocre computer, to do the calculation of the number.

Interestingly, it took Racket longer than 22 seconds to do the calculation of the number of digits in the number.

(I played around with using n^n^n, instead of n^n, but, that function grows too fast. I can't imagine what n^n^n^n would do. Probably, for n = 3, my computer would explode!)

(I guess, at least in this case, it doesn't matter if you use, "#lang scheme", or, "#lang racket".)

(Now that I've, "scratched this itch", I can return to Fibonacci.) ```; code -----------------------------------------------------------------------

#lang scheme

(define big-n^n 0)

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

(define (n^n n) (expt n n))

(define (num-digits n)
(let* ([n-string (number->string n)]
[n-list (string->list n-string)]
[n-digits (length n-list)])
n-digits))

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

Welcome to DrRacket, version 5.1 [3m].
Language: scheme.
> (n^n-time 844123)
21.527
> (num-digits big-n^n)
5002616
>
```  Reply With Quote

8. that reminds me of the Ackermann function http://en.wikipedia.org/wiki/Ackermann_function   Reply With Quote

9. I verified that you are absolutely correct about fib3n, Johan.
I got more than a 6 times speed increase.

```; code ----------------------------------------------------------------

#lang scheme
(define big-fib 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))

(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)))))))

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

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

Welcome to DrRacket, version 5.1 [3m].
Language: scheme.
> (fib-time fib 1000000)
272.155
> (fib-time fib3n 1000000)
42.503
>
```  Reply With Quote

10. You asked about running an executable, Johan.
I made an executable from the following file.
It ran in a console window.

```#lang scheme
(define big-fib 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))

(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)))))))

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

(print (fib-time fib 1000000))
(printf "\n")
(print (fib-time fib3n 1000000))
(printf "\n")
(read-line)
```

The times were,

203.772 and 25.764.

While from within DrRacket, they were, 272.155, and 42.503.

So, there is somewhat of a speed increase.

The downside for executables is that, just to print, "hello", the file size is 4699 KB - at least it is for me.  Reply With Quote

Page 1 of 2 12 Last #### Posting Permissions

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