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 > > > > > len = 34, min = 22, av = 102, max = 199, prec = 106 > > > > > len = 45, min = 9, av = 100, max = 195, prec = 106 > > > > > len = 59, min = 19, av = 101, max = 167, prec = 106 > > > > > len = 77, min = 54, av = 119, max = 187, prec = 106 > > > > > len = 101, min = 46, av = 117, max = 190, prec = 106 > > > > > len = 132, min = 58, av = 103, max = 165, prec = 106 > > > > > len = 172, min = 27, av = 110, max = 199, prec = 106 > > > > > len = 224, min = 47, av = 113, max = 194, prec = 106 > > > > > len = 292, min = 26, av = 110, max = 203, prec = 106 > > > > > len = 380, min = 46, av = 118, max = 203, prec = 106 > > > > > len = 494, min = 38, av = 121, max = 214, prec = 106 > > > > > len = 643, min = 60, av = 132, max = 207, prec = 106 > > > > > len = 836, min = 24, av = 123, max = 198, prec = 106 > > > > > len = 1087, min = 62, av = 111, max = 201, prec = 106 > > > > > len = 1414, min = 27, av = 125, max = 199, prec = 106 > > > > > len = 1839, min = 44, av = 111, max = 194, prec = 106 > > > > > len = 2391, min = 50, av = 120, max = 192, prec = 106 > > > > > > Bill. > > > > > > On Apr 30, 8:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > > > I installed Andreas Enge's mpfrcx package: > > > > > > >http://www.multiprecision.org/index.php?prog=mpfrcx&page=html > > > > > > > which just worked for me. > > > > > > > I took a closer look and the Rader-Brennan FFT is a complex FFT > > > > > > taking > > > > > > mpcx polynomials as input. When multiplying polynomials over the > > > > > > reals, it simply converts to complex polynomials and uses the > > > > > > complex > > > > > > RB FFT. > > > > > > > Anyhow, this wrapper was very nice for me as it just plugged > > > > > > straight > > > > > > into my existing profiling code with no modifications whatsoever!! > > > > > > That sort of thing almost never happens. > > > > > > > Anyhow, here is the precision loss figures for unsigned coefficients > > > > > > all of > > ... > > 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
