Share your repls and programming experiences

← Back to all posts
##### 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)`
##### Comments
hotnewtop
ch1ck3n (2035)

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

ANDREWVOSS (187)

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

ch1ck3n (2035)

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

ANDREWVOSS (187)

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