AlgoVerse

ضرب چندجمله‌ای‌ها با FFT

دو چندجمله‌ای را در O(n log n) ضرب می‌کند: هر دو را در ریشه‌های واحد ارزیابی می‌کند، مقدارها را نقطه به نقطه ضرب می‌کند و با FFT وارون ضریب‌ها را برمی‌گرداند.

ضرب مستقیم دو چندجمله‌ای درجه‌ی n (هر ضریب در هر ضریب) O(n²) است. ولی چندجمله‌ای را می‌شود با مقدارهایش در n نقطه هم نشان داد، و در این نمایش ضرب فقط O(n) است: مقدارها را نقطه به نقطه ضرب کن.

ادامه‌ی توضیح ↓
ورودی:
A 1×3 · B 1×2خروجی PDF

(1 + 2x + 3x²)(4 + 5x) = 4 + 13x + 22x² + 15x³؛ ضریب‌ها از توان صفر شروع می‌شوند.

  1. import cmath
  4. def multiply(A, B):
  5. # Coefficients, lowest power first: [a_0, a_1, …].
  6. a, b = A[0], B[0]
  7. size = len(a) + len(b) - 1
  8. n = 1
  9. while n < size:
  10. n = n * 2
  11. fa = fft(a + [0] * (n - len(a)), False)
  12. fb = fft(b + [0] * (n - len(b)), False)
  13. fc = [x * y for x, y in zip(fa, fb)]
  14. c = fft(fc, True)
  15. product = [round((v / n).real) for v in c][:size]
  16. return product
  19. def fft(a, inverse):
  20. n = len(a)
  21. if n == 1:
  22. return [complex(a[0])]
  23. sign = -1 if inverse else 1
  24. w_n = cmath.exp(sign * 2j * cmath.pi / n)
  25. even = fft(a[0::2], inverse)
  26. odd = fft(a[1::2], inverse)
  27. y = [0] * n
  28. w = 1
  29. for k in range(n // 2):
  30. t = w * odd[k]
  31. y[k] = even[k] + t
  32. y[k + n // 2] = even[k] - t
  33. w = w * w_n
  34. return y

ناوردا: (A·B)(x) = A(x)·B(x) در هر نقطه؛ پس مقدارهای حاصل‌ضرب در n نقطه، و از روی آن‌ها ضریب‌هایش، معلوم‌اند.

شروع اجرا

n—
product—

A

123

B

45

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

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

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

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

A list

[1, 2, 3]

B list

[4, 5]

Call stack

  1. multiply()خط 4
گام ۱ از ۲۲۲
خط سیاه = pointwise · خط نارنجی = گام کلیدیevaluate: 0/1 · pointwise: 0/1 · interpolate: 0/1
    توضیح

    ایده

    ضرب مستقیم دو چندجمله‌ای درجه‌ی n (هر ضریب در هر ضریب) O(n²) است. ولی چندجمله‌ای را می‌شود با مقدارهایش در n نقطه هم نشان داد، و در این نمایش ضرب فقط O(n) است: مقدارها را نقطه به نقطه ضرب کن.

    سه گام

    1. ارزیابی: هر دو چندجمله‌ای را با FFT در n ریشه‌ی واحد حساب کن (n توان ۲ای که برای حاصل‌ضرب کافی است): O(n log n).
    2. ضرب نقطه‌ای: O(n).
    3. درون‌یابی: با FFT وارون ضریب‌های حاصل‌ضرب را برگردان: O(n log n).

    جمعاً O(n log n). چون عددهای میانی مختلط‌اند، ضریب‌های نهایی را به نزدیک‌ترین عدد صحیح گرد می‌کنیم.

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

    • درخت فراخوانی سه FFT را نشان می‌دهد؛ product ضریب‌های نهایی از توان صفر به بالاست.