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.

:idea: :?:


; 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.
:p

[danbaron]

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

:shock01:


; 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
>

[jack]

that reminds me of the Ackermann function http://en.wikipedia.org/wiki/Ackermann_function :)

[danbaron]

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
>

[danbaron]

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.

[danbaron]

We went through the Ackermann function before, here, Johan.

http://www.thinbasic.com/community/search.php?searchid=60624

Maybe it's time to go back to it again, and at least calculate, A(4, 2).

[A(4, 3) = 2^2^65536 - 3.

From within the REPL in DrRacket (using unlimited memory), I tried to execute,

(define a (- (expt 2 (expt 2 65536)) 3)),

and, DrRacket crashed.]

:oops:

[danbaron]

Now I know why DrRacket crashed when I tried to evaluate the value of A(4, 3), i.e., 2^2^65536 - 3.

(I think it's easy to become confused about how big a number is, when it is written as an exponent raised to an exponent.)

In the same article,

http://en.wikipedia.org/wiki/Ackermann_function ,

it says that A(4, 3) is approximately equal to,

10^(6.031 * 10^19727).

So, how big is that number?

Let's forget about the factor, 6.031. It doesn't matter, since as we will see, even without it, the number is effectively infinite.

So instead, just consider the number,

10^10^19727.

Let's approach it like this.

If we had the number,

10^10^6,

then, that number would have one million and one (1,000,001) (decimal) digits.

If we had the number,

10^10^9,

then, that number would have one billion and one (1,000,000,001) digits.

If we had the number,

10^10^12,

then, that number would have one trillion and one (1,000,000,000,001) digits.

If we had the number,

10^10^303,

then, that number would have one centillion and one (10^303 + 1) digits. "cent", is the largest number prefix I can find, -->

http://en.wikipedia.org/wiki/Names_of_large_numbers .

And, from the same article, the largest named number is, "Googolplex". But it is only equal to,

10^10^100.

Anyway,

10^10^19727,

would have, 10^19727 + 1, digits.

I think, we have no way to imagine how many digits that is, because, there is nothing to compare it to.

In fact, if I am not mistaken, then,

10^10^19727 = 10^10^19627 * Googolplex.

I would be surprised if any computer can ever calculate, A(4, 3).

Interestingly, in the Ackermann article, it also says,

"A(4, 2), which appears as a decimal expansion in several web pages, cannot possibly be computed by simple recursive application of the Ackermann function in any tractable amount of time."

:cry:

[danbaron]

I did the calculation in Racket for A(4, 1). It took approximately 48 minutes.

If I tried A(4, 2), I would have to wait forever (if I didn't overflow the stack).

:!:

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

#lang scheme

(define (a m n)
(cond
((= m 0) (+ n 1))
((and (> m 0) (= n 0)) (a (- m 1) 1))
((and (> m 0) (> n 0)) (a (- m 1) (a m (- n 1))))))


(define (ack-time f x y)
(let ([t1 (current-milliseconds)])
(f x y)
(let ([t2 (current-milliseconds)])
(/ (- t2 t1) 1000.0))))

; REPL interaction -------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: scheme.
> (ack-time a 4 1)
2862.129
>

[Johannes]

In fact, if I am not mistaken, then,

10^10^19727 = 10^10^19627 * Googolplex.

Absolutely correct. A googol, defined as 10^100, is already an astounding number. The estimated number of atoms in the universe is 10^80. The factor between the two is not 20, as many non-mathematically-inclined people think, but 10^20: 100,000,000,000,000,000,000. A googolplex is the number one followed by 10^100 zeroes.

And even that number is dwarfed by A(4,3). Actually, "dwarfed" is the wrong word because that word indicates a certain size relation. A difference in magnitude of 10^10^19627 is incomprehensible.

For interest, extended-precision floating-point values (Ext) have a maximum magnitude of 10^4932. Even that number is basically meaningless.

[Johannes]

While testing the fixed-point stuff I saw that F(65) has '65' as its last two digits. And of course F(0)=0 and F(1)=1.


Uses "Console"
Module "BigInt"
Alias String As BigInt
BigInt a
String b,c
BigInt_SetFormat(0,".",FALSE)
a=BigInt_FromInteger(0)
Do
b=BigInt_ToString(BigInt_Fib(a))
c=BigInt_ToString(a)
If RIGHT$(b,Len(c))=c Then Print c+$SPC
a=BigInt_Inc(a)
Loop