How Can I Utilize All CPU Cores for a Fibonacci Calculation in C#?

Lucas sequence is a bit faster than matrix method for finding fibonacci(n), with same time complexity O(log2(n)). For large integers, Karatsuba multiply can be used and also parallelized since it splits and operates on different parts of a big integer.

CCopied
/* lucas sequence method */
int fib(int n) {
    int a, b, p, q, qq, aq;
    a = q = 1;
    b = p = 0;
    while(1) {
        if(n & 1) {
            aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
        }
        n /= 2;
        if(n == 0)
            break;
        qq = q*q;
        q = 2*p*q + qq;
        p = p*p + qq;
    }
    return b;
}  

Please see the comments on the question.

Given the Fibonacci sequence algorithm you want to use, the utilization of additional threads or CPI cores cannot improve its performance in principle. This algorithm cannot be parallelized.

Let me explain some background. There is no such thing as CPU thread. Threads are created dynamically in code, directly by the application developer or not. An example of indirect thread management is TPL, it implements parallelism based on Tasks and Parallel.

When a thread is scheduled for execution, the system assigns one of the CPU cores to execute a slice of a thread code. This assignment can change with time, it depends on the system scheduler algorithm and available resources. Even for single-core CPUs, threading is extremely important. Nevertheless, the application developer can indirectly affect this core assignment using processor affinity or limiting maximum degree of parallelism.

But nothing can organize even the partially parallel execution of an algorithm that is not parallel by its nature, like the sequential calculation of the Fibonacci sequence. I think just the term Fibonacci sequence should suggest it. The next member of the Fibonacci sequence is calculated using a recurrent relation to two previous members. The notions of parallel and sequential are opposite.

Now, I'm not saying that using threads for this algorithm is impossible. It is possible but would create a huge threading misuse. Threading and parallelism are not directly related. You can create and use threads, but you can use them sequentially. A typical effect of such a wrong design is a correct calculation with considerable performance losses. Why? In the case of Fibonacci, you can use two or more threads waiting for each other for the data required for the next recurring step. Only one thread at a time can be not in a wait state. It would be equivalent to single-threaded computing, but it is actually much worse, because of the waste of resources required for the support of the thread operation, thread synchronization, and inter-thread communication.

As a matter of fact, even the performance of some parallel algorithms can be compromised by using Tasks or Parallel. It can happen when the volume of calculations and the level of parallelism don't justify the resource costs of supporting parallelism mechanisms. In particular, it can happen when the number of available CPU cores is insufficient to shift the balance in favor of the parallel execution. In this case, even a potentially parallel algorithm can show better performance in a single-threaded implementation.

You can't parallelize current algorithm efficiently. Please, note that to compute F(n) your should know F(n - 1) which in turn requires F(n - 2) etc. So all you have to do is to compute F(0), F(1), F(2), ..., F(n) sequentially.

What you can do is to change algorithm from current O(n) time complexity to more efficient O(log(n)) algorithm:

Raise matrix A

|1 1|
|0 1|

into n power and take A[1, 1] item.
For instance,

A^10 = |34 55|
       |55 89|

A[1, 1] = 89 <- 10th Fibonacci number

How to do efficient raise into power? Represent n as binary:

n = 10 = 1010 (binary)

A^1 = [1 1; 0 1]
A^2 = (A^1)^2 = [1 1; 1 2]
A^4 = (A^2)^2 = [2 3; 3 5]
A^8 = (A^4)^2 = [13 21; 21 34]

A^10 = A^2 * A^8 = [34 55; 55 89]

Code:

CSHARPCopied
// Matrix multiplication
private static BigInteger[,] Multiply(BigInteger[,] left, BigInteger[,] right) => 
  new BigInteger[,] {
    { left[0, 0] * right[0, 0] + left[0, 1] * right[1, 0], 
      left[0, 0] * right[0, 1] + left[0, 1] * right[1, 1] },

    { left[1, 0] * right[0, 0] + left[1, 1] * right[1, 0], 
      left[1, 0] * right[0, 1] + left[1, 1] * right[1, 1] },
  };

CSHARPCopied
private static BigInteger Fibo(int n) {
  if (n < 0)
    return (n % 2 == 0 ? -1 : 1) * Fibo(-n);

  var result = new BigInteger[,] { { 1, 0 }, { 0, 1 } };
  var current = new BigInteger[,] { { 1, 1 }, { 1, 0 } };

  for (; n > 0; n /= 2) { // Note n /= 2 - we have O(log(n)) time 
    if (n % 2 != 0)
      result = Multiply(result, current);

    current = Multiply(current, current);
  }

  return result[0, 0];
}

Demo:

CSHARPCopied
var result = Fibo(1_000_000);

var text = result.ToString();

Console.WriteLine($"{text[..5]} .. {text[^5..]} ({text.Length} digits)");

Output (about 1 second on my workstation):

31604 .. 37501 (208988 digits)

Fiddle

Edit:

Please, note that this algorithm can easily be made parallel, a very good candidate is Multiply:

CSHARPCopied
// Matrix multiplication, parallel version
private static BigInteger[,] Multiply(BigInteger[,] left, BigInteger[,] right) {
  var result = new BigInteger[2, 2];

  Parallel.Invoke(
    () => result[0, 0] = left[0, 0] * right[0, 0] + left[0, 1] * right[1, 0],
    () => result[0, 1] = left[0, 0] * right[0, 1] + left[0, 1] * right[1, 1],
    () => result[1, 0] = left[1, 0] * right[0, 0] + left[1, 1] * right[1, 0],
    () => result[1, 1] = left[1, 0] * right[0, 1] + left[1, 1] * right[1, 1]);

  return result;
}