Multiplication algorithm: Difference between revisions

Revision as of 14:23, 29 May 2014

Revision as of 23:02, 9 July 2014

Line 386:

Using [[number-theoretic transform]]s instead of [[discrete Fourier transform]]s avoids [[rounding error]] problems by using modular arithmetic instead of [[floating point|floating-point]] arithmetic. In order to apply the factoring which enables the FFT to work, the length of the transform must be factorable to small primes, and must be a factor of ''N''-1, where ''N'' is the field size. In particular, calculation using a Galois Field GF(''k''²), where ''k'' is a [[Mersenne Prime]], allows the use of a transform sized to a power of 2; e.g. ''k'' = 2³¹-1 supports transform sizes up to 2³².

===Linear time multiplication===

Knuth<ref>{{Citation | last1=Knuth | first1=Donald E. | author1-link=Donald Knuth | title=The Art of Computer Programming volume 2: Seminumerical algorithms | publisher=[[Addison-Wesley]] | year=1997 | pages=311}}

</ref> describes computational models in which two n-bit numbers can be multiplied in linear time. The most realistic of these requires that any memory ___location can be accessed in constant time (the so-called RAM model). The approach is to use the FFT based method described above, packing log n bits into each coefficient of the polynomials and doing all computations with 6 log ''n'' bits of accuracy. The time complexity is now O( ''nM'' ) where M is the time needed to multiply two log ''n'' - bit numbers. By precomputing a linear size multiplication lookup table of all pairs of numbers of (log ''n'')/2 bits, M is simply the time needed to perform a constant number of table lookups. If one assumes this takes constant time per table lookup as is true in the unit-cost word RAM model, then the overall algorithm is linear time.

== Lower bounds ==