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キロバイト)
ファイル情報
構造化データ
キャプション
キャプション
このファイルの内容を1行で記述してください
![]() | 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キロバイト) | Dcoetzee (トーク | 投稿記録) |
このファイルは上書きできません。
ファイルの使用状況
以下のページがこのファイルを使用しています:
グローバルなファイル使用状況
以下に挙げる他のウィキがこの画像を使っています:
- de.wikipedia.org での使用状況
- en.wikipedia.org での使用状況
- ja.wikipedia.org での使用状況
- pl.wikipedia.org での使用状況
- zh.wikipedia.org での使用状況