[issue3451] Asymptotically faster divmod and str(long)

Tim Peters added the comment: Ha! This will never die. More discussion in bpo-46558. Ya, I already closed it, but don't want to. I opened it to begin with to record an int->str method that doesn't use division, so it didn't really belong on this report. What if we _didn't_ convert these

[issue3451] Asymptotically faster divmod and str(long)

STINNER Victor added the comment: Python has a reasonable efficiency up to 1000 decimal digits (according to benchmark) which is already really great! Operations with more than 1000 decimal digits is an uncommon. IMO you should use a dedicated library like GMP for that. I would prefer to

[issue3451] Asymptotically faster divmod and str(long)

Carl Friedrich Bolz-Tereick added the comment: yes, that sounds fair. In PyPy we improve things occasionally if somebody feels like working on it, but in general competing against GMP is a fools errand. -- ___ Python tracker

[issue3451] Asymptotically faster divmod and str(long)

Change by Mark Lawrence : -- nosy: -BreamoreBoy ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson added the comment: FWIW, I think we should close this; the same comments as in issue 26256 apply. See msg259408 onwards in that discussion. -- ___ Python tracker

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson added the comment: > we have implemented a faster algorithm for divmod for big numbers using > Mark's fast_div.py in PyPy Urk! I hope your implementation included a healthy dose of validation, testing and cleanup. :-) (I have no doubts that it did.) I'd consider fast_div.py

[issue3451] Asymptotically faster divmod and str(long)

Carl Friedrich Bolz-Tereick added the comment: FWIW, we have implemented a faster algorithm for divmod for big numbers using Mark's fast_div.py in PyPy. In particular, this speeds up str(long) for large numbers significantly (eg calling str on the result of math.factorial(2**17) is now 15x

[issue3451] Asymptotically faster divmod and str(long)

Mark Lawrence added the comment: As issue18107 has been closed as a duplicate of this, should this be moved to open from languishing? -- nosy: +BreamoreBoy, serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3451

[issue3451] Asymptotically faster divmod and str(long)

Eric V. Smith added the comment: See also issue18107, in particular http://mail.python.org/pipermail/pypy-dev/2013-May/011433.html. -- nosy: +eric.smith ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3451

[issue3451] Asymptotically faster divmod and str(long)

Changes by Xuanji Li xua...@gmail.com: -- nosy: +xuanji ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3451 ___ ___ Python-bugs-list mailing list

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson dicki...@gmail.com added the comment: Unassigning myself for now. The most recent patch still needs work before it can be considered for inclusion. -- assignee: mark.dickinson - status: open - languishing versions: -Python 2.7 ___

[issue3451] Asymptotically faster divmod and str(long)

Changes by Mark Dickinson dicki...@gmail.com: -- versions: -Python 3.1 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3451 ___ ___

[issue3451] Asymptotically faster divmod and str(long)

Changes by steve21 steve872929...@yahoo.com.au: -- nosy: +steve21 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3451 ___ ___ Python-bugs-list

[issue3451] Asymptotically faster divmod and str(long)

Changes by Daniel Diniz aja...@gmail.com: -- nosy: +haypo stage: - patch review versions: +Python 3.2 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue3451 ___

[issue3451] Asymptotically faster divmod and str(long)

Pernici Mario pern...@users.sourceforge.net added the comment: In this patch there is an implementation of the algorithm to convert numbers in strings by recursively splitting the number in half, adapted from Fredrik's div.py -- Added file:

[issue3451] Asymptotically faster divmod and str(long)

Pernici Mario pern...@users.sourceforge.net added the comment: In this second patch to the above patch it is added the recursive division algorithm by Burnikel and Ziegler (BZ) from longobject2.diff, unmodified, to see the effect of the subquadratic algorithm; there is still a lot of work to be

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson dicki...@gmail.com added the comment: The longobject2.diff patch probably doesn't apply cleanly any more. Anyone interested in updating it? I think this patch looks like a promising beginning, but there's still quite a lot of work to do. The main concerns at the moment are:

[issue3451] Asymptotically faster divmod and str(long)

Pernici Mario [EMAIL PROTECTED] added the comment: In this patch I added to the patch by Mark in issue 3944 the code in the previous patch, modified to release memory in case of exceptions. Benchmark for division on Athlon 64 3800+ with respect to Python3.0: (1) Python with patch 30bit.patch

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: Thanks for the patch, Mario! I'll give a look when I get the chance. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3451 ___

[issue3451] Asymptotically faster divmod and str(long)

Pernici Mario [EMAIL PROTECTED] added the comment: I have translated in C the algorithm for long division by Burnikel and Ziegler (BZ), using the Python version fast_div.py and the suggestions by Mark. Here is a benchmark for divmod(p. q), p = 7**np, q = 5**nq digits = q_digits = p_digits/2;

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: Indeed, that seems to be much faster. In the mean time, do you mind if I steal the code? :-) Not at all! I guess constant factors could well appear and/or disappear when recoding in C; it might well be worth trying to implement both methods

[issue3451] Asymptotically faster divmod and str(long)

Fredrik Johansson [EMAIL PROTECTED] added the comment: Indeed, that seems to be much faster. In the mean time, do you mind if I steal the code? :-) ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3451 ___

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: There's also the recursive division algorithm due to Burnikel and Ziegler; this might be worth a look. I think it's the same asymptotic complexity (constant times karatsuba multiplication complexity), but may turn out to be faster for one

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: See also issue 1746088. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3451 ___ ___ Python-bugs-list mailing

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: Here's a pure Python implementation of the Burnikel and Ziegler recursive division algorithm. I've no idea whether it's faster or slower than Newton, but it might be worth a look. It depends heavily on bit operations, which ought to be

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: Oops. Wrong file. Here's the right one. Added file: http://bugs.python.org/file11060/fast_div.py ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3451

[issue3451] Asymptotically faster divmod and str(long)

Changes by Mark Dickinson [EMAIL PROTECTED]: Removed file: http://bugs.python.org/file11059/fast_str.py ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3451 ___

[issue3451] Asymptotically faster divmod and str(long)

Mark Dickinson [EMAIL PROTECTED] added the comment: Would there be any interest in porting these algorithms to C and using them in the standard Python long implementation? Yes, definitely! Though it depends a little bit how much complication is involved. A subquadratic algorithm for

[issue3451] Asymptotically faster divmod and str(long)

Fredrik Johansson [EMAIL PROTECTED] added the comment: Yes, definitely! Though it depends a little bit how much complication is involved. Not that much, I think, the pure Python version being just a few lines of code (plus a few more lines of boilerplate). But I'm not too familiar with

[issue3451] Asymptotically faster divmod and str(long)

Fredrik Johansson [EMAIL PROTECTED] added the comment: For your convenience, I have split the division and numeral code off to a standalone .py file which I'm attaching here. I also updated the remainder logic to use the default divmod instead of repeated subtraction, which ensures worst-case

[issue3451] Asymptotically faster divmod and str(long)

Fredrik Johansson [EMAIL PROTECTED] added the comment: And here some timings on my laptop. Both int-str and balanced division become faster somewhere between 1000 and 2000 digits. This is after editing the division benchmark to use random numbers instead of exact powers of ten (interestingly

[issue3451] Asymptotically faster divmod and str(long)

New submission from Fredrik Johansson [EMAIL PROTECTED]: A few weeks ago, I blogged about taking advantage of Karatsuba multiplication and Newton's method to divide big integers quickly (some of you may have read it, as it was posted to Daily Python-URL among other places):

[issue3451] Asymptotically faster divmod and str(long)

Changes by Facundo Batista [EMAIL PROTECTED]: -- nosy: +marketdickinson ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue3451 ___ ___ Python-bugs-list