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 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 -- http://mail.python.org/mailman/listinfo/python-list
