File:Integer multiplication by FFT.svg
来自Wikimedia Commons
跳转到导航
跳转到搜索
此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 |
许可协议
[编辑]我,本作品著作权人,特此采用以下许可协议发表本作品:
本作品采用知识共享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上的用途