Per Wikipedia, "In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1".
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 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.
The way the program is now constructed satisfies my previous concerns:
- Allowing the user a wider range of numbers to input. The largest number I successfully inputed was 1.6 million.
- Formatting the Fibonacci Sequence, comma delimited if over 999, and the user input, both comma delimited and ordinal sequence.
The 'formated' function has been implemented on both the u128 and BigUint datatypes. This allows each of the mentioned dataypes to now have the capability to call the formated function on its own value. The source code can be viewed in the src/main folder for those unfamiliar with the Rust language.
Thanks for reading and do reach out and let me know if you have any questions or concerns. Click 'Star' if you like the program. All suggestions, constructive, even non-constructive, will be welcomed.
For those interested in the Fibonacci sequence, here is a full list of the first 10, 100, and 300 Fibonacci numbers.
This project is licensed under the MIT license.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in 'Generate_Nth_Fibonacci' by you, shall be licensed as MIT, without any additional terms or conditions.