Generating the nth Fibonacci number

Generating the nth Fibonacci number

The initial program I wrote was based on the Binet formula, (see below), which is considered an exact formula for computing the n-th term of the Fibonacci sequence.  After testing the program, I found that the precision was off around an input of 50.  The datatype used in the program was u128.  I assumed the precision loss was due to two mathematical computations; computing the square root and division.  Unsatisified with the outcome, I decided to do a little more research.

Binet formula
ₓ²   ₋  ₓ  _{−  1 =  0 :  α  =  (1 + √5)  ÷ 2,  β  =  (1 − √5)  ÷ 2}
ϝ_{η = (α^η − β^η) ÷ (α − β)}

I came across an interesting article in Medium on Memoization in Rust written by Andrew Pritchard.  Memoization is an optimization technique which is used to speed up the result of a program by storing the result of a computation for the inputted value and then returning the cached result when the same input occurs again.

Using the Fibonacci example in the article, one issue I ran into, again, was the u128 dataype.  In using the datatype with the memoization approach, I would receive a panic message of 'attempt to add with overflow' when inputting a value greater than 186.  Since I could not figure out how to eloquently handle this error, I hardcoded a fix which I wasn't completely happy with: see here on line 66 .  Another issue I found involved the formatting of the output.  The formatting library used with the u128 datatype was not applicable for the BigUint datatype.  I had an idea how I wanted the program to function and what i wanted the output to look like so I scrapped the application and decided to the write a new program using the BigUint datatype and develope my own function to format the output into what I consider a more appealing form.  The algorithm in the new program is based on the display below with a sample output beneath it.