Fun with Fibonacci

[danbaron]

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

http://www.thinbasic.com/community/s...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.]

[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."

[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