Carl Friedrich Bolz-Tereick pushed to branch branch/default at PyPy / pypy
Commits: 5af4ae79 by Carl Friedrich Bolz-Tereick at 2022-09-12T22:12:41+02:00 #3805 implement a sub-quadratic algorithm for int(<some huge string>), O(len(s) ** 1.58) adapted from pure python code in https://github.com/python/cpython/pull/96673 --HG-- branch : rbigint-fromstr-subquadratic - - - - - 902a801b by Carl Friedrich Bolz-Tereick at 2022-09-13T20:55:03+02:00 fix rounding, thanks bjorn martinsson --HG-- branch : rbigint-fromstr-subquadratic - - - - - e10e338f by Carl Friedrich Bolz-Tereick at 2022-09-13T22:27:38+02:00 test for previous commit --HG-- branch : rbigint-fromstr-subquadratic - - - - - 9dd7b25e by Carl Friedrich Bolz-Tereick at 2022-09-15T12:49:31+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - c431c200 by Carl Friedrich Bolz-Tereick at 2022-09-24T12:32:19+02:00 intermediate checkin: resurrect the lopsided karatsuba multiplication case which was wrongly removed it helps a lot for unbalanced huge multiplications. before this commit, unbalanced multiplications would fall back to using O(n**2) base case multiplication, no matter their size not quite sure yet which algorithm to use, CPython's or my own. both fix the complexity, my own seems unexpectedly faster. --HG-- branch : rbigint-fromstr-subquadratic - - - - - dde396a4 by Carl Friedrich Bolz-Tereick at 2022-09-24T12:35:57+02:00 oops --HG-- branch : rbigint-fromstr-subquadratic - - - - - fc674e42 by Carl Friedrich Bolz-Tereick at 2022-09-24T13:22:17+02:00 save a useless multiplication by 0 in the base case --HG-- branch : rbigint-fromstr-subquadratic - - - - - 50615b01 by Carl Friedrich Bolz-Tereick at 2022-09-24T21:04:27+02:00 introduce accessors for size and sign --HG-- branch : rbigint-fromstr-subquadratic - - - - - 8e82e35e by Carl Friedrich Bolz-Tereick at 2022-10-06T15:28:13+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - 11a53919 by Carl Friedrich Bolz-Tereick at 2022-10-06T15:33:13+02:00 Backed out changeset e4c06197fb2d my ideas in that direction didn't help and it breaks other things --HG-- branch : rbigint-fromstr-subquadratic - - - - - 8731e5e2 by Carl Friedrich Bolz-Tereick at 2022-10-09T17:12:39+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - a0b25a34 by Carl Friedrich Bolz-Tereick at 2022-10-09T21:25:18+02:00 implement lopsided mul in the naive way, in my benchmarks it's consistently faster than CPython's approach --HG-- branch : rbigint-fromstr-subquadratic - - - - - 89fdef2c by Carl Friedrich Bolz-Tereick at 2022-10-09T21:25:50+02:00 some more hypothesis tests for string conversion --HG-- branch : rbigint-fromstr-subquadratic - - - - - 713f9727 by Carl Friedrich Bolz-Tereick at 2022-10-09T21:46:38+02:00 make rbigint.floordiv and rbigint.mod also use rbigint.divmod, to benefit from its better complexity for huge inputs --HG-- branch : rbigint-fromstr-subquadratic - - - - - b96d3c4f by Carl Friedrich Bolz-Tereick at 2023-05-18T14:39:43+02:00 merge default --HG-- branch : rbigint-fromstr-subquadratic - - - - - b88b532d by Carl Friedrich Bolz-Tereick at 2023-05-18T16:29:09+02:00 merge heads --HG-- branch : rbigint-fromstr-subquadratic - - - - - 4f8eb614 by Carl Friedrich Bolz-Tereick at 2023-05-18T17:35:28+02:00 some cleanups in the tests --HG-- branch : rbigint-fromstr-subquadratic - - - - - 193767c6 by Carl Friedrich Bolz-Tereick at 2023-05-18T22:04:12+02:00 some additional hypothesis tests that don't rely on the underlying long implementation --HG-- branch : rbigint-fromstr-subquadratic - - - - - 46c30169 by Carl Friedrich Bolz-Tereick at 2023-05-19T09:22:10+02:00 - ouch, one of the tests was not actually checking anything - add a test to check that the big divmod path is actually used --HG-- branch : rbigint-fromstr-subquadratic - - - - - cca76a1f by Carl Friedrich Bolz-Tereick at 2023-05-20T12:00:19+02:00 some more tests for fromrarith_int --HG-- branch : rbigint-fromstr-subquadratic - - - - - b6b4fcdc by Carl Friedrich Bolz-Tereick at 2023-05-20T12:00:38+02:00 after some more testing: we can reduce the minimum size for when to use the new algorithm for rbigint.fromstr --HG-- branch : rbigint-fromstr-subquadratic - - - - - 001e4396 by Carl Friedrich Bolz-Tereick at 2023-05-20T12:13:53+02:00 use a string builder --HG-- branch : rbigint-fromstr-subquadratic - - - - - 5e853322 by Carl Friedrich Bolz-Tereick at 2023-05-20T20:18:31+02:00 reduce the runtime of this hypothesis test --HG-- branch : rbigint-fromstr-subquadratic - - - - - 4f7edf0c by Carl Friedrich Bolz-Tereick at 2023-05-23T08:49:18+02:00 merge rbigint-fromstr-subquadratic implement the base 10 string-to-int conversion using a divide an conquer algorithm with complexity O(n**1.58). The algorithm is due to Bjorn Martinsson. In the process, I discovered that the "lopsided" case of karatsuba multiplication was removed for no good reason at some point. I re-measured and reimplemented it. - - - - - 3 changed files: - rpython/rlib/rbigint.py - rpython/rlib/rstring.py - rpython/rlib/test/test_rbigint.py View it on Heptapod: https://foss.heptapod.net/pypy/pypy/-/compare/3e71db3d1055184f8f089c28cdada8f7d5c4dc89...4f7edf0c60f77e92cf0a5df18bbbbef1a3a108e9 -- View it on Heptapod: https://foss.heptapod.net/pypy/pypy/-/compare/3e71db3d1055184f8f089c28cdada8f7d5c4dc89...4f7edf0c60f77e92cf0a5df18bbbbef1a3a108e9 You're receiving this email because of your account on foss.heptapod.net.
_______________________________________________ pypy-commit mailing list -- pypy-commit@python.org To unsubscribe send an email to pypy-commit-le...@python.org https://mail.python.org/mailman3/lists/pypy-commit.python.org/ Member address: arch...@mail-archive.com
