Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c++ Subject: Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Date: Thu, 26 Dec 2024 18:42:35 -0800 Organization: A noiseless patient Spider Lines: 61 Message-ID: <86ikr5dexw.fsf@linuxsc.com> References: <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> <20241225110505.00001733@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Fri, 27 Dec 2024 03:42:36 +0100 (CET) Injection-Info: dont-email.me; posting-host="ce9c96fed16de83e8c7d4f3eabb78d96"; logging-data="3431812"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/NMFjk8HcmxaOqn5lokGhHHyRI8I8uapU=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:Zand8r5Ay8uc6E7JuMxViltwhsw= sha1:r7962lrcsv/Lq1SYz3rbMMP8Q4I= Xref: csiph.com comp.lang.c++:121302 Michael S writes: > On Tue, 24 Dec 2024 05:21:42 -0800 > Tim Rentsch wrote: >> >>> [python runs much slower than GMP] >> >> 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). That's consistent with using Karatsuba: log2( 3 ) =~ 1.585. > And indeed after binging more I had seen the following discussion on > reddit: [link] > > 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." That ratio suggests the limbs are 32 bits (ie, roughly 10 digits each). > 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 have no intuition regarding whether a threshold would be chosen based on the sizes of the operands or the sizes of the product. For this particular problem it's only one iteration difference anyway. > I wonder, why python uses its own thing instead of GMP. > Incompatible licenses or plain NIH ? Perhaps (1) python doesn't want to be bound by the rather severe terms of a GNU license, or (2) historical inertia. Let me add that I appreciate your excellent investigation results. They reinforce my view that it was wise for me to cease the deep dives into performance issues. :)