Re: constexpr is really very smart!

On Sun, 22 Dec 2024 10:25:59 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:
 

On Fri, 20 Dec 2024 14:59:07 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
 

I ran a python version to compute fibonacci( 10000000 ).  This code
ran 30% faster than the previous version, which I would be is
almost entirely due to the expression factoring with 'c'.  Great! 

>
This one does fib(10M) in 89 msec on my very old home PC.
>
[code] 

 
You are the speed king!

But approximately the same code in python is MUCH slower.
2.9 sec on 11 y.o. PC that still serves me as a desktop at work.
2.0 sec on 5.5 y.o. mall server.

I don't really understand why.
I expected that nearly all time is spend in multiplication of few huge
numbers, probably over 75% of time in last couple of steps (6
multiplications). And I was under impression that internally Python
uses the same GMP library that I used in C. So I expected the same
speed, more or less. May be, 1.5x slowdown because of less efficient
memory handling in Python. 35x difference is a big surprise.


Here is my python routine.

def fib(n):
  if n < 1:
    return 0

  tmp = n
  msb = 1
  while tmp > 1:
    msb += msb
    tmp //= 2

  f0=0; f1=1;
  while msb > 1:
    ff0 = f0*f0 + f1*f1
    f1 = (f0+f0+f1)*f1
    f0 = ff0
    msb //= 2
    if msb & n:
      f0 = f1
      f1 += ff0
  return f1