Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c++
Subject: Bignum multiplication in Python vs GMP (was: constexpr is really
 very smart!)
Date: Wed, 25 Dec 2024 11:05:05 +0200
Organization: A noiseless patient Spider
Lines: 82
Message-ID: <20241225110505.00001733@yahoo.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>
	<86ttatcj2x.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 25 Dec 2024 10:05:24 +0100 (CET)
Injection-Info: dont-email.me; posting-host="44b1cff1d808ffa4568a5ebfd22af919";
	logging-data="2455340"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18XRXuP2W0pyOwkwsrzucXC/PaSkVqa0Xo="
Cancel-Lock: sha1:CcGgP1At9XAK4OMnXWBRXvd+mIQ=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 4965

On Tue, 24 Dec 2024 05:21:42 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> 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.
>

I did few more time measurements both with GMP and with Python. It
clearly showed that they use not just different implementations of
bignum multiplication, but different algorithms.
GMP multiplication for operands in range of above ~200,000 bits is
approximately O(N*log(N)) with number of bits, or just a little bit
slower than that. 
Python multiplication scale much worse, approximately as (N**1.55).

And indeed after binging more I had seen the following discussion on
reddit:
https://www.reddit.com/r/Python/comments/7h62ul/python_largeinteger_computation_speed_a_comparison/

A relevant quote:
"Python seems to use two algorithms for bignum multiplication: "the
O(N**2) school algorithm" and Karatsuba if both operands contain more
than 70 decimal digits. (Your example reaches 70 decimal digits already
after the 5th(?) squaring, and after the 22nd there are ~17million
decimal digits(?). The wast majority of the time is spent on the last
one or two multiplications i.e. Karatsuba.)

Meanwhile GMP implements seven multiplication algorithms: The same(?)
"school" and Karatsuba algorithms, plus various Toom and an FFT method
(Strassen), but I'm unclear on what the exact thresholds are that
select these. It seems these thresholds are in "limbs" ("the part of a
multi-precision number that fits in a single machine word") instead of
decimal digits, with e.g. FFT method being used after "somewhere
between 3000 and 10000 limbs", i.e. >~30k - 100k(?) decimal digits, so
it would probably be used for the relevant steps in your example."


It seem that that threshold for FFT method mentioned in the quote
applies to number of limbs (i.e. 64-bit groups of bits in our specific
case) in the product rather than in the operands. Also it is possible
that in the newer versions of GMP the threshold is a lower than it
was 7 years ago.

I wonder, why python uses its own thing instead of GMP.
Incompatible licenses or plain NIH ?