1
\$\begingroup\$

I have a piece of code that attempts to reduce the work and span in making a Fibonacci sequence. My approach is to parallelize the code as much as possible, along with doing matrix multiplication and exponentiation. Here is my Rust code:

use num_bigint::BigUint;
use rayon::iter::*;
use rayon::prelude::ParallelSlice;
use rayon::join;

fn mat_ops(base: (BigUint, BigUint, BigUint, BigUint), mut exponent: u32) -> (BigUint, BigUint, BigUint, BigUint) {
    if exponent == 0 {
        return (BigUint::from(1u32), BigUint::from(0u32), BigUint::from(0u32), BigUint::from(1u32)); // Identity matrix
    }
    let mut result = (BigUint::from(1u32), BigUint::from(0u32), BigUint::from(0u32), BigUint::from(1u32));
    let mut current_base = base;
    while exponent > 0 {
        if exponent % 2 == 1 {
            result = (
                &result.0 * &current_base.0 + &result.1 * &current_base.2,
                &result.0 * &current_base.1 + &result.1 * &current_base.3,
                &result.2 * &current_base.0 + &result.3 * &current_base.2,
                &result.2 * &current_base.1 + &result.3 * &current_base.3,
            );
        }
        current_base = (
            &current_base.0 * &current_base.0 + &current_base.1 * &current_base.2,
            &current_base.0 * &current_base.1 + &current_base.1 * &current_base.3,
            &current_base.2 * &current_base.0 + &current_base.3 * &current_base.2,
            &current_base.2 * &current_base.1 + &current_base.3 * &current_base.3,
        );

        exponent /= 2;
    }
    result
}

pub fn par_fib_seq(n: u32) -> Vec<BigUint> {
    if n < 1 {
        return Vec::new();
    }

    let fib_matrix = (BigUint::from(1u32), BigUint::from(1u32), BigUint::from(1u32), BigUint::from(0u32));

    let numbers: Vec<u32> = (1..=n).collect();
    let results: Vec<BigUint> = numbers
        .into_par_iter()
        .flat_map(|i| {
            vec![mat_ops(fib_matrix.clone(), i).1] 
        })
        .collect();

    results

}


#[cfg(test)]
mod tests {
    use super::*;
    use num_bigint::BigUint;

    #[test]
    fn test_fib_sequences() {
        let result = par_fib_seq(5);
        let expected = vec![
            BigUint::from(1u32),
            BigUint::from(1u32),
            BigUint::from(2u32),
            BigUint::from(3u32),
            BigUint::from(5u32),
        ];
        assert_eq!(result, expected);

        let result = par_fib_seq(10);
        let expected = vec![
            BigUint::from(1u32),
            BigUint::from(1u32),
            BigUint::from(2u32),
            BigUint::from(3u32),
            BigUint::from(5u32),
            BigUint::from(8u32),
            BigUint::from(13u32),
            BigUint::from(21u32),
            BigUint::from(34u32),
            BigUint::from(55u32),
        ];
        assert_eq!(result, expected);

        let result = par_fib_seq(20);
        let expected = vec![
            BigUint::from(1u32),
            BigUint::from(1u32),
            BigUint::from(2u32),
            BigUint::from(3u32),
            BigUint::from(5u32),
            BigUint::from(8u32),
            BigUint::from(13u32),
            BigUint::from(21u32),
            BigUint::from(34u32),
            BigUint::from(55u32),
            BigUint::from(89u32),
            BigUint::from(144u32),
            BigUint::from(233u32),
            BigUint::from(377u32),
            BigUint::from(610u32),
            BigUint::from(987u32),
            BigUint::from(1597u32),
            BigUint::from(2584u32),
            BigUint::from(4181u32),
            BigUint::from(6765u32),
        ];
        assert_eq!(result, expected);

        let result = par_fib_seq(0);
        let expected: Vec<BigUint> = vec![];
        assert_eq!(result, expected);

        let result = par_fib_seq(1);
        let expected = vec![BigUint::from(1u32)];
        assert_eq!(result, expected);
    }
}

Even though I understand that parallelizing the snippet above more than what I currently have can be tricky due to Fibonacci's sequential nature (each number depends on the previous two), I am hoping to get ideas on reducing its time complexity to \$O(n)\$ and span to \$O(\log^2 n)\$.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Welcome to Code Review! "I have a piece of code that attempts to speed up making a Fibonacci sequence." Does it actually attempt to speed up making one, or just generate one? Also, I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to edit and give it a different title if there is something more appropriate. \$\endgroup\$ Commented Mar 21 at 4:21
  • \$\begingroup\$ hello, I've edited my question to clarify that this piece of code attempts to reduce the work and span when forming a fibonacci sequence. It simply generates one. Thank you \$\endgroup\$ Commented Mar 21 at 4:36
  • 1
    \$\begingroup\$ "parallelize the code as much as possible" In the presence of Binet's formula, I don't even know what that could mean. We have a closed form solution, for arbitrarily large inputs. If the code addresses other goals, state them explicitly, with timing figures. \$\endgroup\$ Commented Mar 21 at 4:42
  • 1
    \$\begingroup\$ Aren't you producing output of size Theta(n^2)? How do you imagine that being possible in O(n) time? \$\endgroup\$ Commented Mar 21 at 13:10
  • 2
    \$\begingroup\$ @nocomment This is a parallelized solution. You produce quadratic output in linear time by doing n or more things at once. Span is a common term in parallelization to refer to the longest sequence of operations that can't be parallelized. Link for info: cs.princeton.edu/~dpw/courses/cos326-12/notes/… \$\endgroup\$ Commented Mar 23 at 15:56

2 Answers 2

Reset to default
6
\$\begingroup\$

I have a hard time trying to figure out what you are trying to achieve.

There are no comments in the code to state your intentions.
Names like mat_ops() are not helpful.

That said, I see a parallelisable way of filling a vector.
"Doing it all from scratch" for each vector value: this seems wasteful.

As an alternative, I imagine "workers" (I don't know the 1st thing about Rust lingo in general or with respect to concurrency in particular) to compute the value from preceding ones, possibly more than one index back.
The biggest problem would seem to be how to have the workers not trash each other's caches/needing fine grain lock-out/synchronisation.

One idea was to partition work taking into accout expected effort: for four workers have the first one process 8, the 2nd 4, the third 2 and the last one 1 15th of the entries; tune the factor between allotments based on how the time varies.
Another would have workers 0 to 3 handle indexes a multiple of 4, +0..3: Fn+4 = 7Fn-Fn-4, starting with 0, 3; 1, 5; 1, 8; and 2, 13, respectively.

\$\endgroup\$
4
\$\begingroup\$

I'm not sure what you are trying to achieve, exactly—but you seem to parallelize at the wrong place.

As far as I can see (but I may see wrong with my exactly zero experience with Rust) you create a sequence of natural numbers, then run a bunch of parallel tasks, each of which raises a [[1,1],[1,0]] matrix to a power to finally extract a consecutive Fibonacci number from it, and then you build a resulting sequence from those extracted numbers.

But what you gain on parallelizing probably does not balance the cost of repeated work. For example, when you call par_fib_seq(20) you calculate \$F_1\$ twenty times, once per each call, but you actually need to calculate it just once for the whole twenty-item sequence. Similarly a mid-result \$F_4\$ appears in calculations every fourth call, when exponent value is divisible by 4.

Calculating a number with exponential steps is a good approach when you need to find just a single number, say \$F_{200}\$. But even then you do not need a full matrix multiplication, a simple 'two terms per step' recurrence will do:

\$\begin{cases}F_{2 n-1} & = {F_{n-1}}^2 + {F_n}^2, \\ F_{2 n} &= (2 F_{n-1}+F_n)F_n.\end{cases}\$

(See Wikipedia article Fibonacci sequence at the end of the section Matrix form – link.)

However, if you need to create a whole sequence \$(F_1, \dots, F_n)\$ at once, then there is no faster way than generating those numbers sequentially. At least for moderate values of n. If n becomes large, say 2000, I would try to split the task into several subsequences (e.g. for index ranges 1..500, 501..1000, 1001..1500, 1501...2000), calculate two initial terms for each interval with the logarithmic routine and then proceed linearly in parallel.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.