Return to Answer

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.

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.

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}\$

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.

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.

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 you probably gain on parallelizing less than you loose on 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}\$

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.

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}\$

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.