Re: constexpr is really very smart!

On 18/12/2024 11:51, Michael S wrote:

Iterative:
 
static long long fib(long n)
{
   if (n <= 0)
     return 0;
   // find MS bit
   unsigned long tmp = n;
   unsigned long bit = 1;
   while (tmp > 1) {
     bit += bit;
     tmp /= 2;
   }
   // for n > 0
   // fib(n*2)   = (fib(n-1)+fib(n+1))*fib(n)
   // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
   long long a = 0, b = 1;
   while (bit > 1) {
     long long c = a + b; // fib(n+1)
     bit /= 2;
     if ((n & bit)==0) { // (n-1,n) => (n*2-1,n*2)
       c += a;
       a = a*a + b*b;
       b = c*b;
     } else {            // (n-1,n) => (n*2,n*2+1)
       a = (a + c)*b;
       b = b*b + c*c;
     }
   }
   return b;
}

Here is my test result of this iterative function:

D:\CmdLine\C_Cpp\Chrono06>program
Testing fibonacci function
fib(92) = 7540113804746346429
Time taken by fib: 0 microseconds
 
D:\CmdLine\C_Cpp\Chrono06>program
Testing fibonacci function
fib(92) = 7540113804746346429
Time taken by fib: 0 microseconds
 
D:\CmdLine\C_Cpp\Chrono06>program
Testing fibonacci function
fib(92) = 7540113804746346429
Time taken by fib: 0 microseconds
 
D:\CmdLine\C_Cpp\Chrono06>program
Testing fibonacci function
fib(92) = 7540113804746346429
Time taken by fib: 0 microseconds

The full program to run in G++ is:

<+++++++++++++++++++++++++++++++++++++++++++++>

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

long long fib(long n)
{
     if (n <= 0)
         return 0;
     // find MS bit
     unsigned long tmp = n;
     unsigned long bit = 1;
     while (tmp > 1)
     {
         bit += bit;
         tmp /= 2;
     }
     // for n > 0
     // fib(n*2)   = (fib(n-1)+fib(n+1))*fib(n)
     // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
     long long a = 0, b = 1;
     while (bit > 1)
     {
         long long c = a + b; // fib(n+1)
         bit /= 2;
         if ((n & bit) == 0)
         { // (n-1,n) => (n*2-1,n*2)
             c += a;
             a = a * a + b * b;
             b = c * b;
         }
         else
         { // (n-1,n) => (n*2,n*2+1)
             a = (a + c) * b;
             b = b * b + c * c;
         }
     }
     return b;
}

int main(void)
{
     cout << "Testing fibonacci function\n";
     auto start = high_resolution_clock::now();
     constexpr int num = 92;
     long long result = fib (num);
     auto stop = high_resolution_clock::now();

     auto duration = duration_cast<microseconds>(stop - start);
     cout << "fib(" << num << ") = " << result << "\n";
     cout << "Time taken by fib: " << duration.count() << " microseconds\n";

}

<+++++++++++++++++++++++++++++++++++++++++++++>