Re: constexpr is really very smart!

Michael S <already5chosen@yahoo.com> writes:

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.

That matches my experience with doing this in python.

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.

Yes, I have no explanation either.  Your reasoning looks sound to
me.

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

Here is my latest python code.

  def fibonacci( n ) :
    return  ff2( 1, 0, high_mask( 1, n ), n )

  def high_mask( m, n ) :
    return  m>>1 if m > n else high_mask( m<<1, n )

  def ff2( a, b, m, n ) :
    c = a+b
    if  m & n   :   return  ff2(          (a+c)*b, b*b+c*c,  m>>1, n )
    if  m       :   return  ff2( a*a+b*b, (a+c)*b,           m>>1, n )
    return  b

Performance trials of these two definitions gave nearly identical
results, within 0.4 percent.