Algoritmo Schönhage-Strassen

O Algoritmo Schönhage-Strassen ou Método de Multiplicação Schönhage - Strassen é um método rápido de multiplicação de 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 $O (n \cdot \log{n})$ aritméticas e operações de $O (n \cdot \log{n} \cdot \log{\log{n}})$ 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 depois de 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. Obter o produto dos polinômios 2x⁴+13x³+42x²+67x+56.
• Ao fazer transferências entre as fileiras, temos 3x⁴+7x³+9x²+2x+6., ou seja, 37.926.

No caso de o sistema de numeração ser de base 2 (sistema binário) podem ser feitas multiplicações em modulo, usando para módulo um número de Fermat $2 ^ {{2} ^ n} +1$.

O Método Schönhage - Strassen foi considerado o método para multiplicações mais rápido em comparação de velocidades assintoticas 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 $10 ^ {10.000}$ a $10 ^ {40.000}$ (de 10.000 a 40.000 dígitos decimais)

Weblinks

• Página pessoal do Prof. Dr. Arnold Schönhage
• Método de recorde mundial de cálculo é usado em homenagem póstuma (Comunicado à imprensa pela Universidade de Bonn em 21 de dezembro de 2004)