1001st Fibonacci Number

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 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)