A question about the Fibonacci sequence

code review
1

Hello,
I have two different programs that calculate the Fibonacci sequence.

Code 1:

fn main() {
let mut number1=0;
let mut number2=1;
let mut number3=0;
for i in 2..10 {
    number3=number1+number2;
    println!("{}",number3);
    number1=number2;
    number2=number3;
   }
}

Code 2:

fn main() {
let mut fib = [1; 10];
for i in 2..fib.len() {
    fib[i] = fib[i - 2] + fib[i - 1];
    }
for i in 0..fib.len() {
    print!("{}, ", fib[i]);
    }
}

How can I modify the following code to calculate the Fibonacci sequence without array?

fn main() {
let mut number=0;
for i in 2..10 {
    number = (i-2) + (i-1);
    println!("{}",number);
    }
}

Thank you.

2

Doesn't the first snippet already calculate the sequence without an array?

1 Like
3

This is a math problem rather than a rust programming problem.

If you want to calculate fib(n) without calculate the full array, Here is one of such solution(description is in Chinese, but the code is useable.)

Further discussion could be found if you use google translate and read related answers carefully.

use rug::{Assign, Integer, integer::IntegerExt64};
fn fib(a:Integer)->Integer {
    let mut idx=a.significant_bits_64();
    let [mut coef_1,mut coef_5, mut c15, mut c1155, mut c55]=[Integer::from(2),Integer::from(0),Integer::from(0),Integer::from(0),Integer::from(0)];
    while idx != u64::MAX {
        std::thread::scope(|s|{
            s.spawn(||c55=Into::<Integer>::into(&coef_5*&coef_5)*5);
            s.spawn(||c15=(&coef_1*&coef_5).into());
            s.spawn(||c1155=(&coef_1*&coef_1).into());
        }); // multithreading is not necessary but it could speed up calculation.
        c1155+=&c55;
        if a.get_bit_64(idx as u64) {
            coef_1.assign(&c15<<1);
            coef_5.assign(&c1155+&coef_1);
            coef_5>>=2;
            coef_1+=&coef_5;
        } else {
            coef_1.assign(&c1155);
            coef_1>>=1;
            coef_5.assign(&c15);
        }
        idx-=1;
    }
    coef_5
}
fn main() {
    for i in 0..100 {println!("{}",fib(Integer::from(i)))}
    let now=std::time::Instant::now();
    let x=fib(Integer::from(10_0000_0000)); // calculate it in several seconds.
    println!("{:?}",now.elapsed());
    println!("{}",x.mod_u64(1145141919));
}
4 
fn print_fibonacci(a: i32, b: i32, n: i32) {
    if n > 0 {
        print!("{} ", b);
        print_fibonacci(b, a + b, n - 1);
    }
}

fn main() {
    let a: i32 = 0;
    let b: i32 = 1;
    let n: i32 = 12;

    println!("Fibonacci series:");
    print_fibonacci(a, b, n);
    println!();
}
5

I think he wants to calculate fib(n) without calculating the previous variable in the recursion/iteration.
Just like a math formula, as shown in @Neutron3529's answer.

6

Caution, I don't know up to which number this formula is exact (when using limited precision floats):

fn fib(idx: usize) -> u64 {
    let sqrt5 = 5.0_f64.sqrt();
    let phi = (1.0 + sqrt5) / 2.0;
    let n = idx as f64;
    ((phi.powf(n) - (1.0 - phi).powf(n)) / sqrt5).round() as u64
}

fn main() {
    for i in 1..=50 {
        println!("fib({i}) = {}", fib(i));
    }
}

(Playground)

Also, it seems to be tricky to use 5.0_f64.sqrt() in a const context.

7 
    ((phi.powf(n) - (1.0 - phi).powf(n)) / sqrt5).round() as u64
//                ^^^^^^^^^^^^^^^^^^^^^

That part quickly goes to 0 and does not even effect the solution at the beginning of the sequence, and can thus just be left out.

3 Likes
8

You can calculate up to the 93rd Fibonacci number in u64 (or 186 in u128). [1]

The formula (simplified or not) is good through 70 using f64.

  1. The ultimate fixed-size-numbers reduction of the OP is to just hard code a small table :slight_smile:. ↩ī¸Ž

4 Likes
9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.