The highest Fibonacci number ever calculated

This is a discussion on The highest Fibonacci number ever calculated within the C Programming forums, part of the General Programming Boards category; Does anyone know of the highest fibonacci number calculated? How quickly it was done? I tried google but couldn't find ...

  1. #1
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045

    Post The highest Fibonacci number ever calculated

    Does anyone know of the highest fibonacci number calculated? How quickly it was done? I tried google but couldn't find anything.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    There's not much use to calculating high Fibonacci numbers, and unlike prime numbers, where calculating a high one takes a lot of luck and is a one-time affair, once you calculate the nth and (n+1)th Fibonacci numbers, you can very easily calculate the (n+2)th Fibonacci number. As soon as a high was published, it would be out of date.

    Here's the first five digits of the 100000th Fibonacci number, which is 20899 digits long: 25974
    Last edited by Rashakil Fol; 07-23-2005 at 01:25 PM.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    No, because they could only publish one number, without the previous number, and therefore you couldn't calculate any higher with one number.

    [edit]
    How did you know that about the 100,000th number?
    [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    I calculated it with this Ruby program:
    Code:
    low = 0
    high = 1
    n = ARGV[0].to_i
    while (n -= 1) != 0
      high += low
      low = high - low
    end
    
    puts high
    And you could still calculate the next Fibonacci number -- when n gets large, fib(n) is approximately equal to (1 + sqrt(5)) / 2 * fib(n - 1) (close enough that rounding to the nearest integer works).
    Last edited by Rashakil Fol; 07-23-2005 at 07:22 PM.

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    I calculated the 200,000th Fibonacci number in half an hour with my C program.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Why would it take half an hour? That's a very long amount of time. It took about 10 seconds here (and Ruby should be (read: "is") slower than C).

  7. #7
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Perhaps he wrote his own number library -- which probably (read: "surely") would be slower than Ruby's.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  8. #8
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Hmmm.... that's a decent (read: "good") point.

  9. #9
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    Yeah 30 minutes is very slow for fib(200000) it took less than a minute to calculate the 200,000th one in my relatively slow scheme interpreter.

    I just translated Rashakil's ruby.
    Code:
    (define fib (lambda (n) 
      (let loop ((i 1) (low 0) (high 1))
        (if (= i n) high
            (loop (+ i 1) high (+ high low))))))

  10. #10
    I like code Rouss's Avatar
    Join Date
    Apr 2004
    Posts
    131
    Quote Originally Posted by Rashakil Fol
    Why would it take half an hour? That's a very long amount of time. It took about 10 seconds here (and Ruby should be (read: "is") slower than C).
    Maybe recursion was involved, but I still don't think it should be that slow.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    42
    I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.
    Code:
    (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))
    This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).

    The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.

  12. #12
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    Quote Originally Posted by the pooper
    I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.
    Code:
    (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))
    This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).

    The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.
    woah

  13. #13
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    868
    Quote Originally Posted by the pooper
    Code:
    (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))
    I couldn't get this formula to produce correct values, but see below.

    Quote Originally Posted by the pooper
    The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.
    And that really does slow things down, because you need more and more precision, the bigger the numbers.

    For example, fib(200000) takes 1.7 seconds on my machine, but fib(1000000) takes 40 seconds. I used the following python code taken from Wikipedia's Fibonacci programs entry:
    Code:
    def mul(A, B):
        a, b, c = A
        d, e, f = B
        return a*d + b*e, a*e + b*f, b*e + c*f
    
    def pow(A, n):
        if n == 1:     return A
        if n & 1 == 0: return pow(mul(A, A), n/2)
        else:          return mul(A, pow(mul(A, A), (n-1)/2))
    
    def fib(n):
        if n < 2: return n
        return pow((1,1,0), n-1)[0]
    
    print fib(1000000)

  14. #14
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by the pooper
    I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.
    Code:
    (pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))
    This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).
    Not true! pow is not an O(1) operation! Not on integers. With doubles, pow uses logarithms, but as N increases, you need linearly increasing amounts of precision to your numbers. This means that using pow (well, some longfloat-capable version of it) would still take at least linear time.

    Quote Originally Posted by the pooper
    The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.
    Exactly.

    One interesting solution would be to use a special datatype which stores irrational numbers of the form x + y*sqrt(5) (storing just x and y) and using exponents of these numbers in calculating the given Binet's formula.

    This is similar to the Python solution given, which instead uses exponents of the matrix
    Code:
    1 1
    1 0
    which when exponentiated produces results such as
    Code:
    13 8
    8 5

  15. #15
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    When I said half an hour, I was speaking relatively. Besides, my computer is 400MHz.

    The number, stored in a text file, is over 50KB (with commas).
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. adding a number to a number
    By bigmac(rexdale) in forum C Programming
    Replies: 11
    Last Post: 10-24-2007, 12:56 PM
  2. scanf oddities
    By robwhit in forum C Programming
    Replies: 5
    Last Post: 09-22-2007, 01:03 AM
  3. Finding a number within a number
    By jeev2005 in forum C Programming
    Replies: 2
    Last Post: 01-10-2006, 07:57 PM
  4. help with a source code..
    By venom424 in forum C++ Programming
    Replies: 8
    Last Post: 05-21-2004, 12:42 PM
  5. parsing a number
    By juancardenas in forum C Programming
    Replies: 1
    Last Post: 02-19-2003, 12:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21