On Jan 14, 7:07 pm, rjf <[email protected]> wrote: > For a discussion of practical fast polynomial multiplication, > seehttp://www.eecs.berkeley.edu/~fateman/papers/dumbisfast.pdf > and also the first reference in that paper. > (As well as other references). > The code in GMP is likely to be well thought out.
Thanks, sparse detection and multiplication in this case is certainly a pending subject. > You are probably making a major mistake setting the cutoff at > zero, if you care about polynomials of only modest degree > (like 50), and are doing many such operations. You are probably right, the number of base rings that will not gain a benefit from a nonzero threshold is quite small. The best would be to identify most of such rings and act accordingly. > If you are doing operations (or timing operations) solely > on polynomials with 10,000 coefficients, you should consider > if your base field supports some kind of discrete fast-Fourier > transform. I have an implementation of a 2-radix FFT as a proof of concept for characteristic zero fields, but it starts to be better at around degree 8000, so it is not around my priorities. I know Cook-Toom but I have never tried to implement them > If the only reason you are doing this is speed, the difference > between 3.4 seconds and 2.6 seconds is hardly worth a week's > programming effort. If it is to establish a really good practical > algorithm, you have to do some reading. You misread the numbers, the gain is from 3.4 seconds to 0.2. ten times faster with my code. But what I wanted to point out is that, for a pair of dense polynomials of degrees 4000, 1500, current karatsuba code is three times as slow as schoolbook method. This is not acceptable. > > The new code, for f is of degree m-1 and g of degree n-1 with m<n, > > consider g as: > > > g0 + x^m*g1 + x^(2*m)g2 + ... + x^(q*m)*gq > > > Compute the products f*gi recursively with karatsuba and reconstruct > > f*g. > > Why use karatsuba? If m is small, use whatever is fastest. > If the sizes differ so substantially,use another algorithm entirely. In this case, if the size of m is below the threshold, it would use schoolbook method. If two polynomials of size m are in the range of karatsuba method, the number of operations of this approach is of order O (m^0.59 n), grows linearly in n. Looks acceptable to me. > If you use an FFT-based algorithm, you can compute a transform of f > just once. This is a good idea. > If f is small enough, the "schoolboy" algorithm is faster. > Also, there are many alternatives between karatsuba and fft (Toom or > Cook-Toom) > algorithms. > > > I took the idea from some documentation of an old implementation of > > gmp. > > Why not look at the latest GMP? Yes, I have to look at it. Bests Luis -- To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
