3 ms·
Indeed, the naive algorithm is quadratic due to the multiplications. Yet everyone familiar with even a bit of crypto and/or otherwise working with huge numbers
by userbinator 4y ago
Indeed, the naive algorithm is quadratic due to the multiplications. Yet everyone familiar with even a bit of crypto and/or otherwise working with huge numbers knows that multiplication can be subquadratic.
...and in doing a bit of research on how Python does multiplication, I found some... rather odd opinions, considering it's one of the few languages with arbitrary precision integers: https://discuss.python.org/t/faster-large-integer-multiplication/13300 https://discuss.python.org/t/faster-large-integer-multiplica...
- stingraycharles 4y agoIntegers / floating point / bignum is such a problem in almost any language, with multiple competing implementations in most languages. I’d argue it’s probably a harder problem than Unicode support, although Python also managed to make that difficult with multiple implementations in the wild (both UCS-2 and UCS-4 are commonly used, depending on how it was compiled).