On Jul 7, 9:30 am, Ulrich Eckhardt
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,
> too.
I'm far from sure that
On Jul 7, 1:30 am, Ulrich Eckhardt
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 for
> >> numbe
Hi,
Billy Mays wrote:
>
>> On 07/06/2011 04:02 PM, Ian Kelly wrote:
>> > On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays 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
>
On Thu, Jul 7, 2011 at 9:49 AM, Ian Kelly wrote:
> On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
> 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
On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
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
specific threshold. Adding Sch
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
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 (int
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 guard
On Wed, Jul 6, 2011 at 2:21 PM, Billy Mays 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
On 07/06/2011 04:02 PM, Ian Kelly wrote:
On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays 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 K
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
Kara
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 con
On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays 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
> chosen over the
13 matches
Mail list logo
