কেন FFT — DFT-এর কম্পিউটেশনাল কমপ্লেক্সিটি

১ · ডিরেক্ট DFT-এর খরচ কোথা থেকে আসে

M5-এ (L22) আমরা DFT-এর সংজ্ঞা শিখেছি:

$$X[k] = \sum_{n=0}^{N-1} x[n] \, e^{-j 2\pi kn/N}, \qquad k = 0, 1, \dots, N-1$$

লক্ষ্য করুন — একটি নির্দিষ্ট k-এর জন্য X[k] বের করতে Nটি পদ যোগ করতে হয়, আর প্রতিটি পদের জন্য একটি জটিল গুণন (x[n] আর exp(...)-এর গুণফল) লাগে। অর্থাৎ একটি k-এর জন্য Nটি গুণন এবং N-1টি যোগ। এখন এটি সবগুলো k = 0 থেকে N-1 পর্যন্ত করতে হবে — তাই মোট গুণন সংখ্যা N × N = N², আর মোট যোগ সংখ্যা N × (N-1)। দুটো মিলিয়ে মোট অপারেশন 2N² - N — যা বড় N-এর জন্য মূলত N²-এর সমানুপাতিক। এটাই DFT-কে O(N²) অ্যালগরিদম বলার কারণ।

২ · সত্যিকারের গণনা — কোডে গুণন ও যোগ গোনা

অনুমান না করে, চলুন সরাসরি কোডের ভেতরে প্রতিটি গুণন ও যোগ অপারেশন গুনে দেখি। নিচের counted_dft ফাংশনটি M5/L22-এর ডিরেক্ট DFT সূত্রই প্রয়োগ করে, কিন্তু প্রতিটি গুণন ও যোগের সাথে সাথে একটি কাউন্টার বাড়িয়ে দেয়:

import cmath, math

def counted_dft(x):
    N = len(x)
    X = [0j] * N
    mults = 0
    adds = 0
    for k in range(N):
        total = 0j
        for n in range(N):
            term = x[n] * cmath.exp(-2j * math.pi * k * n / N)
            mults += 1
            total += term
            if n > 0:
                adds += 1
        X[k] = total
    return X, mults, adds

print(f"{'N':>5} | {'জটিল গুণন':>10} | {'জটিল যোগ':>10} | {'মোট অপারেশন':>13} | {'N^2':>6}")
prev_total = None
for N in [8, 16, 32, 64, 128]:
    x = [math.sin(2 * math.pi * 3 * n / N) for n in range(N)]
    X, mults, adds = counted_dft(x)
    total = mults + adds
    ratio = f"{total/prev_total:.2f}x" if prev_total else "—"
    print(f"{N:>5} | {mults:>10} | {adds:>10} | {total:>13} | {N*N:>6}   (আগের তুলনায় {ratio})")
    prev_total = total

৩ · N বড় হলে বাস্তবে কী দাঁড়ায়

উপরের কোডে গোনা মোট অপারেশন সংখ্যা ঠিক 2N² - N সূত্র মেনে চলে (যাচাই: N=128-এ 2×128² - 128 = 32768 - 128 = 32640 — কোডের আউটপুটের সাথে হুবহু মিলে যায়)। এই যাচাই করা সূত্র ব্যবহার করে বড় N-এর জন্য কী হবে তা হিসেব করা যায় (Pyodide sandbox দ্রুত রাখতে কোডে আমরা N=128 পর্যন্তই সীমাবদ্ধ রাখছি, কিন্তু সূত্রটি বৈধ থাকে):

• N = 512 → 2×512² - 512 = ৫,২৩,৭৭৬টি অপারেশন
• N = 1024 (একটি সাধারণ অডিও FFT সাইজ) → 2×1024² - 1024 = ২১,০৯,১২৮টি অপারেশন
• N = 4096 → 2×4096² - 4096 = ৩,৩৫,৪৪,৩২০টি অপারেশন

একটি বাস্তব অডিও স্ট্রিমে প্রতি সেকেন্ডে হাজার হাজার বার এই ধরনের রূপান্তর করতে হতে পারে (যেমন M10-এ শেখা STFT/স্পেকট্রোগ্রাম)। N=4096-এ প্রতিটি DFT কল করতে প্রায় ৩ কোটি ৩৫ লক্ষ অপারেশন লাগলে, এটি বাস্তব-সময়ে (real-time) চালানো ব্যবহারিকভাবে অসম্ভব হয়ে দাঁড়ায়।