FFT سریع‌تر OpenAI؛ پیشرفت واقعی یا بازی با نمادگذاری؟
هوش مصنوعیClaude Opus 5.5خلاصهٔ کامل‌تر
FFT (یعنی تبدیل فوریهٔ سریع، روشی برای درآوردن محتوای فرکانسی یه سیگنال) یکی از مهم‌ترین الگوریتم‌های پردازش سیگناله. روش ساده برای یه ورودی به طول n حدود n² عملیات لازم داره، ولی الگوریتم بازگشتی کولی و توکی از ۱۹۶۵ این رو به کمتر از 5n log₂ n رسونده. مثلاً برای n برابر یک میلیون، این یعنی حدود ده هزار برابر سریع‌تر.
OpenAI تو مجموعه مقاله‌های ریاضی‌ای که هفتهٔ پیش منتشر کرد، ادعا کرده یه FFT سریع‌تر پیدا کرده که جملهٔ log nش یه ذره کوچیک‌تره. بن رکت تو وبلاگ argmin می‌گه این بیشتر یه سوءاستفاده از قواعد بازیه تا یه پیشرفت. خودش هم با کنایه می‌گه مقاله رو نخونده و فقط از ChatGPT پرسیده نظرش دربارهٔ خروجی خودش چیه.
مشکل اول به نمادگذاری big-O برمی‌گرده (یعنی فقط رشد زمان اجرا برای n خیلی بزرگ مهمه و ضریب‌ها نادیده گرفته می‌شن). نویسنده می‌گه O(n) می‌تونه یعنی ۱۰ به توان ۸۰ ضرب در n و باز هم «خطی» حساب بشه. به این‌جور الگوریتم‌ها که ثابت‌های غیرقابل‌تصوری دارن می‌گن galactic algorithm. طبق تخمین‌ها، ثابت الگوریتم OpenAI حدود ۱۰ به توان ۱۰۰ هست. یعنی حتی برای n برابر ۱۰ به توان ۱۰۰، همون FFT قدیمی ۱۰ به توان ۹۹ برابر سریع‌تره.
مشکل دوم مدل محاسباتیه. الگوریتم فرض می‌کنه میشه عددهای مختلط رو با دقت دلخواه نگه داشت و تو یه عملیات ضرب کرد. در حالی که اندازهٔ این عددها با n به‌صورت فوق‌چندجمله‌ای بزرگ میشه و اگه به بیت ذخیره‌شون کنی، حافظه عملاً نمایی میشه. به گفتهٔ نویسنده، این قبلاً هم معلوم بود: مورگنسترن ۱۹۷۳ نشون داد با ضریب‌های کران‌دار نمی‌شه زیر ½ n log n رفت و نیر آیلون هم بعدها نشون داد زیر n log n بدون ناپایداری عددی شدید ممکن نیست.
رکت همین نقد رو به بقیهٔ نتایج OpenAI هم وارد می‌دونه، مثلاً ضرب ماتریس با O(n^2.25) که حتی نمی‌شه ثابتش رو تخمین زد. اون معتقده مشکل اصلی فرهنگ نظریهٔ علوم کامپیوتره که اجرای الگوریتم روی کامپیوتر واقعی رو تشویق نمی‌کنه. به گفتهٔ نویسنده، AI داره بدترین عادت‌های این حوزه رو خودکار می‌کنه و حالا می‌تونه مقاله‌های نظری بی‌فایده بنویسه.
نکات کلیدی:
- FFT کولی و توکی یه تبدیل به طول n رو با کمتر از 5n log₂ n عملیات حساب می‌کنه.
- الگوریتم OpenAI فقط از نظر مجانبی سریع‌تره و ثابت پنهانش حدود ۱۰ به توان ۱۰۰ تخمین زده شده.
- این الگوریتم فرض می‌کنه ضرب عددهای مختلط با دقت دلخواه فقط یه عملیاته.
- مورگنسترن ۱۹۷۳ کران پایین ½ n log n رو برای ضریب‌های کران‌دار ثابت کرد.
- نتیجهٔ ضرب ماتریس O(n^2.25) هم ثابتی داره که اصلاً قابل تخمین نیست.
