File:Integer multiplication by FFT.svg
出自Wikimedia Commons
跳至導覽
跳至搜尋
![File:Integer multiplication by FFT.svg](https://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Integer_multiplication_by_FFT.svg/666px-Integer_multiplication_by_FFT.svg.png?20111217103744)
此 SVG 檔案的 PNG 預覽的大小:666 × 580 像素。 其他解析度:276 × 240 像素 | 551 × 480 像素 | 882 × 768 像素 | 1,176 × 1,024 像素 | 2,352 × 2,048 像素。
原始檔案 (SVG 檔案,表面大小:666 × 580 像素,檔案大小:79 KB)
檔案資訊
結構化資料
說明
說明
添加單行說明來描述出檔案所代表的內容
![]() | This SVG image was uploaded in a graphics format such as GIF, PNG, JPEG, or SVG. However, it consists purely or largely of information which is better suited to representation in wikitext (possibly using MediaWiki's special syntax for tables, math, or music). This will make the information easier to edit, as well as make it accessible to users of screen readers and text-based browsers.
If possible, please replace any inclusions of this image in articles (noted under the “File links” header) with properly formatted wikitext. After doing so, please consider nominating this image for deletion. Deutsch ∙ English ∙ +/− | ![]() |
摘要
[編輯]描述Integer multiplication by FFT.svg |
English: A demonstration of an integer multiplication based on fast Fourier transforms (FFTs) using a number theoretic transform in the finite field of order 337, choosing 85 as an 8th root of unity (since the input vectors are of length 8). Base 10 is used (normally a power of 2 would used, but 10 is convenient for demonstration), and this technique is overkill for integers of this size (long multiplication would be superior). Because the inputs have 4 digits and the maximum product of two digits in base 10 is 92, the base was chosen as the first prime p greater than 4×92 = 324 where 8 is invertible in the integers modulo p (in this example any suitable base > 61, such as 73, would suffice, but we don't know that a priori). The computation at the top shows how the same acyclic convolution can be computed naively by "long multiplication without carrying," showing the relationship to multiplication. The computation in the lower right shows recombination/carrying of the result vector by (decimal) shifts and adds to obtain the final integer result. Note that all recursive multiplications are of smaller, 3-digit integers. Values are all accurate and were computed using the following Mathematica code:
NTT[x_, b_, r_] :=
Table[Mod[Sum[x[[n + 1]]*PowerMod[r, k*n, b], {n, 0, Length[x] - 1}],
b], {k, 0, Length[x] - 1}]
INTT[x_, b_, r_] := Block[{ninverse},
ninverse = PowerMod[Length[x], -1, b];
Table[Mod[
ninverse*
Sum[x[[n + 1]]*PowerMod[r, (Length[x] - n)*k, b], {n, 0,
Length[x] - 1}], b], {k, 0, Length[x] - 1}]]
x = {4, 3, 2, 1, 0, 0, 0, 0}; y = {8, 7, 6, 5, 0, 0, 0, 0}; b = 337; r = 85;
NTT[x, b, r]
NTT[y, b, r]
Mod[NTT[x, b, r]*NTT[y, b, r], b]
INTT[Mod[NTT[x, b, r]*NTT[y, b, r], b], b, r]
1234*5678
|
日期 | |
來源 | 自己的作品 |
作者 | Dcoetzee |
授權條款
[編輯]我,本作品的著作權持有者,決定用以下授權條款發佈本作品:
![]() ![]() |
此檔案在創用CC CC0 1.0 通用公有領域貢獻宣告之下分發。 |
在此宣告之下分發本作品者,已依據各國著作權法,在全世界放棄其對本作品所擁有的著作權及所有相關相似的法律權利,從而將本作品貢獻至公有領域。您可以複製、修改、分發和演示該作品,用於任何商業用途,所有這些都不需要請求授權。
http://creativecommons.org/publicdomain/zero/1.0/deed.enCC0Creative Commons Zero, Public Domain Dedicationfalsefalse |
檔案歷史
點選日期/時間以檢視該時間的檔案版本。
日期/時間 | 縮圖 | 尺寸 | 使用者 | 備註 | |
---|---|---|---|---|---|
目前 | 2011年12月17日 (六) 10:37 | ![]() | 666 × 580(79 KB) | Dcoetzee(留言 | 貢獻) |
無法覆蓋此檔案。
檔案用途
下列頁面有用到此檔案:
全域檔案使用狀況
以下其他 wiki 使用了這個檔案:
- de.wikipedia.org 的使用狀況
- en.wikipedia.org 的使用狀況
- ja.wikipedia.org 的使用狀況
- pl.wikipedia.org 的使用狀況
- zh.wikipedia.org 的使用狀況