تبدیل سریع فوریه: مقیاس بندی ارزیابی چند نقطه ای

تبدیل سریع فوریه (FFT) یک بلوک اصلی در بسیاری از الگوریتم ها از جمله ضرب اعداد بزرگ و ضرب چند جمله ای است. دگرگونی های فوریه همچنین کاربردهای مهمی در پردازش سیگنال ، مکانیک کوانتوم و سایر زمینه ها دارند و به تحقق بخشهای قابل توجهی از اقتصاد جهانی کمک می کند. ما در مورد دو عملیات مختلف صحبت خواهیم کرد: ارزیابی چند جمله ای چند نقطه ای (ارزیابی درجه) و درون یابی معکوس و چند جمله ای (با توجه به ارزیابی یک درجه)

تصویر
عکس پروفایل Vitalik Buterin Hacker Noon

هشدار محرک: مبحث تخصصی ریاضی

تشکر ویژه از کارل فلورش برای بازخورد

یکی از جالب ترین الگوریتم ها در نظریه اعداد ، تبدیل سریع فوریه (FFT) است. FFT ها یک عنصر اصلی در بسیاری از الگوریتم ها هستند ، از جمله ضرب بسیار سریع اعداد بزرگ ، ضرب چند جمله ای ، و تولید و بازیابی بسیار سریع کدهای پاک کردن.

کدهای پاک کردن به ویژه بسیار متنوع هستند. کدهای پاک کننده علاوه بر موارد استفاده اساسی در ذخیره و بازیابی داده های مقاوم در برابر خطا ، موارد استفاده پیشرفته تری مانند تأمین دسترسی داده ها در بلاک چین های مقیاس پذیر و STARK ها را نیز دارا هستند. این مقاله به سرعت تبدیل فوریه و نحوه عملکرد برخی از الگوریتم های ساده تر برای محاسبه آنها می پردازد.

زمینه

تصویر
تصویر
تصویر

باشه فوریه …