[issue3451] Asymptotically faster divmod and str(long)

2022-01-29 Thread Tim Peters
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 thi

[issue3451] Asymptotically faster divmod and str(long)

2021-04-13 Thread STINNER Victor
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 ke

[issue3451] Asymptotically faster divmod and str(long)

2021-04-13 Thread Carl Friedrich Bolz-Tereick
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)

2021-04-13 Thread Mark Lawrence
Change by Mark Lawrence : -- nosy: -BreamoreBoy ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.

[issue3451] Asymptotically faster divmod and str(long)

2021-04-13 Thread Mark Dickinson
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)

2021-04-13 Thread Mark Dickinson
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 t

[issue3451] Asymptotically faster divmod and str(long)

2021-04-13 Thread Carl Friedrich Bolz-Tereick
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 f

[issue3451] Asymptotically faster divmod and str(long)

2014-06-22 Thread Mark Lawrence
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 _

[issue3451] Asymptotically faster divmod and str(long)

2013-05-31 Thread Eric V. Smith
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 ___ __

[issue3451] Asymptotically faster divmod and str(long)

2011-04-27 Thread Xuanji Li
Changes by Xuanji Li : -- nosy: +xuanji ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/m

[issue3451] Asymptotically faster divmod and str(long)

2010-04-13 Thread Mark Dickinson
Mark Dickinson 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 ___ Python tracker <

[issue3451] Asymptotically faster divmod and str(long)

2010-01-03 Thread Mark Dickinson
Changes by Mark Dickinson : -- versions: -Python 3.1 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mai

[issue3451] Asymptotically faster divmod and str(long)

2009-09-21 Thread steve21
Changes by steve21 : -- nosy: +steve21 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/ma

[issue3451] Asymptotically faster divmod and str(long)

2009-05-16 Thread Daniel Diniz
Changes by Daniel Diniz : -- nosy: +haypo stage: -> patch review versions: +Python 3.2 ___ Python tracker ___ ___ Python-bugs-list mai

[issue3451] Asymptotically faster divmod and str(long)

2009-03-30 Thread Pernici Mario
Pernici Mario 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 done on it, as Mark pointed o

[issue3451] Asymptotically faster divmod and str(long)

2009-03-30 Thread Pernici Mario
Pernici Mario 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: http://bugs.python.org/file13496/longformat.diff __

[issue3451] Asymptotically faster divmod and str(long)

2009-03-24 Thread Mark Dickinson
Mark Dickinson 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: (1) the huge number

[issue3451] Asymptotically faster divmod and str(long)

2008-10-13 Thread Pernici Mario
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)

2008-09-24 Thread Mark Dickinson
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]> ___ __

[issue3451] Asymptotically faster divmod and str(long)

2008-09-08 Thread Pernici Mario
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; t

[issue3451] Asymptotically faster divmod and str(long)

2008-08-11 Thread Mark Dickinson
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 meth

[issue3451] Asymptotically faster divmod and str(long)

2008-08-06 Thread Fredrik Johansson
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]>

[issue3451] Asymptotically faster divmod and str(long)

2008-08-04 Thread Mark Dickinson
Changes by Mark Dickinson <[EMAIL PROTECTED]>: Removed file: http://bugs.python.org/file11059/fast_str.py ___ Python tracker <[EMAIL PROTECTED]> ___ ___

[issue3451] Asymptotically faster divmod and str(long)

2008-08-04 Thread Mark Dickinson
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]>

[issue3451] Asymptotically faster divmod and str(long)

2008-08-04 Thread Mark Dickinson
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 mu

[issue3451] Asymptotically faster divmod and str(long)

2008-08-04 Thread Mark Dickinson
Mark Dickinson <[EMAIL PROTECTED]> added the comment: See also issue 1746088. ___ Python tracker <[EMAIL PROTECTED]> ___ ___ Python-bugs-list mai

[issue3451] Asymptotically faster divmod and str(long)

2008-08-04 Thread Mark Dickinson
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 rea

[issue3451] Asymptotically faster divmod and str(long)

2008-07-27 Thread Fredrik Johansson
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)

2008-07-27 Thread Fredrik Johansson
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)

2008-07-27 Thread Fredrik Johansson
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 conv

[issue3451] Asymptotically faster divmod and str(long)

2008-07-26 Thread Mark Dickinson
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 con

[issue3451] Asymptotically faster divmod and str(long)

2008-07-26 Thread Facundo Batista
Changes by Facundo Batista <[EMAIL PROTECTED]>: -- nosy: +marketdickinson ___ Python tracker <[EMAIL PROTECTED]> ___ ___ Python-bugs-lis

[issue3451] Asymptotically faster divmod and str(long)

2008-07-26 Thread Fredrik Johansson
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): http://fredrik-j.bl