Project: Fibonacci Numbers with Memoization
In the previoius project we could see that computing Fibonacci Numbers with larger values of n can take a long time using recursion. Using a technique called memoization we can cache previously computed values so that we don't have to keep computing them over and over. Create an array to hold the previously computed results. Then when the function is called, look in the list first to see if the answer is there. If not, compute the Fibonacci number and put the result into the list before returning the result.
What is the largest Fibonacci Number that can be computed accurately before overflow occurs? Add a precondition to your function to prevent operation using a value that would produce an incorrect result.
See [[wikipidea or link]]
See Fibonacci1
Output
$ rustc Fibonacci2.rs
error: unknown format trait `d`
--> Fibonacci2.rs:29:31
|
29 | println!("{}", format!("{0:d}: {1:d}", n, fibonacci(n)));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error: unknown format trait `d`
--> Fibonacci2.rs:29:38
|
29 | println!("{}", format!("{0:d}: {1:d}", n, fibonacci(n)));
| ^
|
= note: the only appropriate formatting traits are:
- ``, which uses the `Display` trait
- `?`, which uses the `Debug` trait
- `e`, which uses the `LowerExp` trait
- `E`, which uses the `UpperExp` trait
- `o`, which uses the `Octal` trait
- `p`, which uses the `Pointer` trait
- `b`, which uses the `Binary` trait
- `x`, which uses the `LowerHex` trait
- `X`, which uses the `UpperHex` trait
error[E0308]: mismatched types
--> Fibonacci2.rs:16:9
|
16 | if n < cachedFibonacci.len() {
| - ^^^^^^^^^^^^^^^^^^^^^ expected `isize`, found `usize`
| |
| expected because this is `isize`
|
help: you can convert a `usize` to an `isize` and panic if the converted value doesn't fit
|
16 | if n < cachedFibonacci.len().try_into().unwrap() {
| ++++++++++++++++++++
error[E0277]: the type `[i64]` cannot be indexed by `isize`
--> Fibonacci2.rs:17:26
|
17 | return cachedFibonacci[n];
| ^ slice indices are of type `usize` or ranges of `usize`
|
= help: the trait `SliceIndex<[i64]>` is not implemented for `isize`
= help: the trait `SliceIndex<[T]>` is implemented for `usize`
= note: required for `Vec<i64>` to implement `Index<isize>`
error: aborting due to 4 previous errors
Some errors have detailed explanations: E0277, E0308.
For more information about an error, try `rustc --explain E0277`.
Solution
Pure Programmer
