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 about the same magnitude. Looks like about 2.5-3 times the > > > precision loss of the Fast Hartley Transform: > > > > len = 1, min = 0, av = 0, max = 1, prec = 106 > > > len = 2, min = 0, av = 1, max = 3, prec = 106 > > > len = 3, min = 0, av = 2, max = 12, prec = 106 > > > len = 4, min = 0, av = 2, max = 8, prec = 106 > > > len = 6, min = 1, av = 4, max = 9, prec = 106 > > > len = 8, min = 2, av = 5, max = 12, prec = 106 > > > len = 11, min = 2, av = 5, max = 9, prec = 106 > > > len = 15, min = 4, av = 6, max = 12, prec = 106 > > > len = 20, min = 6, av = 8, max = 13, prec = 106 > > > len = 26, min = 6, av = 8, max = 12, prec = 106 > > > len = 34, min = 8, av = 11, max = 18, prec = 106 > > > len = 45, min = 9, av = 12, max = 20, prec = 106 > > > len = 59, min = 10, av = 12, max = 22, prec = 106 > > > len = 77, min = 10, av = 12, max = 17, prec = 106 > > > len = 101, min = 10, av = 13, max = 17, prec = 106 > > > len = 132, min = 13, av = 15, max = 20, prec = 106 > > > len = 172, min = 13, av = 16, max = 21, prec = 106 > > > len = 224, min = 14, av = 16, max = 22, prec = 106 > > > len = 292, min = 15, av = 17, max = 26, prec = 106 > > > len = 380, min = 16, av = 19, max = 27, prec = 106 > > > len = 494, min = 16, av = 18, max = 24, prec = 106 > > > len = 643, min = 16, av = 18, max = 24, prec = 106 > > > len = 836, min = 16, av = 18, max = 22, prec = 106 > > > len = 1087, min = 18, av = 20, max = 25, prec = 106 > > > len = 1414, min = 19, av = 21, max = 33, prec = 106 > > > len = 1839, min = 19, av = 21, max = 30, prec = 106 > > > len = 2391, min = 22, av = 24, max = 31, prec = 106 > > > len = 3109, min = 23, av = 25, max = 30, prec = 106 > > > len = 4042, min = 23, av = 25, max = 30, prec = 106 > > > len = 5255, min = 24, av = 26, max = 32, prec = 106 > > > len = 6832, min = 25, av = 27, max = 31, prec = 106 > > > > Bill. > > > > On Apr 30, 12:12 am, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > If the coefficients are allowed to vary in sign and vary wildly in the > > > > number of bits, then nothing will save you. Here are the figures for > > > > classical multiplication: > > > > > len = 1, min = 0, av = 18, max = 79, prec = 106 > > > > len = 2, min = 0, av = 23, max = 101, prec = 106 > > > > len = 3, min = 0, av = 19, max = 98, prec = 106 > > > > len = 4, min = 0, av = 16, max = 96, prec = 106 > > > > len = 6, min = 0, av = 21, max = 85, prec = 106 > > > > len = 8, min = 0, av = 26, max = 87, prec = 106 > > > > len = 11, min = 0, av = 24, max = 80, prec = 106 > > > > len = 15, min = 0, av = 15, max = 85, prec = 106 > > > > len = 20, min = 0, av = 25, max = 91, prec = 106 > > > > len = 26, min = 0, av = 16, max = 75, prec = 106 > > > > len = 34, min = 0, av = 20, max = 104, prec = 106 > > > > len = 45, min = 0, av = 20, max = 96, prec = 106 > > > > len = 59, min = 0, av = 16, max = 71, prec = 106 > > > > len = 77, min = 0, av = 26, max = 86, prec = 106 > > > > len = 101, min = 0, av = 24, max = 93, prec = 106 > > > > len = 132, min = 0, av = 10, max = 61, prec = 106 > > > > len = 172, min = 0, av = 19, max = 88, prec = 106 > > > > len = 224, min = 0, av = 21, max = 93, prec = 106 > > > > len = 292, min = 0, av = 16, max = 93, prec = 106 > > > > len = 380, min = 0, av = 23, max = 98, prec = 106 > > > > len = 494, min = 0, av = 25, max = 106, prec = 106 > > > > len = 643, min = 0, av = 31, max = 103, prec = 106 > > > > len = 836, min = 0, av = 28, max = 89, prec = 106 > > > > len = 1087, min = 0, av = 13, max = 90, prec = 106 > > > > len = 1414, min = 0, av = 22, max = 89, prec = 106 > > > > len = 1839, min = 0, av = 15, max = 83, prec = 106 > > > > len = 2391, min = 0, av = 21, max = 82, prec = 106 > > > > > And also for FHT: > > > > > len = 1, min = 0, av = 12, max = 79, prec = 106 > > > > len = 2, min = 0, av = 32, max = 108, prec = 106 > > > > len = 3, min = 0, av = 39, max = 123, prec = 106 > > > > len = 4, min = 0, av = 59, max = 145, prec = 106 > > > > len = 6, min = 10, av = 76, max = 136, prec = 106 > > > > len = 8, min = 2, av = 90, max = 175, prec = 106 > > > > len = 11, min = 5, av = 91, max = 162, prec = 106 > > > > len = 15, min = 29, av = 85, max = 160, prec = 106 > > > > len = 20, min = 14, av = 102, max = 186, prec = 106 > > > > len = 26, min = 20, av = 96, max = 162, prec = 106 > > > > len = 34, min = 11, av = 95, max = 191, prec = 106 > > > > len = 45, min = 0, av = 92, max = 189, prec = 106 > > > > len = 59, min = 10, av = 93, max = 160, prec = 106 > > > > len = 77, min = 40, av = 111, max = 179, prec = 106 > > > > len = 101, min = 44, av = 110, max = 181, prec = 106 > > > > len = 132, min = 47, av = 93, max = 156, prec = 106 > > > > len = 172, min = 19, av = 100, max = 184, prec = 106 > > > > len = 224, min = 38, av = 104, max = 186, prec = 106 > > > > len = 292, min = 13, av = 97, max = 187, prec = 106 > > > > len = 380, min = 31, av = 105, max = 192, prec = 106 > > > > len = 494, min = 27, av = 109, max = 198, prec = 106 > > > > len = 643, min = 47, av = 120, max = 198, prec = 106 > > > > len = 836, min = 13, av = 111, max = 185, prec = 106 > > > > len = 1087, min = 51, av = 96, max = 184, prec = 106 > > > > len = 1414, min = 6, av = 110, max = 184, prec = 106 > > > > len = 1839, min = 30, av = 97, max = 180, prec = 106 > > > > len = 2391, min = 30, av = 102, max = 177, prec = 106 > > > > > Clearly, in this situation, one wants to double the precision one is > > > > working at, at least. > > > > > Bill. > > > > > On Apr 29, 11:02 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > > > I wrote a little program to compute the "exact" product of two > > > > > polynomials with uniformly random unsigned coefficients < 2^prec for > > > > > some precision prec. I then compute the number of bits that are > > > > > correct in each coefficient and subtract from the > > ... > > 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
