File:Integer multiplication by FFT.svg
Aus Wikimedia Commons, dem freien Medienarchiv
Zur Navigation springen
Zur Suche springen
Größe der PNG-Vorschau dieser SVG-Datei: 666 × 580 Pixel. Weitere Auflösungen: 276 × 240 Pixel | 551 × 480 Pixel | 882 × 768 Pixel | 1.176 × 1.024 Pixel | 2.352 × 2.048 Pixel.
Originaldatei (SVG-Datei, Basisgröße: 666 × 580 Pixel, Dateigröße: 79 KB)
Dateiinformationen
Strukturierte Daten
Bildtexte
Dieses SVG Bild wurde hochgeladen in einem Grafikformat wie GIF, PNG, JPEG, oder SVG. Sie besteht jedoch ausschließlich oder größtenteils aus Informationen, die sich besser für die Darstellung in wikitext (möglicherweise unter Verwendung der speziellen MediaWiki-Syntax für Tabellen, Math oder Musik). So lassen sich die Informationen leichter bearbeiten und sind auch für Benutzer von Screenreadern und textbasierten Browsern barrierefrei.
Wenn möglich, ersetze bitte alle Einfügungen dieses Bildes in Artikeln (unter der Überschrift „Filelinks“) durch richtig formatierten Wikitext. Wenn du das getan hast, erwäge bitte, Dieses Bild zur Löschung vorzuschlagen. Deutsch ∙ English ∙ +/− |
Beschreibung
[Bearbeiten]BeschreibungInteger 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
|
Datum | |
Quelle | Eigenes Werk |
Urheber | Dcoetzee |
Lizenz
[Bearbeiten]Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:
Diese Datei wird unter der Creative-Commons-Lizenz „CC0 1.0 Verzicht auf das Copyright“ zur Verfügung gestellt. | |
Die Person, die das Werk mit diesem Dokument verbunden hat, übergibt dieses weltweit der Gemeinfreiheit, indem sie alle Urheberrechte und damit verbundenen weiteren Rechte – im Rahmen der jeweils geltenden gesetzlichen Bestimmungen – aufgibt. Das Werk kann – selbst für kommerzielle Zwecke – kopiert, modifiziert und weiterverteilt werden, ohne hierfür um Erlaubnis bitten zu müssen.
http://creativecommons.org/publicdomain/zero/1.0/deed.enCC0Creative Commons Zero, Public Domain Dedicationfalsefalse |
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 10:37, 17. Dez. 2011 | 666 × 580 (79 KB) | Dcoetzee (Diskussion | Beiträge) |
Du kannst diese Datei nicht überschreiben.
Dateiverwendung
Die folgende Seite verwendet diese Datei:
Globale Dateiverwendung
Die nachfolgenden anderen Wikis verwenden diese Datei:
- Verwendung auf de.wikipedia.org
- Verwendung auf en.wikipedia.org
- Verwendung auf ja.wikipedia.org
- Verwendung auf pl.wikipedia.org
- Verwendung auf zh.wikipedia.org