Em matemática, a transformada discreta ponderada de base irracional (em inglês: IBDWT, sigla para irrational base discrete weighted transform) é uma variante da transformada rápida de Fourier que utiliza uma base irracional; foi desenvolvida por Richard Crandall (Reed College), Barry Fagin (Faculdade de Dartmouth) e Joshua Doenias (NeXT Software) no início da década de 1990 usando o Mathematica. Ela implica uma implementação rápida e prática da multiplicação modular de números muito grandes em computadores modernos, sendo assintoticamente duas vezes mais rápida do que a multiplicação por FFT não modular.
É mais notavelmente utilizada no Great Internet Mersenne Prime Search (GIMPS).
Algoritmo O método IBDWT, conforme aplicado no Teste de Lucas-Lehmer para números primos de Mersenne (que requer elevações ao quadrado repetidas num módulo de um número de Mersenne ), é baseado em quatro elementos-chave desenvolvidos por Crandall e Fagin: Representações de raiz balanceada: Permite que os dígitos tenham sinal (por exemplo, no intervalo ), o que reduz os limites de erro. Representações de dígitos de base variável: Permite que cada dígito tenha a sua própria base . Convoluções cíclicas ponderadas: A multiplicação é realizada usando uma Transformada Discreta Ponderada (DWT). Bases numéricas irracionais: A base utilizada para a transformada é irracional.
Essa abordagem evita a necessidade de preenchimento com zeros (zero-padding) nas matrizes e realiza a multiplicação do módulo diretamente. O algoritmo para calcular o produto é o seguinte: Escolha o comprimento do sinal (run length) . Estabeleça uma representação de base variável para os números. Por exemplo, . Cada termo geralmente tem entre 16 e 20 bits se forem usados termos de precisão dupla. O tamanho máximo de cada termo é determinado empiricamente, pelo menos antes da contribuição de Percival em 2003. Defina um sinal de peso onde cada componente , aproximado por números de ponto flutuante (floats) no intervalo [1, 2). Calcule a DWT direta (forward DWT) para ambos os números: e . Isso é calculado de forma prática usando uma Transformada discreta de Fourier (DFT) padrão, como a FFT, através da fórmula . Realize o produto componente a componente das matrizes transformadas: . Calcule a DWT inversa: . Isso é calculado como . Arredonde os componentes resultantes para o número inteiro mais próximo: , opcionalmente verificando se o erro de arredondamento não é superior a 0,4 (um valor maior indica que muitos bits inteiros foram inseridos em cada termo). Ajuste os dígitos resultantes para restaurar a representação de raiz de base variável. Esta etapa lida com os transportes (carries) e os empréstimos (borrows). O transporte parcial de passo único é suficiente.
Aplicações A IBDWT de precisão dupla é utilizada no cliente Prime95 x86 da Great Internet Mersenne Prime Search para realizar multiplicações modulares no Teste de Lucas-Lehmer e nos testes de primalidade de Fermat. A biblioteca IBDWT gwnum do Prime95 também é empregada em programas como o LLR2 e PRST do PrimeGrid. Ela é escolhida porque as CPUs x86 desde o Pentium 4 possuem tanta capacidade de computação em ponto flutuante de precisão dupla que é muito mais rápido multiplicar números usando IBDWT do que fazê-lo usando uma FFT inteira mais simples (como a Transformada Teórica dos Números, NTT).
A IBDWT de precisão dupla também foi portada para outras arquiteturas de CPU na forma do projeto Glucas. Ela também foi adaptada para GPUs na forma de CUDALucas, GPUowl e PRPLL.
A IBDWT também pode ser executada utilizando aritmética de inteiros no módulo 264-232+1, consistindo em uma Transformada Teórica dos Números. Esta abordagem foi demonstrada pela primeira vez por Nick Craig-Wood em ARMPrime. Essa técnica também foi portada para GPUs, oferecendo uma alternativa para GPUs de uso doméstico que têm fraco desempenho em computação de precisão dupla, mas uma potência aceitável em inteiros de 32 bits, especialmente nos modelos da Nvidia da década de 2020, que oferecem uma velocidade de multiplicação de inteiros de 32 bits "1:1" ou "1:2", mas uma velocidade de precisão dupla de "1:64" em relação ao ponto flutuante de 32 bits.
Métodos derivados Granger e Scott demonstraram o uso da "multiplicação GRP" (primo repunit generalizado), inspirada na IBDWT, para acelerar a criptografia de curvas elípticas sobre F(2521-1), na curva P-521. Trata-se de uma técnica semelhante à multiplicação de Karatsuba, apresentando uma convolução cíclica parecida com a IBDWT.
Leitura adicional Richard Crandall, Barry Fagin: Discrete weighted transforms and large-integer arithmetic, Mathematics of Computation 62, 205, 305-324, January 1994 (Arquivo PDF) Richard Crandall: Topics in Advanced Scientific Computation, TELOS/Springer-Verlag
Categoria:Análise de Fourier