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)

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