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_di
New submission from Pernici Mario <[EMAIL PROTECTED]>:
In this patch x_mul(a, b) uses fewer bit operations for a != b,
asymptotically half of them.
On the three computers I tried the speed-up is around 5% for size=4
and it increases up to 45-60% just below the Karatsuba cutoff,
then it dec
Pernici Mario <[EMAIL PROTECTED]> added the comment:
Yes, I think that the speed-up is due to reducing the number of
shifts and masks.
Changing PyLong_SHIFT to 16 would be complicated; for instance in
v_iadd() carry could not be a digit of 16 bits anymore; writing code
specific for
Pernici Mario <[EMAIL PROTECTED]> added the comment:
Mark, following your suggestions about using bigger integer types,
I added code to convert Python numbers to arrays of twodigits,
when a 64 bit integer type is supported, and for numbers with size
larger than 20; otherwise the code
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
Pernici Mario added the comment:
The attached patch uses mul1 in long_mul in the version patched with
30bit_longdigit13+optimizations.patch
Comparison between these two patches on hp pavilion Q8200 2.33GHz
pybench patch new patch
SimpleIntegerArithmetic 89 85
other
Pernici Mario added the comment:
This patch comes from 30bit_longdigit13+optimizations1.patch in issue4258
with modification for the case of multiplication by 0; it passes
test_long.py and pidigits is a bit faster.
--
Added file: http://bugs.python.org/file13394/longobject_diff1
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
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
New submission from Pernici Mario:
A trivial optimization can be made in ``pow(a, b, c)``
if ``b`` is even and ``c - a < a``
```
In [1]: c = (1 << 100) + 1
In [2]: a = c - 1234567
In [3]: b = 2
In [4]: %timeit pow(a, b, c)
1 loops, best of 3: 3.03 s per loop
In [5]: %timeit
10 matches
Mail list logo
