Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #121302

Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!)

Show key headers only | View raw

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 24 Dec 2024 05:21:42 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> 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. :)

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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