PDA

View Full Version : Fun with Fibonacci

Johannes
08-04-2011, 13:25
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
09-04-2011, 07:57
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
09-04-2011, 11:25
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
09-04-2011, 14:18
Dan, have tried making an executable to see if the time is about the same?

jack
09-04-2011, 20:00
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
09-04-2011, 20:42
No time now, guys, later.
:p

danbaron
10-04-2011, 07:05
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".)

: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
11-04-2011, 03:57
that reminds me of the Ackermann function http://en.wikipedia.org/wiki/Ackermann_function :)

danbaron
11-04-2011, 06:30
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
11-04-2011, 07:17
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")

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
11-04-2011, 07:27
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
12-04-2011, 08:02
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.

10^10^6,

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

10^10^9,

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

10^10^12,

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

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
12-04-2011, 09:37
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
12-04-2011, 10:28
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
12-04-2011, 16:29
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