| dbo:abstract
|
- Der Schönhage-Strassen-Algorithmus ist ein Algorithmus zur Multiplikation zweier n-stelliger ganzer Zahlen. Er wurde 1971 von Arnold Schönhage und Volker Strassen entwickelt. Der Algorithmus basiert auf einer sehr schnellen Variante der diskreten schnellen Fourier-Transformation sowie einem geschickten Wechsel zwischen der Restklassen- und der zyklischen Arithmetik in endlichen Zahlenringen. Der Schönhage-Strassen-Algorithmus terminiert in (siehe Landau-Notation), wenn als Effizienzmaß die Bitkomplexität auf mehrbändigen Turingmaschinen, also die maximale Laufzeit des Algorithmus gemessen als benötigte Bitoperationen in Abhängigkeit von der Bitlänge der Eingabegrößen gewählt wird.Diese Komplexität stellt eine Verbesserung sowohl gegenüber dem naiven aus der Schule bekannten Algorithmus der Laufzeit als auch gegenüber dem 1962 entwickelten Karatsuba-Algorithmus mit einer Laufzeit von sowie dessen verbesserter Variante, dem Toom-Cook-Algorithmus mit Laufzeit dar. Der Schönhage-Strassen-Algorithmus war von 1971 bis 2007 der effizienteste bekannte Algorithmus zur Multiplikation großer Zahlen; 2007 veröffentlichte eine Weiterentwicklung des Algorithmus mit der noch niedrigeren asymptotischen Komplexität , wobei der iterierte Logarithmus von n ist.Durch Optimierungen des Algorithmus von Fürer erreichten David Harvey, Joris van der Hoeven und Grégoire Lecerf eine weitere Verbesserung der asymptotischen Laufzeit auf . (de)
- El Algoritmo de Schonhage-Strassen es un algoritmo que consiste en la multiplicación de matrices. Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes. (es)
- L’algorithme de Schönhage-Strassen est un algorithme de multiplication de grands entiers par transformée de Fourier rapide publié en 1971 par Arnold Schönhage et Volker Strassen. Dans le modèle de complexité courant des machines de Turing à plusieurs bandes, il permet de multiplier deux entiers de bits en opérations. Jusqu'en 2007 et la publication de l'algorithme de Fürer, cela en faisait la méthode asymptotiquement la plus rapide connue pour la multiplication d'entiers. (fr)
- The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. The run-time bit complexity is, in big O notation, for two n-digit numbers. The algorithm uses recursive fast Fourier transforms in rings with 2n+1 elements, a specific type of number theoretic transform. The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007, when a new method, Fürer's algorithm, was announced with lower asymptotic complexity, and is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library. The algorithm does not adapt for polynomials over finite fields though. The current best multiplication algorithm in terms of asymptotic complexity is by David Harvey and Joris van der Hoeven, which gives complexity. However, this improvement is too insignificant to be seen in integer sizes seen in practice (see Galactic algorithms) and implementations do not exist. In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2215 to 2217 (10,000 to 40,000 decimal digits). The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (33,000 to 150,000 decimal digits), depending on architecture. There is a Java implementation of Schönhage–Strassen which uses it above 74,000 decimal digits. Applications of the Schönhage–Strassen algorithm include mathematical empiricism, such as the Great Internet Mersenne Prime Search and computing approximations of π, as well as practical applications such as Kronecker substitution, in which multiplication of polynomials with integer coefficients can be efficiently reduced to large integer multiplication; this is used in practice by GMP-ECM for Lenstra elliptic curve factorization. (en)
- ショーンハーゲ・ストラッセン法は、大きな整数の掛け算を高速に計算できるである。1971年にとフォルカー・シュトラッセンによって発見された。2進法で n 桁の整数同士の掛け算の時間計算量はランダウの記号を用いて である。このアルゴリズムではの1つである 2n+1個の要素を持つ整数環での高速フーリエ変換を用いる。 ショーンハーゲ・ストラッセン法は、発見された1971年から、が発見される2007年まで十分大きな整数の掛け算の最速アルゴリズムであった。しかし、ショーンハーゲ・ストラッセン法よりフューラーのアルゴリズムの性能が上回るのは天文学的に大きな整数同士の掛け算に限るため、フューラーのアルゴリズムはほとんど実用されていない。 実際には、ショーンハーゲ・ストラッセン法がカラツバ法やのような従来の手法より性能が上回り始めるのは、2215 - 2217（10進法で10 000 - 40 000桁）同士の掛け算である。GNU Multi-Precision Libraryはアーキテクチャに依存するが 、64ビット演算において少なくとも1728 - 7808ワード（10進法で33 000 - 150 000桁）の大きさの計算において初めてショーンハーゲ・ストラッセン法を用いる。10進法で74 000桁以上においてショーンハーゲ・ストラッセン法を用いるJavaの実装も存在する。 ショーンハーゲ・ストラッセン法の応用には、GIMPSや円周率の近似計算などの数学的経験主義や、整数係数多項式の乗算を整数の掛け算に帰着して効率的に行うクロネッカー置換などの実用的な応用がある。これは楕円曲線法のためにGMP-ECMで用いられている。 (ja)
- L'algoritmo di Schönhage-Strassen è un algoritmo di moltiplicazione rapido per grandi numeri interi, sviluppato da e nel 1971. La sua complessità, nella notazione O-grande, è O(n log n log log n). L'algoritmo usa ricorsivi Trasformate di Fourier veloci negli anelli con 22n + 1 elementi. L'algoritmo di Schönhage-Strassen era asintoticamente il più veloce metodo di moltiplicazione conosciuto tra il 1971 ed il 2007, finché non è stato annunciato l' che ha complessità asintotica minore, però al momento raggiunge il vantaggio solo per numeri astronomicamente grandi e non è utilizzato praticamente. In pratica, l'algoritmo di Schönhage-Strassen è più veloce di metodi vecchi come quello di Karatsuba e di Toom-Cook per i numeri da 2215 a 2217 (10.000 a 40.000 cifre decimali). La lo utilizza per valori di almeno 1728 a 7808 word a 64 bit (33.000 a 150.000 cifre decimali), a seconda dell'architettura. C'è una realizzazione in Java dell'algoritmo di Schönhage-Strassen che lo usa per i numeri con più di 74.000 cifre decimali. Applicazioni dell'algoritmo di Schönhage-Strassen includono empirismo matematico come il GIMPS e calcolo di π, così come applicazioni pratiche quali la in cui la moltiplicazione di polinomi con coefficienti interi può essere efficientemente ridotta alla moltiplicazione di grandi numeri interi. (it)
- 쇤하게-슈트라센 알고리즘(Schönhage–Strassen algorithm)은 두 정수를 매우 빠르게 곱할 수 있는 알고리즘으로, 자리 정수 두 개를 시간에 곱할 수 있다. 이 알고리즘은 1971년에 등장하여 카라추바 알고리즘과 톰-쿡 알고리즘을 능가하였고, 2007년에 퓌러 알고리즘이 등장하기 전까지 두 개의 정수를 곱할 때 쓰이던 가장 빠른 알고리즘이었다. 고속 푸리에 변환을 재귀적으로 사용하며, 여기에 약간의 기술을 추가하여 두 수를 곱하는 알고리즘이다. (ko)
- O Algoritmo Schönhage-Strassen ou Método de Multiplicação Schönhage-Strassen é um método rápido de multiplicação de números inteiros grandes. O método por trás do algoritmo consiste na Transformação Rápida de Fourier ou Transformada Rápida de Fourier, abreviada e conhecida pelo inglês como FFT (Fast Fourier Transform). Criada por Volker Schönhage e Arnold Strassen em 1971, este método requer operações aritméticas e operações de bits de ordem assintótica, onde n é o número de dígitos no produto. Na realidade, o método Schönhage-Strassen é um método de multiplicação de polinômios em uma variável. Ele representa, no algoritmo de multiplicação, os números como polinômios na base do próprio sistema de numeração; e após receber o resultado, faz a transferência por entre as fileiras. Por exemplo, para multiplicar 147 e 258 (em decimal), serão realizadas as seguintes operações:
* Representação de 147 como x²+4x+7; e 258 como 2x²+5x+8, onde x = 10.
* Multiplique polinômios x²+4x+7 e 2x²+5x+8 usando a transformada rápida de Fourier. Obtenha o produto dos polinômios 2x4+13x³+42x²+67x+56.
* Ao fazer transferências entre as fileiras, temos 3x4+7x³+9x²+2x+6, ou seja, 37.926. No caso do sistema de numeração ser de base 2 (sistema binário), podem ser feitas multiplicações em módulo, utilizando, para o módulo um, número de Fermat . O Método Schönhage - Strassen foi considerado o método para multiplicações mais rápido em comparação de velocidades assintóticas entre 1971 e 2007, até que foi encontrado um novo método de estimativa de complexidade de multiplicação. Na prática, o método Schönhage - Strassen começa a extrapolar o tempo de outros métodos, tais como Karatsuba e Toom-Cook (uma espécie de generalização do método de Karatsuba) para inteiros de magnitude no intervalo a (de 10.000 a 40.000 dígitos decimais) (pt)
- Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует ) битовых операций, где — количество двоичных цифр в произведении. Изобретён Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году. Фактически является методом умножения многочленов от одной переменной, превращается в алгоритм умножения чисел, если эти числа представить как многочлены от основы системы счисления, а после получения результата сделать переносы через разряды. Например, для перемножения 157 и 171 (в десятичной системе счисления) выполняются следующие операции:
* представляется как , а — как , где ;
* перемножаются многочлены и с помощью быстрого преобразования Фурье, результат — ;
* применяются переносы через разряды: , то есть . Также в алгоритме можно умножать по модулю чисел Ферма , если применять двоичную систему счисления. Метод считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был изобретён алгоритм Фюрера с лучшей оценкой сложности. На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка — (от 10 000 до 40 000 десятичных знаков). (ru)
- 頌哈吉-施特拉森演算法（英語：Schönhage–Strassen algorithm）是漸近快速的大整数乘法算法。是由和沃爾克·施特拉森在1971年發明。若針對二個n位元的整數，其運行的，若以大O符号表示，是。演算法使用在有2n+1個元素的环上的迭代快速傅里叶变换，這是一種特別的數論轉換。 頌哈吉-施特拉森演算法是1971年至2007年之間，漸近最快的乘法演算法，2007年時有一個新的乘法演算法，其漸近複雜度較低，不過Fürer演算法只有在大到天文數字的程度時，其速度才會比頌哈吉-施特拉森演算法快，實務上不會使用Fürer演算法（參考银河式算法）。 在實務上，當數字大於2215至2217（十進制下的10,000到40,000位數）時，頌哈吉-施特拉森演算法的速度會比較早期的卡拉楚巴算法和图姆-库克算法要快。GNU多重精度运算库用這個演算法計算至少1728至7808個64位元字節的數值（十進制下的33,000至150,000位數），依硬體架構而定，有一個用Java實現的頌哈吉-施特拉森演算法，可以計算十進位超過74,000位數。 頌哈吉-施特拉森演算法的應用包括数学哲学（例如互联网梅森素数大搜索以及計算圆周率近似值），實務的應用包括，其中將整係數多項式的乘法有效的簡化為大數的乘法，GMP-ECM中用此算法來計算。 (zh)
|
| rdfs:comment
|
- El Algoritmo de Schonhage-Strassen es un algoritmo que consiste en la multiplicación de matrices. Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes. (es)
- L’algorithme de Schönhage-Strassen est un algorithme de multiplication de grands entiers par transformée de Fourier rapide publié en 1971 par Arnold Schönhage et Volker Strassen. Dans le modèle de complexité courant des machines de Turing à plusieurs bandes, il permet de multiplier deux entiers de bits en opérations. Jusqu'en 2007 et la publication de l'algorithme de Fürer, cela en faisait la méthode asymptotiquement la plus rapide connue pour la multiplication d'entiers. (fr)
- 쇤하게-슈트라센 알고리즘(Schönhage–Strassen algorithm)은 두 정수를 매우 빠르게 곱할 수 있는 알고리즘으로, 자리 정수 두 개를 시간에 곱할 수 있다. 이 알고리즘은 1971년에 등장하여 카라추바 알고리즘과 톰-쿡 알고리즘을 능가하였고, 2007년에 퓌러 알고리즘이 등장하기 전까지 두 개의 정수를 곱할 때 쓰이던 가장 빠른 알고리즘이었다. 고속 푸리에 변환을 재귀적으로 사용하며, 여기에 약간의 기술을 추가하여 두 수를 곱하는 알고리즘이다. (ko)
- 頌哈吉-施特拉森演算法（英語：Schönhage–Strassen algorithm）是漸近快速的大整数乘法算法。是由和沃爾克·施特拉森在1971年發明。若針對二個n位元的整數，其運行的，若以大O符号表示，是。演算法使用在有2n+1個元素的环上的迭代快速傅里叶变换，這是一種特別的數論轉換。 頌哈吉-施特拉森演算法是1971年至2007年之間，漸近最快的乘法演算法，2007年時有一個新的乘法演算法，其漸近複雜度較低，不過Fürer演算法只有在大到天文數字的程度時，其速度才會比頌哈吉-施特拉森演算法快，實務上不會使用Fürer演算法（參考银河式算法）。 在實務上，當數字大於2215至2217（十進制下的10,000到40,000位數）時，頌哈吉-施特拉森演算法的速度會比較早期的卡拉楚巴算法和图姆-库克算法要快。GNU多重精度运算库用這個演算法計算至少1728至7808個64位元字節的數值（十進制下的33,000至150,000位數），依硬體架構而定，有一個用Java實現的頌哈吉-施特拉森演算法，可以計算十進位超過74,000位數。 頌哈吉-施特拉森演算法的應用包括数学哲学（例如互联网梅森素数大搜索以及計算圆周率近似值），實務的應用包括，其中將整係數多項式的乘法有效的簡化為大數的乘法，GMP-ECM中用此算法來計算。 (zh)
- Der Schönhage-Strassen-Algorithmus ist ein Algorithmus zur Multiplikation zweier n-stelliger ganzer Zahlen. Er wurde 1971 von Arnold Schönhage und Volker Strassen entwickelt. Der Algorithmus basiert auf einer sehr schnellen Variante der diskreten schnellen Fourier-Transformation sowie einem geschickten Wechsel zwischen der Restklassen- und der zyklischen Arithmetik in endlichen Zahlenringen. (de)
- The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. The run-time bit complexity is, in big O notation, for two n-digit numbers. The algorithm uses recursive fast Fourier transforms in rings with 2n+1 elements, a specific type of number theoretic transform. (en)
- L'algoritmo di Schönhage-Strassen è un algoritmo di moltiplicazione rapido per grandi numeri interi, sviluppato da e nel 1971. La sua complessità, nella notazione O-grande, è O(n log n log log n). L'algoritmo usa ricorsivi Trasformate di Fourier veloci negli anelli con 22n + 1 elementi. Applicazioni dell'algoritmo di Schönhage-Strassen includono empirismo matematico come il GIMPS e calcolo di π, così come applicazioni pratiche quali la in cui la moltiplicazione di polinomi con coefficienti interi può essere efficientemente ridotta alla moltiplicazione di grandi numeri interi. (it)
- ショーンハーゲ・ストラッセン法は、大きな整数の掛け算を高速に計算できるである。1971年にとフォルカー・シュトラッセンによって発見された。2進法で n 桁の整数同士の掛け算の時間計算量はランダウの記号を用いて である。このアルゴリズムではの1つである 2n+1個の要素を持つ整数環での高速フーリエ変換を用いる。 ショーンハーゲ・ストラッセン法は、発見された1971年から、が発見される2007年まで十分大きな整数の掛け算の最速アルゴリズムであった。しかし、ショーンハーゲ・ストラッセン法よりフューラーのアルゴリズムの性能が上回るのは天文学的に大きな整数同士の掛け算に限るため、フューラーのアルゴリズムはほとんど実用されていない。 実際には、ショーンハーゲ・ストラッセン法がカラツバ法やのような従来の手法より性能が上回り始めるのは、2215 - 2217（10進法で10 000 - 40 000桁）同士の掛け算である。GNU Multi-Precision Libraryはアーキテクチャに依存するが 、64ビット演算において少なくとも1728 - 7808ワード（10進法で33 000 - 150 000桁）の大きさの計算において初めてショーンハーゲ・ストラッセン法を用いる。10進法で74 000桁以上においてショーンハーゲ・ストラッセン法を用いるJavaの実装も存在する。 (ja)
- O Algoritmo Schönhage-Strassen ou Método de Multiplicação Schönhage-Strassen é um método rápido de multiplicação de números inteiros grandes. O método por trás do algoritmo consiste na Transformação Rápida de Fourier ou Transformada Rápida de Fourier, abreviada e conhecida pelo inglês como FFT (Fast Fourier Transform). Criada por Volker Schönhage e Arnold Strassen em 1971, este método requer operações aritméticas e operações de bits de ordem assintótica, onde n é o número de dígitos no produto. (pt)
- Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует ) битовых операций, где — количество двоичных цифр в произведении. Изобретён Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году.
* представляется как , а — как , где ;
* перемножаются многочлены и с помощью быстрого преобразования Фурье, результат — ;
* применяются переносы через разряды: , то есть . Также в алгоритме можно умножать по модулю чисел Ферма , если применять двоичную систему счисления. (ru)
|
