Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: constexpr is really very smart!
Date: Tue, 24 Dec 2024 05:21:42 -0800
Organization: A noiseless patient Spider
Lines: 76
Message-ID: <86ttatcj2x.fsf@linuxsc.com>
References: <vjndub$2glcu$1@paganini.bofh.team> <20241216112808.00003f74@yahoo.com> <86jzbyghdw.fsf@linuxsc.com> <20241218013342.0000518a@yahoo.com> <20241218135131.00000006@yahoo.com> <86zfksf4lb.fsf@linuxsc.com> <20241220021703.00003e9e@yahoo.com> <86msgqezb8.fsf@linuxsc.com> <20241222000708.000007ef@yahoo.com> <86a5cnfubs.fsf@linuxsc.com> <20241223174708.000062b3@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Tue, 24 Dec 2024 14:21:43 +0100 (CET)
Injection-Info: dont-email.me; posting-host="0b35227985084685f7db26e049ff6a4a"; logging-data="1971237"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ZaD4UgKwJU/8D800+OyX4cu8DOnZ7JOg="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:bsgqeONYEubFUWVcWaApRiDJpQA= sha1:JOSWVEyWyubN6WiMVjKoGI7J3v0=
Xref: csiph.com comp.lang.c++:121297

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.