Печать страницы - Умножение многочленов с помощью преобразования Фурье

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: RawonaM от декабря 30, 2011, 22:15

Не получается.
Вот код на питоне:

Код Выделить

a = [1, 2, 3]
b = [1, 2, 3]

poli1 = fft(a,  2*len(a))
poli2 = fft(b,  2*len(b))

poli3 = []

for i in range(0, len(poli1)):
    poli3.append(poli1[i] * poli2[i])
    
print poli3
print ifft(poli3, (len(a)-1)*(len(b)-1))

Вот вывод:

Цитировать[(36+0j), (-18.499999999999993-4.3301270189221563j), (1.4999999999999993-2.5980762113533169j), (4.0000000000000018-1.352477158045318e-14j), (1.4999999999999993+2.5980762113533169j), (-18.500000000000014+4.3301270189222274j)]

[ 5.75000000-1.73205081j 9.70753175-4.97548095j 13.00000000+0.4330127j
7.54246825+6.27451905j]

Что я делаю не так?

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: Квас от декабря 30, 2011, 23:05

Питон! :=

Не нашёл в справке, что такое fft и ifft.

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: RawonaM от декабря 30, 2011, 23:24

Цитата: Квас от декабря 30, 2011, 23:05
Не нашёл в справке, что такое fft и ifft.

http://docs.scipy.org/doc/numpy/reference/routines.fft.html

Нужно поставить пакет numpy. В Убунту это просто, на винде нужно колдовать.
Ну или самому написать fft (Fast Fourier Transform, там всего 10 строк кода).

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: RawonaM от декабря 30, 2011, 23:24

А вы знаете про преобразование Фурье? :)

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: Квас от декабря 30, 2011, 23:49

Цитата: RawonaM от декабря 30, 2011, 23:24
А вы знаете про преобразование Фурье? :)

$[tex]F[\varphi](\xi) = \int \varphi(x) e^{i(\xi, x)} dx[/tex]$

8-)

Правда, эта штука у меня ассоциируется с матфизикой, и не знаю, чем может облегчить перемножение многочленов тот факт, что преобразование Фурье переводит свёртку в произведение. Поэтому я подумал, что речь может идти о другом преобразовании.

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: RawonaM от декабря 30, 2011, 23:57

Да, это оно, только дискретное.
Чтобы перемножить два многочлена нужно произвести конволюцию коэффициентов. Допустим есть два многочлена размером n, если производить конволюцию в лоб, то нужно произвести n² умножений.
Преобразование Фурье позволяет быстро вычислить произвольное количество точек на функции. Находим 2n точек у обоих многочленов, перемножаем их по одному, потом из новых 2n точек делаем обратное преобразование Фурье и получаем результат - помножение двух многочленов.
Собственно получаем результат конволюции, а это всего лишь частный случай.

Название: Умножение многочленов с помощью преобразования Фурье
Отправлено: RawonaM от апреля 18, 2012, 10:35

J'ai réussi.

Код Выделить

from numpy import *

poli1 = [1, 2]
poli2 = [3, 4]

f1 = fft.fft(poli1,  len(poli1)*2,  -1)
f2 = fft.fft(poli2,  len(poli2)*2,  -1)

result = []

for i in range(len(f1)):
    result.append(f1[i]*f2[i])

print fft.ifft(result)

Цитата: output[ 3.+0.j 10.+0.j 8.+0.j 0.+0.j]

Et c'est vrai que (1+2x)(3+4x)=3+10x+8x²+0

Лингвофорум

Общий раздел => Наука и техника => Математика => Тема начата: RawonaM от декабря 30, 2011, 22:15