Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #121297
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: constexpr is really very smart! |
| Date | 2024-12-24 05:21 -0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <86ttatcj2x.fsf@linuxsc.com> (permalink) |
| References | (6 earlier) <20241220021703.00003e9e@yahoo.com> <86msgqezb8.fsf@linuxsc.com> <20241222000708.000007ef@yahoo.com> <86a5cnfubs.fsf@linuxsc.com> <20241223174708.000062b3@yahoo.com> |
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.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-15 20:20 +0000
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 11:28 +0200
Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 11:18 +0100
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 13:23 +0200
Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 13:43 +0100
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-17 11:08 +0200
Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-17 11:10 +0100
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 03:26 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:39 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 07:42 -0800
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-17 12:54 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 01:33 +0200
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 13:51 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:40 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-20 02:17 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:59 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:07 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:25 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 17:47 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-24 05:21 -0800
Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 11:05 +0200
Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 13:33 +0200
Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:54 -0800
Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:42 -0800
Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-19 19:14 +0000
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 09:45 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 22:00 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:57 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-19 23:45 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:31 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:14 +0200
Re: constexpr is really very smart! James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-12-21 17:55 -0500
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 02:22 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:33 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 00:05 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 17:17 -0800
Re: constexpr is really very smart! Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-12-17 12:20 -0800
Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-18 04:45 +0000
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:17 +0200
csiph-web