Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Large number multiplication

Reply
Thread Tools

Large number multiplication

 
 
casevh
Guest
Posts: n/a
 
      07-07-2011
On Jul 7, 1:30*am, Ulrich Eckhardt <(E-Mail Removed)>
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
> >> numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
> >> """

>
> >> I think most Python users are probably not working with numbers that
> >> large, and if they are, they are probably using specialized numerical
> >> libraries anyway, so there would be little benefit in implementing it
> >> in core.

>
> > You are right that not many people would gain significant use of it.

>
> 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.
>
> > The reason I ask is because convolution has a better (best ?) complexity
> > class than the current multiplication algorithm.

>
> The "asymptotic complexity" of algorithms (I guess that's what you mean) is
> concerned with large up to infinite n elements in operations. The claim
> there always excludes any number of elements below n_0, where the complexity
> might be different, even though that is usually not repeatedly mentioned.In
> other words, lower complexity does not mean that something runs faster, only
> that for large enough n it runs faster. If you never realistically reach
> that limit, you can't reap those benefits.
>
> 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 was more interested in finding previous discussion (if any) on why
> > Karatsuba was chosen, not so much as trying to alter the current
> > multiplication implementation.

>
> I would hope that such design decisions are documented in code or at least
> referenced from there. Otherwise the code is impossible to understand and
> argue about.
>
> Cheers!
>
> Uli
>
> --
> Domino Laser GmbH
> Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932- Hide quoted text -
>
> - Show quoted text -


A quick search on the Python issue tracker (bugs.python.org) yields
the following issues:

http://bugs.python.org/issue560379

http://bugs.python.org/issue4258

The issues also refer to discussion threads on the python-dev mailing
list.

casevh
 
Reply With Quote
 
 
 
 
Mark Dickinson
Guest
Posts: n/a
 
      07-08-2011
On Jul 7, 9:30*am, Ulrich Eckhardt <(E-Mail Removed)>
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 such a patch would be accepted. Indeed,
Tim Peters has been heard to mention that if he were to do it all
again, he probably wouldn't even have implemented Karatsuba [1].
Asymptotically fast integer multiplication is a specialist need that's
already available in 3rd-party Python libraries (gmpy). IMO, it's not
appropriate to include it in a general-purpose programming language,
and the burden of maintaining such code would outweigh the benefits.

One thing that has been considered in the past is making it possible
to use GMP directly for Python's implementation of long integers; see
Victor Stinner's efforts in this direction [2]. Licensing concerns,
and the fact that Python's implementation is faster for small
integers, ended up killing this issue.

[1] http://mail.python.org/pipermail/pyt...er/083355.html
[2] http://bugs.python.org/issue1814

--
Mark
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Source of term "multiplication" in matrix multiplication William Hughes C Programming 13 03-15-2010 02:04 PM
OT: Number Nine, Number Nine, Number Nine Frisbee® MCSE 37 09-26-2005 04:06 PM
need help with large int multiplication and division akickdoe22@hotmail.com C++ 1 01-21-2005 02:46 AM
Re: long number multiplication Terry Reedy Python 1 12-06-2004 03:02 PM
long number multiplication I.V. Aprameya Rao Python 3 12-06-2004 11:30 AM



Advertisments