AlgoVerse

تبدیل فوریه‌ی سریع (FFT)

مقدار چندجمله‌ای را در n ریشه‌ی واحد با تقسیم و حل در O(n log n) حساب می‌کند (و برعکس، با FFT وارون)؛ پایه‌ی ضرب سریع چندجمله‌ای‌ها.

چندجمله‌ای A(x) = a_0 + a_1·x + … + a_{n−1}·x^{n−1} را می‌خواهیم در n نقطه حساب کنیم. اگر نقطه‌ها ریشه‌های n‌ام واحد ω^0, ω^1, …, ω^{n−1} (با ω = e^{2πi/n}) باشند، ترفندی ممکن است:

ادامه‌ی توضیح ↓
ورودی:
coeffs 1×4 · inverse=0خروجی PDF

A(x) = 1 + 2x + 3x² + 4x³ در چهار ریشه‌ی چهارم واحد (1، i، −1، −i): ۱۰، −2−2i، −2، −2+2i.

  1. import cmath
  4. def transform(coeffs, inverse):
  5. a = coeffs[0]
  6. n = len(a)
  7. if n & (n - 1) != 0:
  8. return None
  9. y = fft(a, inverse)
  10. if inverse:
  11. y = [v / n for v in y]
  12. rows = [(k, show(v)) for k, v in enumerate(y)]
  13. return [show(v) for v in y]
  16. def fft(a, inverse):
  17. n = len(a)
  18. if n == 1:
  19. return [complex(a[0])]
  20. sign = -1 if inverse else 1
  21. w_n = cmath.exp(sign * 2j * cmath.pi / n) # the principal n-th root of unity
  22. even = fft(a[0::2], inverse)
  23. odd = fft(a[1::2], inverse)
  24. y = [0] * n
  25. w = 1
  26. for k in range(n // 2):
  27. t = w * odd[k]
  28. y[k] = even[k] + t
  29. y[k + n // 2] = even[k] - t
  30. w = w * w_n
  31. return y
  34. def show(z):
  35. # Rounded for reading, e.g. "2-1.414i".
  36. re, im = round(z.real, 3) + 0.0, round(z.imag, 3) + 0.0
  37. return f"{re:g}" if im == 0 else f"{re:g}{im:+g}i"

ناوردا: A(ω^k) = A_زوج(ω^(2k)) + ω^k · A_فرد(ω^(2k))، و مربع ریشه‌های n‌ام واحد همان ریشه‌های (n/2)‌ام‌اند؛ پس هر سطح نصف کار را دارد.

شروع اجرا

n—
k—

جدول هنوز خالی است.

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

inverse0

نارنجی = در همین گام عوض شد

coeffs list

[1, 2, 3, 4]

Call stack

  1. transform()خط 4
گام ۱ از ۱۰۱
خط سیاه = butterfly · خط نارنجی = گام کلیدیbase: 0/4 · butterfly: 0/4 · done: 0/1
    توضیح

    ایده

    چندجمله‌ای A(x) = a_0 + a_1·x + … + a_{n−1}·x^{n−1} را می‌خواهیم در n نقطه حساب کنیم. اگر نقطه‌ها ریشه‌های n‌ام واحد ω^0, ω^1, …, ω^{n−1} (با ω = e^{2πi/n}) باشند، ترفندی ممکن است:

    A(x) = A_زوج(x²) + x · A_فرد(x²)

    و مربع ریشه‌های n‌ام همان ریشه‌های (n/2)‌ام‌اند. پس دو مسئله‌ی نیم‌اندازه حل می‌کنیم و با پروانه‌ها ترکیب می‌کنیم:

    y[k] = y⁰[k] + ω^k·y¹[k]      y[k + n/2] = y⁰[k] − ω^k·y¹[k]

    T(n) = 2T(n/2) + O(n) = O(n log n)، در برابر O(n²) برای حساب جداگانه‌ی n مقدار.

    FFT وارون

    برگشت از مقدارها به ضریب‌ها همان FFT است با ω⁻¹ به‌جای ω و تقسیم بر n (پارامتر inverse = 1).

    در trace به چه چیزی نگاه کنی

    • درخت فراخوانی دودویی است (زوج و فرد)؛ جدول آخر مقدارهای گردشده است.