1001st Fibonacci Number
ANDREWVOSS (188)

This post is a follow-up to my previous post. Basically, it shows off how dynamic programming can be used to calculate absurdly large numbers in a relatively short amount of time. In order to calculate such numbers, I used 1024-bit unsigned integers, provided by the boost library. There are 2 reasons this is impressive (at least to me):

  • The size of the number is much too big to fit in the normal 32-bit or 64-bit integer types (or in any of the 64-bit registers on a normal CPU)
  • Doing this calculation recursively would take exponentially longer (Recursive method takes O(2^n) time, dynamic takes O(n)
You are viewing a single comment. View All
ch1ck3n (2380)

O(2^n) 0x = 0. so it takes so time.

ANDREWVOSS (188)

@ch1ck3n Excuse me, but I don't understand what you're trying to say here.

ch1ck3n (2380)

@ANDREWVOSS i dont understand what O(2^n) means

ANDREWVOSS (188)

@ch1ck3n It's Big O Notation. Basically, it's a way of approximating how long a function will take, where O represents a variety of factors such as CPU speed and cache memory, and n represents the variable (in this case, the argument to the function)