يعد تحويل فورييه السريع (FFT) لبنة أساسية في العديد من الخوارزميات ، بما في ذلك مضاعفة الأعداد الكبيرة وضرب كثيرات الحدود. تحتوي تحويلات فورييه أيضًا على تطبيقات مهمة في معالجة الإشارات وميكانيكا الكم ومجالات أخرى ، وتساعد في تحقيق أجزاء مهمة من الاقتصاد العالمي. سنتحدث عن عمليتين مختلفتين: التقييم متعدد الحدود متعدد النقاط (تقييم الدرجة) والاستيفاء المعكوس متعدد الحدود (بالنظر إلى تقييمات الدرجة)

تحذير الزناد: موضوع رياضي متخصص

شكر خاص لكارل فلورش على آرائهم

يعد تحويل فورييه السريع (FFT) أحد الخوارزميات الأكثر إثارة للاهتمام في نظرية الأعداد. FFTs هي لبنة أساسية في العديد من الخوارزميات ، بما في ذلك الضرب السريع للغاية للأعداد الكبيرة، ومضاعفة كثيرات الحدود ، وتوليد واسترداد سريع للغاية رموز المحو.

رموز المحو على وجه الخصوص متعددة الاستخدامات ؛ بالإضافة إلى حالات الاستخدام الأساسية في تخزين البيانات المتسامحة واستردادها ، فإن رموز المحو لها أيضًا حالات استخدام أكثر تقدمًا مثل تأمين توافر البيانات في سلاسل الكتل القابلة للتطوير و  ستاركس. ستتناول هذه المقالة ماهية تحويلات فورييه السريعة ، وكيف تعمل بعض الخوارزميات الأبسط لحسابها.

خلفيّة

حسنًا ، تحويلات فورييه لها أيضًا تطبيقات مهمة حقًا في معالجة الإشارات وميكانيكا الكم ومجالات أخرى ، وتساعد في جعل أجزاء كبيرة من الاقتصاد العالمي تحدث. لكن هيا ، الفيلة أكثر برودة.

الأصلي تحويل فورييه هي عملية حسابية توصف غالبًا بأنها تحويل البيانات بين "مجال التردد" و "المجال الزمني". ما يعنيه هذا بشكل أكثر دقة هو أنه إذا كان لديك جزء من البيانات ، فإن تشغيل الخوارزمية سيأتي بمجموعة من الموجات الجيبية ذات الترددات والسعات المختلفة التي ، إذا أضفتها معًا ، ستقارب البيانات الأصلية. يمكن استخدام تحويلات فورييه لأشياء رائعة مثل التعبير عن مدارات مربعة من خلال التدوير و  اشتقاق مجموعة من المعادلات التي يمكن أن ترسم الفيل:

نوع تحويل فورييه الذي سنتحدث عنه في هذا المنشور هو خوارزمية مماثلة ، باستثناء أنه بدلاً من أن يكون متواصل فورييه يتحول أعداد حقيقية أو معقدة، انه تحويل فورييه المنفصل على مدى مجالات محدودة (راجع قسم "فاصلة الرياضيات المعيارية" هنا لتجديد المعلومات عن ماهية الحقول المحدودة).

بدلاً من الحديث عن التحويل بين "مجال التردد" و "المجال الزمني" ، سنتحدث هنا عن عمليتين مختلفتين: تقييم متعدد الحدود متعدد النقاط (تقييم درجة <N كثير الحدود في N نقاط مختلفة) وعكسها ، استيفاء كثير الحدود (بالنظر إلى تقييمات الدرجة <N كثير الحدود في N نقاط مختلفة ، واستعادة كثير الحدود). على سبيل المثال ، إذا كنا نعمل في الحقل الأولي بالمعامل 5 ، فحينئذٍ يكون كثير الحدود ص = س² + 3 (للراحة يمكننا كتابة المعاملات بترتيب تصاعدي: [3,0,1]) تقييمها عند النقاط [0,1,2] يعطي القيم [3,4,2] اذا لم تكن [3,4,7] لأننا نعمل في مجال محدود حيث تلتف الأرقام عند 5) ، ويمكننا بالفعل أخذ التقييمات [3,4,2] والإحداثيات التي تم تقييمها عند ([0,1,2]) لاستعادة كثير الحدود الأصلي [3,0,1].

هناك خوارزميات لكل من التقييم متعدد النقاط والاستيفاء التي يمكن أن تقوم بأي عملية في O (N²) زمن. التقييم متعدد النقاط بسيط: فقط قم بتقييم كثير الحدود بشكل منفصل في كل نقطة. إليك كود Python للقيام بذلك:

def eval_poly_at(self, poly, x, modulus): y = 0 power_of_x = 1 for coefficient in poly: y += power_of_x * coefficient power_of_x *= x return y % modulus

تدير الخوارزمية حلقة تمر عبر كل معامل وتفعل شيئًا واحدًا لكل معامل ، لذا فهي تعمل في على) زمن. يتضمن التقييم متعدد النقاط إجراء هذا التقييم في N نقاط مختلفة ، وبالتالي فإن إجمالي وقت التشغيل هو O (N²).

استيفاء لاغرانج أكثر تعقيدًا (ابحث عن "استيفاء لاغرانج" هنا للحصول على شرح أكثر تفصيلاً). اللبنة الأساسية للاستراتيجية الأساسية هي ذلك لأي مجال D و نقطة x، يمكننا بناء كثير الحدود الذي يعود 1 For x و  0 لأي قيمة في D غير x. على سبيل المثال، إذا D=[1,2,3,4] و  x=1، كثير الحدود هو:

يمكنك توصيل عقليا 1, 2, 3 و  4 للتعبير أعلاه وتحقق من أنه يعود 1 For x=1 و  0 في الحالات الثلاث الأخرى.

يمكننا استرداد كثير الحدود الذي يعطي أي مجموعة مرغوبة من المخرجات على المجال المحدد بضرب هذه كثيرات الحدود وإضافتها. إذا أطلقنا على كثير الحدود أعلاه P1، وما يعادلها من أجل س = 2, س = 3, س = 4, P2, P3 و  P4، ثم كثير الحدود الذي يتم إرجاعه [3,1,4,1] في المجال [1,2,3,4] هو ببساطة 3⋅P1+P2+4⋅P3+P4. يأخذ حساب متعدد الحدود Pi على²) الوقت (تقوم أولاً ببناء كثير الحدود الذي يعود إلى 0 على المجال بأكمله ، وهو ما يستغرقه O (N²) الوقت ، ثم قسّمه بشكل منفصل على (x − xi) لكل منهما الحادي عشر)، وحساب التركيبة الخطية يأخذ شيئًا آخر O (N²) الوقت ، لذلك حان O (N²) إجمالي وقت التشغيل.

تحويلات فورييه السريعة

هناك ثمن يتعين عليك دفعه مقابل استخدام هذه الخوارزمية الأسرع بكثير ، وهو أنه لا يمكنك اختيار أي مجال عشوائي وأي مجال عشوائي. بينما باستخدام استيفاء لاغرانج ، يمكنك اختيار أي إحداثيات x وإحداثيات y التي تريدها ، وأي مجال تريده (يمكنك حتى القيام بذلك باستخدام أرقام حقيقية قديمة بسيطة) ، ويمكنك الحصول على كثير الحدود الذي يمر من خلالها. ، باستخدام FFT ، يجب عليك استخدام حقل محدد ، ويجب أن يكون المجال المجموعة الفرعية المضاعفة من الحقل (أي قائمة القوى لبعض قيمة "المولد").

على سبيل المثال ، يمكنك استخدام الحقل المحدود لنموذج الأعداد الصحيحة 337، ولاستخدام المجال [1,85,148,111,336,252,189,226] (هذه هي صلاحيات 85 في الميدان ، على سبيل المثال. 85 ^ 3٪ 337 = 111؛ يتوقف عند 226 لأن القوة التالية 85 دورات العودة إلى 1). علاوة على ذلك ، يجب أن يكون للمجموعة الفرعية المضاعفة حجم 2n (هناك طرق لجعلها تعمل مع أرقام النموذج 2 ^ م 3 ^ ن وربما قوى أولية أعلى قليلاً ولكن بعد ذلك تصبح أكثر تعقيدًا وغير فعالة). المجال المحدود من intergers modulo 59، على سبيل المثال ، لن ينجح ، لأن هناك فقط مجموعات فرعية مضاعفة من النظام 2 ، 29 ، XNUMX و  58 ؛ 2 صغير جدًا ليكون مثيرًا للاهتمام ، والعامل 29 أكبر بكثير من أن يكون مناسبًا لـ FFT. التناظر الذي يأتي من مجموعات الحجم المضاعفة 2 ^ ن يتيح لنا إنشاء خوارزمية تكرارية تحسب بذكاء النتائج التي نحتاجها من قدر أقل بكثير من العمل.

لفهم الخوارزمية وسبب انخفاض وقت تشغيلها ، من المهم فهم المفهوم العام للتكرار. الخوارزمية العودية عبارة عن خوارزمية لها حالتان: "الحالة الأساسية" حيث يكون إدخال الخوارزمية صغيرًا بما يكفي لإعطاء المخرجات مباشرة ، و "الحالة العودية" حيث يتكون الحساب المطلوب من بعض "الحسابات اللاصقة" بالإضافة إلى استخدام واحد أو أكثر لنفس الخوارزمية لمدخلات أصغر. على سبيل المثال ، ربما تكون قد شاهدت خوارزميات متكررة تُستخدم لفرز القوائم. إذا كان لديك قائمة (على سبيل المثال. [1,8,7,4,5,6,3,2,9]) ، ثم يمكنك فرزها باستخدام الإجراء التالي:

• إذا كان الإدخال يحتوي على عنصر واحد ، فسيكون "مفروزًا" بالفعل ، لذا يمكنك فقط إرجاع الإدخال.

• إذا كان الإدخال يحتوي على أكثر من عنصر واحد ، فقم بفرز النصف الأول من القائمة والنصف الثاني من القائمة بشكل منفصل ، ثم ادمج القائمتين الفرزيتين (اتصل بهم A و  B) على النحو التالي. الحفاظ على عدادات ، أبوس] و  بيوس، كلاهما يبدأ من الصفر ، ويحتفظ بقائمة مخرجات تبدأ فارغة. حتى إما أبوس] or بيوس في نهاية القائمة المقابلة ، تحقق مما إذا كان A[أبوس] or B[بوس] أصغر. أيهما أصغر ، أضف تلك القيمة إلى نهاية قائمة الإخراج ، وقم بزيادة هذا العداد بمقدار 1. بمجرد الانتهاء من ذلك ، أضف بقية القائمة التي لم تتم معالجتها بالكامل إلى نهاية قائمة الإخراج ، وأعد الإخراج قائمة.

لاحظ أن "الغراء" في الإجراء الثاني له وقت تشغيل على): إذا كانت كل من القائمتين الفرعيتين تحتوي على N العناصر ، فأنت بحاجة إلى تشغيل كل عنصر في كل قائمة مرة واحدة ، لذا فهو على) مجموع الحساب. لذا فإن الخوارزمية ككل تعمل عن طريق حل مشكلة الحجم N، وتقسيمها إلى مشكلتين من حيث الحجم N2، بالإضافة إلى على) تنفيذ "الغراء".

هناك نظرية تسمى نظرية الماجستير يتيح لنا حساب إجمالي وقت تشغيل الخوارزميات مثل هذا. يحتوي على العديد من الحالات الفرعية ، ولكن في حالة تقسيم تنفيذ الحجم N إلى حالات فرعية من الحجم غير متاح مع على) الغراء (كما هو الحال هنا) ، والنتيجة هي أن التنفيذ يستغرق وقتًا O (N⋅log (N)).

يعمل FFT بنفس الطريقة. نحن نأخذ مشكلة الحجم N، وقسمها إلى مشكلتين من حيث الحجم N2و افعل على) عمل الغراء لدمج الحلول الأصغر في حل أكبر ، لذلك نحصل عليه O (N⋅log (N)) إجمالي وقت التشغيل - أسرع بكثير من على 2). فيما يلي كيف نفعل ذلك. سأصف أولاً كيفية استخدام FFT للتقييم متعدد النقاط (على سبيل المثال ، بالنسبة لبعض المجالات D وكثير الحدود P، احسب ص (خ) لكل x in D) ، واتضح أنه يمكنك استخدام نفس الخوارزمية للاستيفاء باستخدام قرص بسيط.

افترض أن لدينا FFT حيث المجال المعطى هو صلاحيات x في بعض المجالات ، حيث س ^ 2 ^ ك = 1 (على سبيل المثال ، في الحالة التي قدمناها أعلاه ، فإن المجال هو صلاحيات 85 مودولو 337و 85 ^ 2 ^ 3 = 1). لدينا بعض كثير الحدود ، على سبيل المثال. y=6×7+2×6+9×5+5×4+x3+4×2+x+3 (سنكتبها كـ p = [3,1,4,1,5,9,2,6،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX]). نريد تقييم كثير الحدود هذا عند كل نقطة في المجال ، أي. في كل من القوى الثمانية لـ 85. هنا هو ما نقوم به.

أولًا ، نقسم كثيرة الحدود إلى جزأين ، سنسميهما يوحد و  الاحتمالات: يسوي =[3,4,5,2] و  خلاف [1,1,9,6] (أو يسوي =2×3+5×2+4x+3 و  احتمالات =6×3+9×2+x+1؛ نعم ، هذا فقط يأخذ معاملات الدرجة الزوجية ومعاملات الدرجة الفردية). الآن ، نلاحظ ملاحظة رياضية: ع (س) = يساوي (x2) + x⋅odds (x2) و  ع (−x) = يساوي (x2) −xodds (x2) (فكر في هذا بنفسك وتأكد من فهمك له قبل المضي قدمًا).

"الغراء" سهل نسبيًا (و على) في وقت التشغيل): نتلقى تقييمات التساويات والاحتمالات مثل الحجم- N / 2 القوائم ، لذلك نحن نفعل ذلك بكل بساطة p [i] = evens_result [i] + المجال [i] ⋅odds_result [i] و p [N2 + i] = evens_result [i] −domain [i] ⋅odds_result [i] لكل فهرس i.

ها هو الكود الكامل:

def fft(vals, modulus, domain): if len(vals) == 1: return vals L = fft(vals[::2], modulus, domain[::2]) R = fft(vals[1::2], modulus, domain[::2]) o = [0 for i in vals] for i, (x, y) in enumerate(zip(L, R)): y_times_root = y*domain[i] o[i] = (x+y_times_root) % modulus o[i+len(L)] = (x-y_times_root) % modulus return o

يمكننا محاولة تشغيله:

>>> fft([3,1,4,1,5,9,2,6], 337, [1, 85, 148, 111, 336, 252, 189, 226])
[31, 70, 109, 74, 334, 181, 232, 4]

ويمكننا التحقق من النتيجة ؛ تقييم كثير الحدود في الموضع 85، على سبيل المثال ، يعطي النتيجة بالفعل 70. لاحظ أن هذا لا يعمل إلا إذا كان المجال "صحيحًا" ؛ يجب أن يكون بالشكل [x ^ i٪ modulus for i in range (n)] أين س ^ ن = 1.

عكس FFT بسيط بشكل مدهش:

def inverse_fft(vals, modulus, domain): vals = fft(vals, modulus, domain) return [x * modular_inverse(len(vals), modulus) % modulus for x in [vals[0]] + vals[1:][::-1]]

بشكل أساسي ، قم بتشغيل FFT مرة أخرى ، لكن اعكس النتيجة (باستثناء بقاء العنصر الأول في مكانه) وقسم كل قيمة على طول القائمة.

>>> domain = [1, 85, 148, 111, 336, 252, 189, 226]
>>> def modular_inverse(x, n): return pow(x, n - 2, n)
>>> values = fft([3,1,4,1,5,9,2,6], 337, domain)
>>> values
[31, 70, 109, 74, 334, 181, 232, 4]
>>> inverse_fft(values, 337, domain)
[3, 1, 4, 1, 5, 9, 2, 6]

الآن ، في أي شيء يمكننا استخدام هذا؟ إليك حالة استخدام ممتعة: يمكننا استخدام FFT لمضاعفة الأرقام بسرعة كبيرة. افترض أننا أردنا الضرب 1253 by 1895. هذا ما سنفعله. أولًا ، سنحول المسألة إلى مشكلة يتبين أنها أسهل قليلاً: اضرب متعددو الحدود [3,5,2,1] by [5,9,8,1] (هذه فقط أرقام العددين بترتيب تصاعدي) ، ثم قم بتحويل الإجابة مرة أخرى إلى رقم عن طريق القيام بتمريرة واحدة لتحمل عشرات الأرقام.

يمكننا مضاعفة كثيرات الحدود باستخدام FFTs بسرعة ، لأنه يتضح أنه إذا قمت بتحويل كثير الحدود إلى استمارة تقييم (بمعنى آخر. و (خ) لكل x في بعض المجالات D) ، يمكنك إذن ضرب اثنين من كثيرات الحدود بضرب تقييماتهما. إذن ما سنفعله هو أخذ كثيرات الحدود التي تمثل العددين شكل معامل، استخدم FFTs لتحويلها إلى نموذج تقييم ، واضربها في الاتجاه المعاكس ، ثم قم بالتحويل مرة أخرى:

>>> p1 = [3,5,2,1,0,0,0,0]
>>> p2 = [5,9,8,1,0,0,0,0]
>>> x1 = fft(p1, 337, domain)
>>> x1
[11, 161, 256, 10, 336, 100, 83, 78]
>>> x2 = fft(p2, 337, domain)
>>> x2
[23, 43, 170, 242, 3, 313, 161, 96]
>>> x3 = [(v1 * v2) % 337 for v1, v2 in zip(x1, x2)]
>>> x3
[253, 183, 47, 61, 334, 296, 220, 74]
>>> inverse_fft(x3, 337, domain)
[15, 52, 79, 66, 30, 10, 1, 0]

هذا يتطلب ثلاثة FFTs (كل O (N⋅log (N)) time) وضرب نقطي واحد (على) الوقت) ، لذلك يستغرق الأمر O (N⋅log (N)) الوقت تمامًا (تقنيًا أكثر قليلاً من O (N⋅log (N)) ، لأن الأعداد الكبيرة جدًا ستحتاج إلى استبدالها 337 بمعامل أكبر وهذا من شأنه أن يجعل الضرب أكثر صعوبة ، ولكنه قريب بما فيه الكفاية). هذا هو أسرع بكثير من الضرب في الكتاب المدرسي ، والذي يأخذ على 2) زمن:

 3 5 2 1 ------------
5 | 15 25 10 5
9 | 27 45 18 9
8 | 24 40 16 8
1 | 3 5 2 1 --------------------- 15 52 79 66 30 10 1

والآن نأخذ النتيجة ونحمل أرقام العشرات (هذه خوارزمية "استعراض القائمة مرة واحدة وفعل شيئًا واحدًا في كل نقطة" ، لذا يتطلب الأمر على) زمن):

[15, 52, 79, 66, 30, 10, 1, 0]
[ 5, 53, 79, 66, 30, 10, 1, 0]
[ 5, 3, 84, 66, 30, 10, 1, 0]
[ 5, 3, 4, 74, 30, 10, 1, 0]
[ 5, 3, 4, 4, 37, 10, 1, 0]
[ 5, 3, 4, 4, 7, 13, 1, 0]
[ 5, 3, 4, 4, 7, 3, 2, 0]

وإذا قرأنا الأرقام من أعلى إلى أسفل ، نحصل عليها 2374435. دعونا نتحقق من الإجابة….

>>> 1253 * 1895
2374435

ياي! انها عملت. في الممارسة العملية ، على مثل هذه المدخلات الصغيرة ، الفرق بين O (N⋅log (N)) و  O (N ^ 2) ليس أن كبير ، لذا فإن عملية الضرب في الكتاب المدرسي أسرع من عملية الضرب المبنية على FFT لمجرد أن الخوارزمية أبسط ، ولكنها تحدث فرقًا كبيرًا حقًا في المدخلات الكبيرة.

لكن FFTs مفيدة ليس فقط لضرب الأرقام ؛ كما هو مذكور أعلاه ، يعد الضرب متعدد الحدود والتقييم متعدد النقاط عمليتين مهمتين للغاية في تنفيذ تشفير المحو ، وهو أسلوب مهم جدًا لبناء أنواع عديدة من الأنظمة الزائدة المتسامحة مع الأخطاء. إذا كنت تحب التسامح مع الأخطاء وتحب الكفاءة ، فإن FFTs هي صديقك.

FFTs والمجالات الثنائية

الحقول الرئيسية ليست النوع الوحيد من الحقول المحدودة الموجودة هناك. نوع آخر من المجال المحدود (حقًا حالة خاصة للمفهوم الأكثر عمومية لـ مجال التمديد، والتي تشبه إلى حد ما مكافئ المجال المحدود للأرقام المركبة) هي حقول ثنائية. في الحقل الثنائي ، يتم التعبير عن كل عنصر على أنه متعدد الحدود حيث تكون جميع الإدخالات 0 or 1، على سبيل المثال. س ^ 3 + س + 1.

تتم إضافة كثيرات الحدود بطريقة نمطية 2، والطرح هو نفسه الجمع (مثل −1 = 1 نموذج 2). نختار بعض كثيرات الحدود غير القابلة للاختزال كمعامل (على سبيل المثال. س ^ 4 + س + 1 ؛ س ^ 4 + 1 لن يعمل بسبب س ^ 4 + 1 يمكن أخذها في الاعتبار (x2 + 1) ⋅ (x2 + 1) لذلك فهي ليست "غير قابلة للاختزال") ؛ يتم الضرب بمقياس هذا المعامل. على سبيل المثال ، في تعديل المجال الثنائي س ^ 4 + س + 1، ضرب x2 + 1 في x3 + 1 كنت لأعطي x5 + x3 + x2 + 1 إذا كنت تقوم بعملية الضرب فقط ، ولكن x^5+x^3+x^2+1=(x^4+x+1)⋅x+(x^3+x+1)، وبالتالي فإن النتيجة هي الباقي س ^ 3 + س + 1.

يمكننا التعبير عن هذا المثال كجدول ضرب. اضرب أولا [1,0,0,1] (بمعنى آخر. س ^ 3 + 1) بواسطة [1,0,1] (بمعنى آخر. س ^ 2 + 1):

 1 0 0 1 --------
1 | 1 0 0 1
0 | 0 0 0 0
1 | 1 0 0 1 ------------ 1 0 1 1 0 1

نتيجة الضرب تحتوي على س ^ 5 المصطلح حتى نتمكن من طرحه (x4 + x + 1) ⋅x:

 1 0 1 1 0 1 - 1 1 0 0 1 [(x⁴ + x + 1) shifted right by one to reflect being multipled by x] ------------ 1 1 0 1 0 0 

ونحصل على النتيجة ، [1,1,0,1] (or x3 + x + 1).

جداول الجمع والضرب لتعديل المجال الثنائي س ^ 4 + س + 1. يتم التعبير عن عناصر الحقل كأعداد صحيحة محولة من ثنائي (على سبيل المثال. x ^ 3 + x ^ 2 → 1100 → 12)

المجالات الثنائية مثيرة للاهتمام لسببين. بادئ ذي بدء ، إذا كنت تريد مسح البيانات الثنائية ذات التعليمات البرمجية ، فإن الحقول الثنائية مناسبة حقًا لأن N يمكن تشفير بايت البيانات مباشرة كعنصر حقل ثنائي ، وأي عناصر حقل ثنائي تقوم بإنشائها عن طريق إجراء عمليات حسابية عليها ستكون أيضًا N بايت طويل. لا يمكنك القيام بذلك مع الحقول الأولية لأن حجم الحقول الأولية ليس بالضبط قوة اثنين ؛ على سبيل المثال ، يمكنك ترميز كل 2 بايت كرقم من 0 ... 65536 في نمط المجال الرئيسي 65537 (وهو أولي) ، ولكن إذا قمت بإجراء FFT على هذه القيم ، فيمكن أن يحتوي الإخراج على 65536، والتي لا يمكن التعبير عنها في وحدتي بايت.

ثانيًا ، حقيقة أن الجمع والطرح يصبحان نفس العملية ، و 1 + = 1 0، إنشاء بعض "البنية" التي تؤدي إلى بعض النتائج المثيرة للاهتمام للغاية. أحد المجالات الغريبة والمثيرة للاهتمام والمفيدة بشكل خاص في المجالات الثنائية هو "حلم الطالب الجديدنظرية: (س + ص) ^ 2 = س ^ 2 + ص ^ 2 (ونفس الشيء بالنسبة للأسس 4,8,16 ... في الأساس أي قوة اثنين).

ولكن إذا كنت ترغب في استخدام الحقول الثنائية لمحو الترميز ، والقيام بذلك بكفاءة ، فأنت بحاجة إلى أن تكون قادرًا على إجراء تحويلات فورييه السريعة عبر الحقول الثنائية. ولكن هناك مشكلة بعد ذلك: في مجال ثنائي ، لا توجد مجموعات ترتيب مضاعفة (غير بديهية) 2 ^ ن. هذا لأن مجموعات الضرب كلها مرتبة 2 ^ ن -1. على سبيل المثال ، في المجال الثنائي مع المعامل س ^ 4 + س + 1، إذا بدأت في حساب قوى متتالية لـ x + 1، يمكنك العودة إلى 1 بعد 15 خطوات - لا 16. والسبب هو أن العدد الإجمالي للعناصر في الحقل هو 16، ولكن واحدًا منهم يساوي صفرًا ، ولن تصل أبدًا إلى الصفر بضرب أي قيمة غير صفرية في نفسها في الحقل ، لذا فإن قوى x + 1 دورة من خلال كل عنصر باستثناء الصفر ، وبالتالي فإن طول الدورة هو 15، لا 16. إذن ماذا نفعل؟

السبب في احتياجنا للمجال للحصول على "بنية" مجموعة مضاعفة مع عناصر 2n من قبل هو أننا نحتاج إلى تقليل حجم المجال بمعامل اثنين عن طريق تربيع كل رقم فيه: المجال [1,85,148,111,336,252,189,226] إلى [1,148,336,189] لان 1 هو مربع كلاهما 1 و  336 ، 148 ، XNUMX هو مربع كلاهما 85 و  252، وهكذا دواليك.

ولكن ماذا لو كانت هناك طريقة مختلفة في مجال ثنائي لخفض حجم المجال إلى النصف؟ اتضح أن هناك: معطى المجال الذي يحتوي على 2 ^ ك القيم ، بما في ذلك الصفر (من الناحية الفنية ، يجب أن يكون المجال أ فضاء جزئي) ، يمكننا بناء مجال جديد نصف الحجم D ′ عن طريق أخذ س (س + ك) For x in D باستخدام بعض محددة k in D. لأن المجال الأصلي هو فضاء فرعي ، منذ ذلك الحين k في المجال ، أي x في المجال لديه المقابل س + ك أيضا في المجال والوظيفة و (س) = س⋅ (س + ك) إرجاع نفس القيمة لـ x و  س + ك لذلك نحصل على نفس النوع من المراسلات الثنائية إلى واحد التي يعطينا إياها التربيع.

إذن الآن ، كيف يمكننا عمل FFT فوق هذا؟ سنستخدم نفس الحيلة ، في تحويل مشكلة بامتداد Nمتعدد الحدود الحجم و Nذات الحجم إلى مشكلتين لكل منهما N / 2متعدد الحدود الحجم و N / 2المجال ذو الحجم ، ولكن هذه المرة باستخدام معادلات مختلفة. سنحول p كثير الحدود إلى كثيرتي حدود يوحد و  خلاف مثل ذلك ع (س) = يساوي (س⋅ (ك − س)) + x⋅odds (س (ك − س)). لاحظ أنه بالنسبة للتساويات والاحتمالات التي نجدها ، فإنها ستفعل أيضا كن صحيحا p (x + k) = مساوي (x⋅ (k − x)) + (x + k) ⋅odds (x⋅ (k − x)). لذلك يمكننا بعد ذلك إجراء عملية FFT بشكل متكرر لتسوية وتفضيل المجال المختزل [x⋅ (k − x) لـ x في D]، ثم نستخدم هاتين الصيغتين للحصول على إجابات "نصفي" المجال ، أحدهما يقابله k من الآخر.

تحويل p إلى يوحد و  خلاف كما هو موضح أعلاه تبين أنه غير بديهي. الخوارزمية "الساذجة" للقيام بذلك هي نفسها O (N ^ 2)، ولكن اتضح أنه في المجال الثنائي ، يمكننا استخدام حقيقة ذلك (x2−kx)2=x4−k2⋅x2، وبشكل أعم (x2−kx)2i=x2i+1−k2i⋅x2i ، لإنشاء خوارزمية تكرارية أخرى للقيام بذلك في O (N⋅log (N)) مرة.

وإذا كنت تريد أن تفعل معكوس FFT ، لإجراء الاستيفاء ، فأنت بحاجة إلى تشغيل الخطوات في الخوارزمية بترتيب عكسي. يمكنك العثور على الكود الكامل للقيام بذلك هنا: https://github.com/ethereum/research/tree/master/binary_fft، وورقة تحتوي على تفاصيل حول المزيد من الخوارزميات المثلى هنا: http://www.math.clemson.edu/~sgao/papers/GM10.pdf

إذن ما الذي نحصل عليه من كل هذا التعقيد؟ حسنًا ، يمكننا محاولة تشغيل التطبيق ، والذي يتميز بكل من "السذاجة" O (N ^ 2) تقييم متعدد النقاط والتقييم الأمثل القائم على FFT ، والوقت على حد سواء. ها هي نتائجي:

>>> import binary_fft as b
>>> import time, random
>>> f = b.BinaryField(1033)
>>> poly = [random.randrange(1024) for i in range(1024)]
>>> a = time.time(); x1 = b._simple_ft(f, poly); time.time() - a
0.5752472877502441
>>> a = time.time(); x2 = b.fft(f, poly, list(range(1024))); time.time() - a
0.03820443153381348

ومع زيادة حجم كثير الحدود ، فإن التطبيق الساذج (_simple_ft) يصبح أبطأ بكثير من FFT:

>>> f = b.BinaryField(2053)
>>> poly = [random.randrange(2048) for i in range(2048)]
>>> a = time.time(); x1 = b._simple_ft(f, poly); time.time() - a
2.2243144512176514
>>> a = time.time(); x2 = b.fft(f, poly, list(range(2048))); time.time() - a
0.07896280288696289

وفويلا ، لدينا طريقة فعالة وقابلة للتطوير للتقييم متعدد النقاط واستيفاء كثيرات الحدود. إذا أردنا استخدام FFTs لاستعادة البيانات المشفرة للمحو أينما كنا مفقود بعض القطع ، ثم الخوارزميات لذلك موجودة أيضا، على الرغم من أنها أقل كفاءة إلى حد ما من مجرد إجراء FFT واحد. يتمتع!

تم نشر هذه المقالة في الأصل باسم "تحويلات فورييه السريعة"

أفلاطون. Web3 مُعاد تصوره. تضخيم ذكاء البيانات.
انقر هنا للوصول.

المصدر: https://hackernoon.com/fast-fourier-transform-scaling-multi-point-evaluation؟source=rss