Мой сайт

-->Главная » » Цитата про умножение. Компьютер и умножение.

02:36

Цитата про умножение. Компьютер и умножение.

Гм.. Но там реализация на double как то это странно. Да и fft_rev отсутствует. Может кто видел более целочисленную реализацию? Мне что то найти не удалось.

UPD: Ага нашел таки корректный анализ сложности - то что вызывало эти Гм..с моей стороны - точность или размер коэффициентов. Наслаждайтесь:

In fact, the time complexity of multiplication with FFT is a little bigger than n log(n).

Let us be more precise. To multiply two numbers of N digits, we write them in a base B which contains k digits (say B = 10k), thus giving a number of coefficients equal to n @ N/k. The discussion above tells us that to multiply those two numbers, FFT permits to perform O(n log (n)) operations on basic numbers (basic numbers express coefficients in the base B, they are usually basic numerical data types like double in C of Fortran). Because of the numerical error bound, these basic numbers should be precise enough to represent integers up to $6n^2B^2\log(n)$ (for example, working in double precision, the base B should be choosen small enough so that the error bound is not too large... and this is not even possible if n is too large). Thus the number of digits of these basic numbers should be of the order of $\log(B)+\log(n)$ . As a consequence, the basic operations on these numbers has cost $O((\log(B)+\log(n))^2)$ and the final cost is $O( n \log(n) (\log(B) + \log(n))^2)$ . The base B is choosen so that $k = \log_{10}(B)$ is of the same order than log(n), and finally, multiplying those two numbers of N @ kn digits have cost $O( n \log(n)^3 ) = O( N \log(N)^2)$ .

Thus the cost of Strassen multiplication (this is the name of the floating-FFT we presented) to multiply numbers of N digits is $O(N\log^2(N))$ . If the Strassen mulplication is also used to compute the operations on the basic numbers (one recursive level), the cost reduces to $O(N\log(N)\log\log^2(N))$ . The best bound is obtained with complete recursive version and is $O(N\log(N) \log\log(N) \log\log\log(N))$ . The use of the Number Theoretic Transform (see above) leads to the same bounds.

The lowest known theoritical bound is obtained with the Schцnhage multiplication, which generalizes the process by working in finite rings, and is $O(N \log(N) \log\log(N))$ (see Multiplication en le Lisp for a description of Schцnhage multiplication). The Nussbaumer multiplication also reaches this complexity (see [2] for an explanation of various large-multiplication routines). Notice that on actual implementations, the Strassen approach is the fastest, even if asymptotically slightly inferior.

ссылка: http://numbers.computation.free.fr/Constan...rithms/fft.html

Резюме - если мы умножаем реально БОЛЬШИЕ числа то умножение будет стоить по БПФ $O(N\log(N) \log\log(N) \log\log\log(N))$ , а наилучший алгоритм $O(N \log(N) \log\log(N))$ за счет работы в конечных кольцах. По поводу колец надо разбираться дальше похоже)

Ключевое слово NTT - умножение производится над кольцом простых чисел - на самом деле производится несколько FFT по разным простым модулям потом результат собирается обратно по китайской теореме об остатках - как ни странно практическая реализация есть в исходниках - ребяты вычисляли число пи - с точностью до ярда цифр. Кто найдет исходниик - бросьте сюда плиз!