On Jul 7, 9:30 am, Ulrich Eckhardt ulrich.eckha...@dominolaser.com
wrote:
That said, I'm sure that the developers would accept a patch that switches
to a different algorithm if the numbers get large enough. I believe it
already doesn't use Karatsuba for small numbers that fit into registers,
Billy Mays wrote:
On 07/06/2011 04:02 PM, Ian Kelly wrote:
According to Wikipedia:
In practice the Schönhage–Strassen algorithm starts to outperform
older methods such as Karatsuba and Toom–Cook multiplication for
numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
I
On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
ulrich.eckha...@dominolaser.com wrote:
Even worse, most people would actually pay for its use, because they don't
use numbers large enough to merit the Schönhage–Strassen algorithm.
As it stands, Karatsuba is only used for numbers greater than a
On Thu, Jul 7, 2011 at 9:49 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
ulrich.eckha...@dominolaser.com wrote:
Even worse, most people would actually pay for its use, because they don't
use numbers large enough to merit the Schönhage–Strassen
in context:
http://old.nabble.com/Large-number-multiplication-tp32007815p32014454.html
Sent from the Python - python-list mailing list archive at Nabble.com.
--
http://mail.python.org/mailman/listinfo/python-list
On Jul 7, 1:30 am, Ulrich Eckhardt ulrich.eckha...@dominolaser.com
wrote:
Billy Mays wrote:
On 07/06/2011 04:02 PM, Ian Kelly wrote:
According to Wikipedia:
In practice the Schönhage–Strassen algorithm starts to outperform
older methods such as Karatsuba and Toom–Cook multiplication
I was looking through the python source and noticed that long
multiplication is done using the Karatsuba method (O(~n^1.5)) rather
than using FFTs O(~n log n). I was wondering if there was a reason the
Karatsuba method was chosen over the FFT convolution method?
--
Bill
--
On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays no...@nohow.com wrote:
I was looking through the python source and noticed that long multiplication
is done using the Karatsuba method (O(~n^1.5)) rather than using FFTs O(~n
log n). I was wondering if there was a reason the Karatsuba method was
Am 06.07.2011 21:30, schrieb Billy Mays:
I was looking through the python source and noticed that long
multiplication is done using the Karatsuba method (O(~n^1.5)) rather
than using FFTs O(~n log n). I was wondering if there was a reason the
Karatsuba method was chosen over the FFT
On 07/06/2011 04:05 PM, Christian Heimes wrote:
Am 06.07.2011 21:30, schrieb Billy Mays:
I was looking through the python source and noticed that long
multiplication is done using the Karatsuba method (O(~n^1.5)) rather
than using FFTs O(~n log n). I was wondering if there was a reason the
On 07/06/2011 04:02 PM, Ian Kelly wrote:
On Wed, Jul 6, 2011 at 1:30 PM, Billy Maysno...@nohow.com wrote:
I was looking through the python source and noticed that long multiplication
is done using the Karatsuba method (O(~n^1.5)) rather than using FFTs O(~n
log n). I was wondering if there
On Wed, Jul 6, 2011 at 2:21 PM, Billy Mays no...@nohow.com wrote:
Side note: Are Numpy/Scipy the libraries you are referring to?
I was thinking more of gmpy or mpmath, but I'm not personally well
acquainted with any of them.
--
http://mail.python.org/mailman/listinfo/python-list
Am 06.07.2011 22:15, schrieb Billy Mays:
I believe it is possible to do FFTs without significant rounding error.
I know that the GIMPS's Prime95 does very large multiplications using
FFTs (I don't know if they use the integer based or double based
version). I also know they have guards
On Wed, 06 Jul 2011 22:05:52 +0200, Christian Heimes wrote:
On the other hand FFT are based on e, complex numbers or
trigonometric functions (=floats), which mean you'll get rounding errors.
It's possible to perform a DFT over any field. Schoenhage-Strassen uses
a DFT over a finite field
14 matches
Mail list logo
