Page 2 of 2 FirstFirst 12
Results 11 to 15 of 15

Thread: Fun with Fibonacci

  1. #11
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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.]



    Last edited by danbaron; 11-04-2011 at 08:05.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  2. #12
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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."



    Last edited by danbaron; 12-04-2011 at 09:23.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  3. #13
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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
    >
    

    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  4. #14
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25
    Quote Originally Posted by danbaron View Post
    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.
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

  5. #15
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25

    Funny Fibonacci numbers

    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
    
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Fibonacci sequence
    By macleay in forum Shout Box Area
    Replies: 1
    Last Post: 22-08-2011, 15:39
  2. Fibonacci by Oxygen
    By ErosOlmi in forum O2 JIT Compiler / Assembler / Oxygen project
    Replies: 13
    Last Post: 18-11-2010, 14:25

Members who have read this thread: 0

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
  •