A transformada rápida de Fourier (FFT) é um bloco de construção chave em muitos algoritmos, incluindo multiplicação de grandes números e multiplicação de polinômios. As transformadas de Fourier também têm aplicações importantes em processamento de sinais, mecânica quântica e outras áreas, e ajudam a fazer com que partes significativas da economia global aconteçam. Falaremos sobre duas operações diferentes: avaliação polinomial multiponto (avaliando um grau) e seu inverso, interpolação polinomial (dadas as avaliações de um grau

Aviso de gatilho: tópico matemático especializado

Agradecimentos especiais a Karl Floersch pelo feedback

Um dos algoritmos mais interessantes na teoria dos números é a transformada rápida de Fourier (FFT). FFTs são um bloco de construção chave em muitos algoritmos, incluindo multiplicação extremamente rápida de grandes números, multiplicação de polinômios e geração e recuperação extremamente rápida de códigos de apagamento.

Os códigos de apagamento, em particular, são altamente versáteis; além de seus casos de uso básicos em armazenamento e recuperação de dados tolerantes a falhas, os códigos de eliminação também têm casos de uso mais avançados, como garantindo a disponibilidade de dados em blockchains escalonáveis e STARKs. Este artigo abordará o que são as transformadas rápidas de Fourier e como alguns dos algoritmos mais simples para computá-las funcionam.

BACKGROUND

Ok, tudo bem, as transformadas de Fourier também têm aplicações realmente importantes em processamento de sinais, mecânica quântica e outras áreas, e ajudam a fazer com que partes significativas da economia global aconteçam. Mas vamos lá, os elefantes são mais legais.

O original transformada de Fourier é uma operação matemática que é frequentemente descrita como a conversão de dados entre o “domínio da frequência” e o “domínio do tempo”. O que isso significa mais precisamente é que, se você tiver alguns dados, a execução do algoritmo resultará em uma coleção de ondas senoidais com diferentes frequências e amplitudes que, se você as adicionar, se aproximariam dos dados originais. As transformadas de Fourier podem ser usadas para coisas maravilhosas como expressando órbitas quadradas por meio de epiciclos e derivando um conjunto de equações que podem desenhar um elefante:

O tipo de transformada de Fourier de que falaremos nesta postagem é um algoritmo semelhante, exceto que em vez de ser um contínuo Transformação de Fourier números reais ou complexos, é um transformada discreta de Fourier Acima de campos finitos (consulte a seção "Um Interlúdio Matemático Modular" SUA PARTICIPAÇÃO FAZ A DIFERENÇA para uma atualização sobre o que são campos finitos).

Em vez de falar sobre a conversão entre “domínio da frequência” e “domínio do tempo”, aqui falaremos sobre duas operações diferentes: avaliação polinomial multiponto (avaliando um diploma <N polinomial em N pontos diferentes) e seu inverso, interpolação polinomial (dadas as avaliações de um diploma <N polinomial em N pontos diferentes, recuperando o polinômio). Por exemplo, se estivermos operando no campo primo com módulo 5, então o polinômio y = x² + 3 (por conveniência, podemos escrever os coeficientes em ordem crescente: [3,0,1]) avaliado nos pontos [0,1,2] dá os valores [3,4,2] (Não é [3,4,7] porque estamos operando em um campo finito onde os números envolvem 5), e podemos realmente fazer as avaliações [3,4,2] e as coordenadas em que foram avaliados ([0,1,2]) para recuperar o polinômio original [3,0,1].

Existem algoritmos para avaliação multiponto e interpolação que podem fazer qualquer operação em O (N²) Tempo. A avaliação multiponto é simples: apenas avalie separadamente o polinômio em cada ponto. Aqui está o código Python para fazer isso:

def eval_poly_at(self, poly, x, modulus): y = 0 power_of_x = 1 for coefficient in poly: y += power_of_x * coefficient power_of_x *= x return y % modulus

O algoritmo executa um loop passando por cada coeficiente e faz uma coisa para cada coeficiente, então ele é executado em SOBRE) Tempo. A avaliação multiponto envolve fazer esta avaliação em N pontos diferentes, então o tempo total de execução é O (N²).

A interpolação de Lagrange é mais complicada (procure por “interpolação de Lagrange” SUA PARTICIPAÇÃO FAZ A DIFERENÇA para uma explicação mais detalhada). O bloco de construção chave da estratégia básica é que para qualquer domínio D e apontar x, podemos construir um polinômio que retorna 1 para x e 0 para qualquer valor em D exceto x. Por exemplo, se D=[1,2,3,4] e x=1, o polinômio é:

Você pode ligar mentalmente 1, 2, 3 e 4 à expressão acima e verifique se ela retorna 1 para x=1 e 0 nos outros três casos.

Podemos recuperar o polinômio que fornece qualquer conjunto desejado de saídas no domínio dado, multiplicando e adicionando esses polinômios. Se chamarmos o polinômio acima P1, e os equivalentes para x = 2, x = 3, x = 4, P2, P3 e P4, então o polinômio que retorna [3,1,4,1] no domínio [1,2,3,4] é simplesmente 3⋅P1+P2+4⋅P3+P4. O cálculo dos polinômios Pi leva SOBRE²) tempo (primeiro você constrói o polinômio que retorna a 0 em todo o domínio, o que leva O (N²) tempo, em seguida, divida separadamente por (x − xi) para cada XI), e computar a combinação linear leva outro O (N²) tempo, então é O (N²) tempo de execução total.

Transformadas rápidas de Fourier

Há um preço que você tem que pagar por usar esse algoritmo muito mais rápido, que é o de que você não pode escolher nenhum campo arbitrário e nenhum domínio arbitrário. Ao passo que com a interpolação de Lagrange, você poderia escolher quaisquer coordenadas xey que desejasse e qualquer campo que desejasse (você poderia até mesmo fazer isso sobre números reais simples e antigos), e você poderia obter um polinômio que passa por eles., Com um FFT , você deve usar um campo finito e o domínio deve ser um subgrupo multiplicativo do campo (ou seja, uma lista de potências de algum valor de “gerador”).

Por exemplo, você pode usar o campo finito do módulo de inteiros 337, e para o uso do domínio [1,85,148,111,336,252,189,226] (esses são os poderes de 85 no campo, por exemplo. 85 ^ 3% 337 = 111; para em 226 porque o próximo poder de 85 ciclos de volta a 1). Além disso, o subgrupo multiplicativo deve ter tamanho 2n (há maneiras de fazer funcionar para números do formulário 2 ^ m⋅3 ^ n e, possivelmente, poderes primos ligeiramente mais elevados, mas depois torna-se muito mais complicado e ineficiente). O campo finito do módulo intergers 59, por exemplo, não funcionaria, porque existem apenas subgrupos multiplicativos de ordem 2, 29 e 58; 2 é muito pequeno para ser interessante, e o fator 29 é muito grande para ser compatível com FFT. A simetria que vem de grupos multiplicativos de tamanho 2 ^ n nos permite criar um algoritmo recursivo que calcula de maneira bastante inteligente os resultados de que precisamos a partir de uma quantidade de trabalho muito menor.

Para entender o algoritmo e por que ele tem um baixo tempo de execução, é importante entender o conceito geral de recursão. Um algoritmo recursivo é um algoritmo que tem dois casos: um "caso base" onde a entrada para o algoritmo é pequena o suficiente para que você possa fornecer a saída diretamente, e o "caso recursivo" onde o cálculo necessário consiste em algum "cálculo de colagem" mais um ou mais usos do mesmo algoritmo para entradas menores. Por exemplo, você pode ter visto algoritmos recursivos sendo usados ​​para classificar listas. Se você tiver uma lista (por exemplo, [1,8,7,4,5,6,3,2,9]), então você pode classificá-lo usando o seguinte procedimento:

• Se a entrada tiver um elemento, então ela já está “classificada”, então você pode apenas retornar a entrada.

• Se a entrada tiver mais de um elemento, classifique separadamente a primeira metade da lista e a segunda metade da lista e, em seguida, mescle as duas sublistas classificadas (chame-as A e B) do seguinte modo. Manter dois contadores, após e bpos, ambos começando em zero e mantêm uma lista de saída, que começa vazia. Até qualquer um após or bpos está no final da lista correspondente, verifique se A[após] or B[bpos] é menor. O que for menor, adicione esse valor ao final da lista de saída e aumente esse contador em 1. Uma vez feito isso, adicione o resto de qualquer lista que não foi totalmente processada ao final da lista de saída e retorne a saída Lista.

Observe que a "cola" no segundo procedimento tem tempo de execução SOBRE): se cada uma das duas sublistas tiver N elementos, então você precisa percorrer cada item em cada lista uma vez, então é SOBRE) cálculo total. Portanto, o algoritmo como um todo funciona considerando um problema de tamanho N, e dividindo-o em dois problemas de tamanho N2, mais SOBRE) de execução de “cola”.

Existe um teorema chamado de Teorema Mestre que nos permite calcular o tempo de execução total de algoritmos como este. Tem muitos subcasos, mas no caso em que você divide uma execução de tamanho N em k subcasos de tamanho N / k com SOBRE) cola (como é o caso aqui), o resultado é que a execução leva tempo O (N⋅log (N)).

Um FFT funciona da mesma maneira. Nós pegamos um problema de tamanho N, divida-o em dois problemas de tamanho N2, e fazer SOBRE) trabalho de cola para combinar as soluções menores em uma solução maior, então temos O (N⋅log (N)) tempo de execução total - muito mais rapido do que O (N2). Aqui está como fazemos. Descreverei primeiro como usar um FFT para avaliação multiponto (ou seja, para algum domínio D e polinomial P, calcular P (x) para cada x in D), e acontece que você pode usar o mesmo algoritmo para interpolação com um pequeno ajuste.

Suponha que temos um FFT onde o domínio dado é as potências de x em algum campo, onde x ^ 2 ^ k = 1 (por exemplo, no caso que apresentamos acima, o domínio são os poderes de 85 módulo 337 e 85 ^ 2 ^ 3 = 1) Temos alguns polinômios, por exemplo. y=6×7+2×6+9×5+5×4+x3+4×2+x+3 (vamos escrever como p = [3,1,4,1,5,9,2,6]) Queremos avaliar esse polinômio em cada ponto do domínio, ou seja. em cada um dos oito poderes de 85. Aqui está o que fazemos.

Primeiro, dividimos o polinômio em duas partes, que chamaremos mesmo e odds: evens =[3,4,5,2] e probabilidade [1,1,9,6] (ou evens =2×3+5×2+4x+3 e odds =6×3+9×2+x+1; sim, isso é apenas pegar os coeficientes de grau par e coeficientes de grau ímpar). Agora, notamos uma observação matemática: p (x) = pares (x2) + x⋅odds (x2) e p (−x) = evens (x2) −x⋅odds (x2) (pense sobre isso por si mesmo e certifique-se de entendê-lo antes de prosseguir).

A "cola" é relativamente fácil (e SOBRE) em tempo de execução): recebemos as avaliações de pares e probabilidades como tamanho-N / 2 listas, então simplesmente fazemos p [i] = evens_result [i] + domínio [i] ⋅odds_result [i] e p [N2 + i] = evens_result [i] −domain [i] ⋅odds_result [i] para cada índice i.

Aqui está o código completo:

def fft(vals, modulus, domain): if len(vals) == 1: return vals L = fft(vals[::2], modulus, domain[::2]) R = fft(vals[1::2], modulus, domain[::2]) o = [0 for i in vals] for i, (x, y) in enumerate(zip(L, R)): y_times_root = y*domain[i] o[i] = (x+y_times_root) % modulus o[i+len(L)] = (x-y_times_root) % modulus return o

Podemos tentar executá-lo:

>>> fft([3,1,4,1,5,9,2,6], 337, [1, 85, 148, 111, 336, 252, 189, 226])
[31, 70, 109, 74, 334, 181, 232, 4]

E podemos verificar o resultado; avaliando o polinômio na posição 85, por exemplo, realmente dá o resultado 70. Observe que isso só funciona se o domínio estiver “correto”; precisa ser da forma [x ^ i% módulo para i no intervalo (n)] onde x ^ n = 1.

Um FFT inverso é surpreendentemente simples:

def inverse_fft(vals, modulus, domain): vals = fft(vals, modulus, domain) return [x * modular_inverse(len(vals), modulus) % modulus for x in [vals[0]] + vals[1:][::-1]]

Basicamente, execute a FFT novamente, mas inverta o resultado (exceto se o primeiro item permanecer no lugar) e divida cada valor pelo comprimento da lista.

>>> domain = [1, 85, 148, 111, 336, 252, 189, 226]
>>> def modular_inverse(x, n): return pow(x, n - 2, n)
>>> values = fft([3,1,4,1,5,9,2,6], 337, domain)
>>> values
[31, 70, 109, 74, 334, 181, 232, 4]
>>> inverse_fft(values, 337, domain)
[3, 1, 4, 1, 5, 9, 2, 6]

Agora, para que podemos usar isso? Aqui está um caso de uso divertido: podemos usar FFTs para multiplicar números muito rapidamente. Suponha que queremos multiplicar 1253 by 1895. Aqui está o que faríamos. Primeiro, converteríamos o problema em um que fosse um pouco mais fácil: multiplicar o polinômios [3,5,2,1] by [5,9,8,1] (são apenas os dígitos dos dois números em ordem crescente) e, em seguida, converta a resposta de volta em um número fazendo uma única passagem para carregar dezenas de dígitos.

Podemos multiplicar polinômios com FFTs rapidamente, porque se você converter um polinômio em formulário de avaliação (ie. f (x) para cada x em algum domínio D), então você pode multiplicar dois polinômios simplesmente multiplicando suas avaliações. Então o que faremos é pegar os polinômios que representam nossos dois números em forma de coeficiente, use FFTs para convertê-los em forma de avaliação, multiplique-os pontualmente e converta de volta:

>>> p1 = [3,5,2,1,0,0,0,0]
>>> p2 = [5,9,8,1,0,0,0,0]
>>> x1 = fft(p1, 337, domain)
>>> x1
[11, 161, 256, 10, 336, 100, 83, 78]
>>> x2 = fft(p2, 337, domain)
>>> x2
[23, 43, 170, 242, 3, 313, 161, 96]
>>> x3 = [(v1 * v2) % 337 for v1, v2 in zip(x1, x2)]
>>> x3
[253, 183, 47, 61, 334, 296, 220, 74]
>>> inverse_fft(x3, 337, domain)
[15, 52, 79, 66, 30, 10, 1, 0]

Isso requer três FFTs (cada O (N⋅log (N)) tempo) e uma multiplicação pontual (SOBRE) tempo), então leva O (N⋅log (N)) tempo completamente (tecnicamente um pouco mais do que O (N⋅log (N)), porque para números muito grandes, você precisaria substituir 337 com um módulo maior e isso tornaria a multiplicação mais difícil, mas perto o suficiente). Isto é muito mais rapido do que a multiplicação do livro escolar, o que leva O (N2) Tempo:

 3 5 2 1 ------------
5 | 15 25 10 5
9 | 27 45 18 9
8 | 24 40 16 8
1 | 3 5 2 1 --------------------- 15 52 79 66 30 10 1

Portanto, agora pegamos o resultado e carregamos as dezenas de dígitos (este é um algoritmo de "percorrer a lista uma vez e fazer uma coisa em cada ponto", de modo que leva SOBRE) Tempo):

[15, 52, 79, 66, 30, 10, 1, 0]
[ 5, 53, 79, 66, 30, 10, 1, 0]
[ 5, 3, 84, 66, 30, 10, 1, 0]
[ 5, 3, 4, 74, 30, 10, 1, 0]
[ 5, 3, 4, 4, 37, 10, 1, 0]
[ 5, 3, 4, 4, 7, 13, 1, 0]
[ 5, 3, 4, 4, 7, 3, 2, 0]

E se lermos os dígitos de cima para baixo, obtemos 2374435. Vamos verificar a resposta….

>>> 1253 * 1895
2374435

Yay! Funcionou. Na prática, com essas pequenas entradas, a diferença entre O (N⋅log (N)) e O (N ^ 2) não é que grande, então a multiplicação do livro escolar é mais rápida do que esse processo de multiplicação baseado em FFT apenas porque o algoritmo é mais simples, mas em grandes entradas faz uma grande diferença.

Mas os FFTs são úteis não apenas para multiplicar números; como mencionado acima, a multiplicação polinomial e a avaliação multiponto são operações crucialmente importantes na implementação da codificação de eliminação, que é uma técnica muito importante para construir muitos tipos de sistemas tolerantes a falhas redundantes. Se você gosta de tolerância a falhas e eficiência, os FFTs são seus amigos.

FFTs e campos binários

Os campos principais não são o único tipo de campo finito que existe. Outro tipo de campo finito (realmente um caso especial do conceito mais geral de um campo de extensão, que são como o equivalente de campo finito de números complexos) são campos binários. Em um campo binário, cada elemento é expresso como um polinômio onde todas as entradas são 0 or 1, por exemplo. x ^ 3 + x + 1.

Adicionar polinômios é feito módulo 2, e subtração é o mesmo que adição (como -1 = 1mod2) Selecionamos algum polinômio irredutível como um módulo (por exemplo, x ^ 4 + x + 1; x ^ 4 + 1 não funcionaria porque x ^ 4 + 1 pode ser fatorado em (x2 + 1) ⋅ (x2 + 1) portanto, não é “irredutível”); a multiplicação é feita módulo desse módulo. Por exemplo, no campo binário mod x ^ 4 + x + 1, multiplicando x2 + 1 por x3 + 1 daria x5 + x3 + x2 + 1 se você apenas fizer a multiplicação, mas x^5+x^3+x^2+1=(x^4+x+1)⋅x+(x^3+x+1), então o resultado é o resto x ^ 3 + x + 1.

Podemos expressar este exemplo como uma tabuada de multiplicação. Multiplique primeiro [1,0,0,1] (ie. x ^ 3 + 1) de [1,0,1] (ie. x ^ 2 + 1):

 1 0 0 1 --------
1 | 1 0 0 1
0 | 0 0 0 0
1 | 1 0 0 1 ------------ 1 0 1 1 0 1

O resultado da multiplicação contém um x ^ 5 termo para que possamos subtrair (x4 + x + 1) ⋅x:

 1 0 1 1 0 1 - 1 1 0 0 1 [(x⁴ + x + 1) shifted right by one to reflect being multipled by x] ------------ 1 1 0 1 0 0 

E obtemos o resultado, [1,1,0,1] (or x3 + x + 1).

Tabelas de adição e multiplicação para o mod de campo binário x ^ 4 + x + 1. Elementos de campo são expressos como inteiros convertidos de binário (por exemplo, x ^ 3 + x ^ 2 → 1100 → 12)

Os campos binários são interessantes por dois motivos. Em primeiro lugar, se você quiser apagar dados binários de código, os campos binários são realmente convenientes porque N bytes de dados podem ser codificados diretamente como um elemento de campo binário, e quaisquer elementos de campo binário que você gerar executando cálculos nele também serão N bytes de comprimento. Você não pode fazer isso com campos primos porque o tamanho dos campos primos não é exatamente uma potência de dois; por exemplo, você pode codificar cada 2 bytes como um número de 0 ... 65536 no módulo de campo principal 65537 (que é primo), mas se você fizer um FFT nesses valores, a saída pode conter 65536, que não pode ser expresso em dois bytes.

Em segundo lugar, o fato de que adição e subtração tornam-se a mesma operação, e 1 + = 1 0, cria alguma “estrutura” que leva a algumas consequências muito interessantes. Uma peculiaridade particularmente interessante e útil dos campos binários é o “sonho de calouro”Teorema: (x + y) ^ 2 = x ^ 2 + y ^ 2 (e o mesmo para expoentes 4,8,16 ... basicamente qualquer potência de dois).

Mas se você quiser usar campos binários para codificação de eliminação, e fazê-lo de forma eficiente, você precisa ser capaz de fazer transformações rápidas de Fourier em campos binários. Mas então há um problema: em um campo binário, não há grupos multiplicativos (não triviais) de ordem 2 ^ n. Isso ocorre porque os grupos multiplicativos são todos ordenados 2 ^ n-1. Por exemplo, no campo binário com módulo x ^ 4 + x + 1, se você começar a calcular poderes sucessivos de x + 1, você volta para 1 depois de 15 passos - não 16. A razão é que o número total de elementos no campo é 16, mas um deles é zero, e você nunca vai chegar a zero multiplicando qualquer valor diferente de zero por si mesmo em um campo, então as potências de x + 1 ciclo em todos os elementos, exceto zero, então a duração do ciclo é 15, não 16. Então, o que fazemos?

A razão pela qual precisávamos que o domínio tivesse a "estrutura" de um grupo multiplicativo com 2n elementos antes é que precisávamos reduzir o tamanho do domínio por um fator de dois elevando ao quadrado cada número nele: o domínio [1,85,148,111,336,252,189,226] fica reduzido a [1,148,336,189] Porque 1 é o quadrado de ambos 1 e 336, 148 é o quadrado de ambos 85 e 252, e assim por diante.

Mas e se em um campo binário houver uma maneira diferente de reduzir pela metade o tamanho de um domínio? Acontece que existe: dado um domínio contendo 2 ^ k valores, incluindo zero (tecnicamente, o domínio deve ser um subespaço), podemos construir um novo domínio D ′ com metade do tamanho, tomando x⋅ (x + k) para x in D usando algum específico k in D. Porque o domínio original é um subespaço, uma vez que k está no domínio, qualquer x no domínio tem um correspondente x + k também no domínio, e a função f (x) = x⋅ (x + k) retorna o mesmo valor para x e x + k assim, obtemos o mesmo tipo de correspondência dois para um que a quadratura nos dá.

Então agora, como fazemos um FFT em cima disso? Usaremos o mesmo truque, convertendo um problema com um N-sized polinomial e N-dimensionado domínio em dois problemas, cada um com um N / 2-sized polinomial e N / 2Domínio de tamanho reduzido, mas desta vez usando equações diferentes. Vamos converter um polinômio p em dois polinômios mesmo e probabilidade de tal modo que p (x) = pares (x⋅ (k − x)) + x⋅odds (x⋅ (k − x)). Observe que para os pares e probabilidades que encontramos, tb seja verdade que p (x + k) = pares (x⋅ (k − x)) + (x + k) ⋅odds (x⋅ (k − x)). Então podemos fazer recursivamente um FFT para igualar e probabilidades no domínio reduzido [x⋅ (k − x) para x em D], e então usamos essas duas fórmulas para obter as respostas para duas “metades” do domínio, uma deslocada por k da outra.

Convertendo p em mesmo e probabilidade conforme descrito acima, acaba por não ser trivial. O algoritmo "ingênuo" para fazer isso é ele mesmo O (N ^ 2), mas acontece que em um campo binário, podemos usar o fato de que (x2−kx)2=x4−k2⋅x2, e mais geralmente (x2−kx)2i=x2i+1−k2i⋅x2i , para criar ainda outro algoritmo recursivo para fazer isso em O (N⋅log (N)) tempo.

E se você quiser fazer um inverso FFT, para fazer a interpolação, você precisa executar as etapas do algoritmo na ordem inversa. Você pode encontrar o código completo para fazer isso aqui: https://github.com/ethereum/research/tree/master/binary_fft, e um artigo com detalhes sobre algoritmos mais otimizados aqui: http://www.math.clemson.edu/~sgao/papers/GM10.pdf

Então, o que ganhamos com toda essa complexidade? Bem, podemos tentar executar a implementação, que apresenta tanto um "ingênuo" O (N ^ 2) avaliação multiponto e a baseada em FFT otimizada, e tempo de ambos. Aqui estão meus resultados:

>>> import binary_fft as b
>>> import time, random
>>> f = b.BinaryField(1033)
>>> poly = [random.randrange(1024) for i in range(1024)]
>>> a = time.time(); x1 = b._simple_ft(f, poly); time.time() - a
0.5752472877502441
>>> a = time.time(); x2 = b.fft(f, poly, list(range(1024))); time.time() - a
0.03820443153381348

E conforme o tamanho do polinômio fica maior, a implementação ingênua (_simples_ft) fica mais lento muito mais rapidamente do que o FFT:

>>> f = b.BinaryField(2053)
>>> poly = [random.randrange(2048) for i in range(2048)]
>>> a = time.time(); x1 = b._simple_ft(f, poly); time.time() - a
2.2243144512176514
>>> a = time.time(); x2 = b.fft(f, poly, list(range(2048))); time.time() - a
0.07896280288696289

E pronto, temos uma maneira eficiente e escalonável de avaliar e interpolar polinômios em vários pontos. Se quisermos usar FFTs para recuperar dados codificados por apagamento onde estamos desaparecido algumas peças, então algoritmos para isso também existem, embora sejam um pouco menos eficientes do que apenas fazer um único FFT. Aproveitar!

Este artigo foi publicado originalmente como “Transformadas rápidas de Fourier"

PlatoAi. Web3 Reimagined. Inteligência de dados amplificada.
Clique aqui para acessar.

Fonte: https://hackernoon.com/fast-fourier-transform-scaling-multi-point-evaluation?source=rss