Finally, the figures for karatsuba with signed coefficients that vary wildly. Hardly distinguishable from the figures for classical multiplication. With that I finish my little study. And in the inimitable words of Adam and Jamie (and with about as much "science" to back it up): MYTH BUSTED!!
So what have we learned: * The Sage timings for multiplication in RR[x] are not great, (please note however that my original timings of the classical algorithm in flint2 were incorrect due to a bug in my code; flint is actually only 10-20% faster for this - the times for the Hartley Transform were also misreported and should have been 9ms and 125ms for degree 1000 and 10000 multiplications, respectively, still considerably faster than Sage). * Karatsuba does not display noticeably worse behaviour than classical multiplication. Toom-Cook is also acceptable. * There is no such thing as Fateman multiplication. * The "Fateman multiplication" code is broken. * The Hartley transform is much better than Rader-Brennen. * For fixed point arithmetic the FFT techniques are fine, but for floating point they will suck when the "magnitude" of the coefficients varies greatly. * To answer the question asked by the OP, yes, there is a better algorithm; see the algorithm of Joris vdH * NO algorithm that we have looked at will deal with the kind of cancellation talked about in the docstring which started this whole thread off. If anyone is interested in adding to the module I started off in flint2 so that we can get some really good code into Sage for this sort of stuff, please let me know. Missing is code for "Fateman multiplication", Joris' algorithm, approximate GCD and lots of lower level stuff, like addition and subtraction of polynomials. len = 1, min = 0, av = 18, max = 79, prec = 106 len = 2, min = 0, av = 27, max = 101, prec = 106 len = 3, min = 0, av = 22, max = 98, prec = 106 len = 4, min = 0, av = 20, max = 96, prec = 106 len = 6, min = 0, av = 28, max = 85, prec = 106 len = 8, min = 0, av = 31, max = 87, prec = 106 len = 11, min = 0, av = 28, max = 80, prec = 106 len = 15, min = 0, av = 22, max = 85, prec = 106 len = 20, min = 0, av = 26, max = 91, prec = 106 len = 26, min = 0, av = 20, max = 75, prec = 106 len = 34, min = 0, av = 25, max = 104, prec = 106 len = 45, min = 0, av = 26, max = 96, prec = 106 len = 59, min = 0, av = 20, max = 71, prec = 106 len = 77, min = 0, av = 32, max = 86, prec = 106 len = 101, min = 0, av = 29, max = 93, prec = 106 len = 132, min = 0, av = 19, max = 61, prec = 106 len = 172, min = 0, av = 20, max = 88, prec = 106 len = 224, min = 0, av = 28, max = 93, prec = 106 len = 292, min = 0, av = 19, max = 93, prec = 106 len = 380, min = 0, av = 27, max = 98, prec = 106 len = 494, min = 0, av = 27, max = 106, prec = 106 len = 643, min = 0, av = 35, max = 103, prec = 106 len = 836, min = 0, av = 32, max = 89, prec = 106 len = 1087, min = 0, av = 16, max = 90, prec = 106 len = 1414, min = 0, av = 24, max = 89, prec = 106 len = 1839, min = 0, av = 20, max = 83, prec = 106 len = 2391, min = 0, av = 27, max = 82, prec = 106 len = 3109, min = 0, av = 31, max = 100, prec = 106 len = 4042, min = 0, av = 21, max = 104, prec = 106 len = 5255, min = 0, av = 24, max = 62, prec = 106 Bill. On May 1, 3:25 am, Bill Hart <goodwillh...@googlemail.com> wrote: > Now karatsuba for signed coefficients: > > len = 1, min = 0, av = 0, max = 0, prec = 106 > len = 2, min = 0, av = 1, max = 5, prec = 106 > len = 3, min = 0, av = 1, max = 4, prec = 106 > len = 4, min = 0, av = 0, max = 3, prec = 106 > len = 6, min = 0, av = 0, max = 6, prec = 106 > len = 8, min = 0, av = 1, max = 7, prec = 106 > len = 11, min = 0, av = 0, max = 4, prec = 106 > len = 15, min = 0, av = 1, max = 5, prec = 106 > len = 20, min = 0, av = 1, max = 5, prec = 106 > len = 26, min = 0, av = 1, max = 3, prec = 106 > len = 34, min = 0, av = 1, max = 4, prec = 106 > len = 45, min = 0, av = 0, max = 3, prec = 106 > len = 59, min = 0, av = 1, max = 5, prec = 106 > len = 77, min = 0, av = 0, max = 7, prec = 106 > len = 101, min = 0, av = 1, max = 5, prec = 106 > len = 132, min = 0, av = 1, max = 6, prec = 106 > len = 172, min = 0, av = 1, max = 5, prec = 106 > len = 224, min = 0, av = 0, max = 3, prec = 106 > len = 292, min = 0, av = 1, max = 7, prec = 106 > len = 380, min = 0, av = 0, max = 3, prec = 106 > len = 494, min = 0, av = 0, max = 5, prec = 106 > len = 643, min = 0, av = 0, max = 2, prec = 106 > len = 836, min = 0, av = 0, max = 3, prec = 106 > len = 1087, min = 0, av = 1, max = 2, prec = 106 > len = 1414, min = 0, av = 1, max = 5, prec = 106 > len = 1839, min = 0, av = 0, max = 3, prec = 106 > len = 2391, min = 0, av = 1, max = 5, prec = 106 > len = 3109, min = 0, av = 0, max = 4, prec = 106 > len = 4042, min = 0, av = 0, max = 4, prec = 106 > len = 5255, min = 0, av = 1, max = 8, prec = 106 > > Bill. > > On May 1, 3:19 am, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > And now for karatsuba. First for unsigned coefficients all about the > > same magnitude: > > > len = 1, min = 0, av = 0, max = 0, prec = 106 > > len = 2, min = 0, av = 1, max = 2, prec = 106 > > len = 3, min = 0, av = 1, max = 3, prec = 106 > > len = 4, min = 0, av = 1, max = 3, prec = 106 > > len = 6, min = 0, av = 0, max = 2, prec = 106 > > len = 8, min = 0, av = 0, max = 3, prec = 106 > > len = 11, min = 0, av = 0, max = 3, prec = 106 > > len = 15, min = 0, av = 0, max = 2, prec = 106 > > len = 20, min = 0, av = 1, max = 3, prec = 106 > > len = 26, min = 0, av = 0, max = 2, prec = 106 > > len = 34, min = 0, av = 0, max = 2, prec = 106 > > len = 45, min = 0, av = 0, max = 2, prec = 106 > > len = 59, min = 0, av = 1, max = 4, prec = 106 > > len = 77, min = 0, av = 1, max = 2, prec = 106 > > len = 101, min = 0, av = 1, max = 3, prec = 106 > > len = 132, min = 0, av = 0, max = 3, prec = 106 > > len = 172, min = 0, av = 1, max = 3, prec = 106 > > len = 224, min = 0, av = 0, max = 2, prec = 106 > > len = 292, min = 0, av = 1, max = 3, prec = 106 > > len = 380, min = 0, av = 0, max = 3, prec = 106 > > len = 494, min = 0, av = 0, max = 3, prec = 106 > > len = 643, min = 0, av = 1, max = 3, prec = 106 > > len = 836, min = 0, av = 1, max = 3, prec = 106 > > len = 1087, min = 0, av = 1, max = 2, prec = 106 > > len = 1414, min = 0, av = 1, max = 3, prec = 106 > > len = 1839, min = 0, av = 0, max = 2, prec = 106 > > len = 2391, min = 0, av = 0, max = 2, prec = 106 > > len = 3109, min = 0, av = 0, max = 2, prec = 106 > > len = 4042, min = 0, av = 1, max = 4, prec = 106 > > len = 5255, min = 0, av = 1, max = 3, prec = 106 > > > Bill. > > > On May 1, 3:13 am, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > Now for toom cook with wildly varying signed coefficients. A little > > > over twice the precision loss of the classical algorithm. Hardly what > > > I'd call an unmitigated disaster. Certainly very usable. > > > > len = 1, min = 0, av = 18, max = 79, prec = 106 > > > len = 2, min = 0, av = 27, max = 101, prec = 106 > > > len = 3, min = 0, av = 33, max = 98, prec = 106 > > > len = 4, min = 0, av = 20, max = 96, prec = 106 > > > len = 6, min = 0, av = 39, max = 91, prec = 106 > > > len = 8, min = 1, av = 45, max = 116, prec = 106 > > > len = 11, min = 0, av = 42, max = 145, prec = 106 > > > len = 15, min = 1, av = 28, max = 88, prec = 106 > > > len = 20, min = 0, av = 34, max = 105, prec = 106 > > > len = 26, min = 0, av = 28, max = 75, prec = 106 > > > len = 34, min = 0, av = 39, max = 104, prec = 106 > > > len = 45, min = 0, av = 35, max = 96, prec = 106 > > > len = 59, min = 0, av = 29, max = 82, prec = 106 > > > len = 77, min = 0, av = 40, max = 92, prec = 106 > > > len = 101, min = 0, av = 43, max = 102, prec = 106 > > > len = 132, min = 0, av = 34, max = 92, prec = 106 > > > len = 172, min = 0, av = 29, max = 163, prec = 106 > > > len = 224, min = 2, av = 37, max = 106, prec = 106 > > > len = 292, min = 0, av = 26, max = 99, prec = 106 > > > len = 380, min = 0, av = 35, max = 98, prec = 106 > > > len = 494, min = 0, av = 40, max = 106, prec = 106 > > > len = 643, min = 0, av = 45, max = 103, prec = 106 > > > len = 836, min = 0, av = 39, max = 101, prec = 106 > > > len = 1087, min = 0, av = 27, max = 94, prec = 106 > > > len = 1414, min = 0, av = 37, max = 94, prec = 106 > > > len = 1839, min = 1, av = 31, max = 100, prec = 106 > > > len = 2391, min = 0, av = 32, max = 85, prec = 106 > > > len = 3109, min = 1, av = 47, max = 139, prec = 106 > > > len = 4042, min = 0, av = 36, max = 107, prec = 106 > > > len = 5255, min = 0, av = 33, max = 79, prec = 106 > > > > Bill. > > > > On May 1, 3:07 am, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > Now toom cook with signed coefficients: > > > > > len = 1, min = 0, av = 0, max = 0, prec = 106 > > > > len = 2, min = 0, av = 1, max = 5, prec = 106 > > > > len = 3, min = 0, av = 2, max = 7, prec = 106 > > > > len = 4, min = 0, av = 0, max = 3, prec = 106 > > > > len = 6, min = 0, av = 2, max = 6, prec = 106 > > > > len = 8, min = 0, av = 2, max = 8, prec = 106 > > > > len = 11, min = 0, av = 2, max = 7, prec = 106 > > > > len = 15, min = 0, av = 2, max = 5, prec = 106 > > > > len = 20, min = 0, av = 2, max = 8, prec = 106 > > > > len = 26, min = 0, av = 2, max = 6, prec = 106 > > > > len = 34, min = 0, av = 2, max = 6, prec = 106 > > > > len = 45, min = 0, av = 1, max = 8, prec = 106 > > > > len = 59, min = 0, av = 2, max = 5, prec = 106 > > > > len = 77, min = 0, av = 2, max = 8, prec = 106 > > > > len = 101, min = 0, av = 2, max = 6, prec = 106 > > > > len = 132, min = 0, av = 2, max = 10, prec = 106 > > > > len = 172, min = 0, av = 2, max = 6, prec = 106 > > > > len = 224, min = 0, av = 2, max = 11, prec = 106 > > > > len = 292, min = 0, av = 2, max = 11, prec = 106 > > > > len = 380, min = 0, av = 2, max = 8, prec = 106 > > > > len = 494, min = 0, av = 2, max = 7, prec = 106 > > > > len = 643, min = 0, av = 1, max = 6, prec = 106 > > > > len = 836, min = 0, av = 2, max = 5, prec = 106 > > > > len = 1087, min = 0, av = 2, max = 5, prec = 106 > > > > len = 1414, min = 0, av = 2, max = 7, prec = 106 > > > > len = 1839, min = 0, av = 1, max = 6, prec = 106 > > > > len = 2391, min = 0, av = 1, max = 8, prec = 106 > > > > len = 3109, min = 0, av = 1, max = 8, prec = 106 > > > > len = 4042, min = 0, av = 1, max = 4, prec = 106 > > > > len = 5255, min = 0, av = 2, max = 6, prec = 106 > > > > > Bill. > > > > > On May 1, 3:01 am, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > > As promised, here with toom cook figures, first for unsigned > > > > > coefficients all about the same magnitude: > > > > > > len = 1, min = 0, av = 0, max = 0, prec = 106 > > > > > len = 2, min = 0, av = 1, max = 2, prec = 106 > > > > > len = 3, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 4, min = 0, av = 1, max = 3, prec = 106 > > > > > len = 6, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 8, min = 1, av = 2, max = 6, prec = 106 > > > > > len = 11, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 15, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 20, min = 0, av = 2, max = 5, prec = 106 > > > > > len = 26, min = 0, av = 1, max = 4, prec = 106 > > > > > len = 34, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 45, min = 0, av = 2, max = 4, prec = 106 > > > > > len = 59, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 77, min = 0, av = 2, max = 5, prec = 106 > > > > > len = 101, min = 0, av = 2, max = 4, prec = 106 > > > > > len = 132, min = 0, av = 2, max = 4, prec = 106 > > > > > len = 172, min = 0, av = 2, max = 7, prec = 106 > > > > > len = 224, min = 0, av = 2, max = 7, prec = 106 > > > > > len = 292, min = 0, av = 2, max = 5, prec = 106 > > > > > len = 380, min = 0, av = 2, max = 8, prec = 106 > > > > > len = 494, min = 0, av = 2, max = 4, prec = 106 > > > > > len = 643, min = 0, av = 2, max = 5, prec = 106 > > > > > len = 836, min = 0, av = 2, max = 4, prec = 106 > > > > > len = 1087, min = 0, av = 2, max = 5, prec = 106 > > > > > len = 1414, min = 0, av = 2, max = 7, prec = 106 > > > > > len = 1839, min = 0, av = 2, max = 6, prec = 106 > > > > > len = 2391, min = 0, av = 2, max = 5, prec = 106 > > > > > len = 3109, min = 0, av = 1, max = 4, prec = 106 > > > > > len = 4042, min = 0, av = 2, max = 7, prec = 106 > > > > > len = 5255, min = 0, av = 2, max = 5, prec = 106 > > > > > > Bill. > > > > > > On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > > > And finally, the figures for Rader-Brennan for signed coefficients > > > > > > whose magnitudes also vary wildly: as with FHT, on average, no > > > > > > usable > > > > > > information results. No FFT algorithm will be of use in that > > > > > > situation. Joris vdH's algorithm is your only hope. > > > > > > > After dinner, figures for Karatsuba and Toom Cook. I think there may > > > > > > be a surprise in store for us there.... > > > > > > > len = 1, min = 0, av = 5, max = 74, prec = 106 > > > > > > len = 2, min = 5, av = 36, max = 106, prec = 106 > > > > > > len = 3, min = 1, av = 46, max = 124, prec = 106 > > > > > > len = 4, min = 2, av = 63, max = 170, prec = 106 > > > > > > len = 6, min = 13, av = 79, max = 140, prec = 106 > > > > > > len = 8, min = 4, av = 95, max = 180, prec = 106 > > > > > > len = 11, min = 8, av = 95, max = 164, prec = 106 > > > > > > len = 15, min = 31, av = 89, max = 163, prec = 106 > > > > > > len = 20, min = 17, av = 107, max = 191, prec = 106 > > > > > > len = 26, min = 26, av = 101, max = 168, prec = 106 > > ... > > read more » -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
