التقييم متعدد الحدود

تقوم طريقة هورنر بتقييم متعدد الحدود باستخدام الأقواس المتكررة: $${\displaystyle {\begin{aligned}a_{0}+&a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\&=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}$$ تقلل هذه الطريقة عدد عمليات الضرب والجمع إلى عدد قليل جدًا${\displaystyle n}$

تُعد طريقة هورنر شائعة لدرجة أن عملية "الضرب والتجميع " مدرجة ضمن مجموعة تعليمات العديد من معالجات الكمبيوتر، مما يسمح بإجراء عمليات الجمع والضرب في خطوة واحدة مدمجة.

يمكن حساب كثيرات الحدود العشوائية بعدد عمليات أقل مما تتطلبه قاعدة هورنر إذا قمنا أولاً "بمعالجة مسبقة" للمعاملات.${\displaystyle a_{n},\dots ,a_{0}}$.

قدم موتزكين ^{[ 3 ]} مثالاً على ذلك ، حيث أشار إلى أن

${\displaystyle P(x)=x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}$

يمكن كتابتها على النحو التالي

${\displaystyle y=(x+\beta _{0})x+\beta _{1},\quad P(x)=(y+x+\beta _{2})y+\beta _{3},}$

حيث القيم${\displaystyle \beta _{0},\dots ,\beta _{3}}$يتم حسابها مسبقاً، بناءً على${\displaystyle a_{0},\dots ,a_{3}}$تستخدم طريقة موتزكين 3 عمليات ضرب فقط مقارنة بـ 4 عمليات ضرب لهورنر.

القيم لكل منها${\displaystyle \beta _{i}}$يمكن حسابها بسهولة عن طريق التوسيع${\displaystyle P(x)}$ومساواة المعاملات:

${\displaystyle {\begin{aligned}\beta _{0}&={\tfrac {1}{2}}(a_{3}-1),\quad &z&=a_{2}-\beta _{0}(\beta _{0}+1),\quad &\beta _{1}&=a_{1}-\beta _{0}z,\\\beta _{2}&=z-2\beta _{1},\quad &\beta _{3}&=a_{0}-\beta _{1}(\beta _{1}+\beta _{2}).\end{aligned}}}$

تقييم متعددة الحدود من الدرجة n${\displaystyle P(x)}$في نقاط متعددة${\displaystyle x_{1},\dots ,x_{m}}$يمكن القيام بذلك باستخدام${\displaystyle mn}$عمليات الضرب باستخدام طريقة هورنر${\displaystyle m}$مرات. باستخدام أسلوب المعالجة المسبقة المذكور أعلاه، يمكن تقليل ذلك بمقدار النصف؛ أي إلى${\displaystyle mn/2}$الضرب.

ومع ذلك، من الممكن تحسين الأداء وتقليل الوقت المطلوب إلى مجرد${\displaystyle O{\big (}(n+m)\log ^{2}(n+m){\big )}}$[ ^{5 ]} الفكرة هي تعريف كثيرتي حدود تكونان صفرًا في النصف الأول والثاني من النقاط على التوالي ^:${\displaystyle m_{0}(x)=(x-x_{1})\cdots (x-x_{n/2})}$و${\displaystyle m_{1}(x)=(x-x_{n/2+1})\cdots (x-x_{n})}$ثم نقوم بالحساب${\displaystyle R_{0}=P{\bmod {m}}_{0}}$و${\displaystyle R_{1}=P{\bmod {m}}_{1}}$باستخدام نظرية باقي كثير الحدود ، والتي يمكن القيام بها في${\displaystyle O(n\log n)}$الوقت باستخدام تحويل فورييه السريع . هذا يعني${\displaystyle P(x)=Q_{0}(x)m_{0}(x)+R_{0}(x)}$و${\displaystyle P(x)=Q_{1}(x)m_{1}(x)+R_{1}(x)}$عن طريق البناء، حيث${\displaystyle R_{0}}$و${\displaystyle R_{1}}$هي كثيرات حدود من الدرجة على الأكثر${\displaystyle n/2}$بسبب كيف${\displaystyle m_{0}}$و${\displaystyle m_{1}}$تم تعريفها، لدينا

${\displaystyle {\begin{aligned}R_{0}(x_{i})&=P(x_{i})\quad {\text{for }}i\leq n/2\quad {\text{and}}\\R_{1}(x_{i})&=P(x_{i})\quad {\text{for }}i>n/2.\end{aligned}}}$

وبالتالي لحساب${\displaystyle P}$على جميع${\displaystyle n}$التابع${\displaystyle x_{i}}$يكفي حساب كثيرات الحدود الأصغر${\displaystyle R_{0}}$و${\displaystyle R_{1}}$على كل نصف من النقاط. وهذا يعطينا خوارزمية فرق تسد مع${\displaystyle T(n)=2T(n/2)+n\log n}$وهذا يعني${\displaystyle T(n)=O(n(\log n)^{2})}$بحسب النظرية الرئيسية .

في حالة وجود بنية معينة للنقاط التي نرغب في تقييم كثيرات الحدود عندها، توجد طرق أبسط. على سبيل المثال، يقدم كنوت ^{[ 6 ]} القسم 4.6.4 طريقة لجدولة قيم كثيرات الحدود من النوع

${\displaystyle P(x_{0}+h),P(x_{0}+2h),\dots .}$

في الحالة التي${\displaystyle x_{1},\dots ,x_{m}}$إذا لم تكن هذه المعلومات معروفة مسبقًا، فقد قدم كيدلايا وأومانز ^{[ 7 ]} بنية بيانات لتقييم كثيرات الحدود على حقل منتهٍ بحجم${\displaystyle F_{q}}$في الوقت المناسب${\displaystyle (\log n)^{O(1)}(\log _{2}q)^{1+o(1)}}$لكل تقييم بعد بعض المعالجة المسبقة الأولية. وقد أظهر لارسون ^{[ 8 ]} أن هذا هو الأمثل بشكل أساسي.

الفكرة هي التحول${\displaystyle P(x)}$درجة علمية${\displaystyle n}$إلى متعدد الحدود متعدد المتغيرات${\displaystyle f(x_{1},x_{2},\dots ,x_{m})}$بحيث${\displaystyle P(x)=f(x,x^{d},x^{d^{2}},\dots ,x^{d^{m}})}$والدرجات الفردية لـ${\displaystyle f}$هو على الأكثر${\displaystyle d}$بما أن هذا قد انتهى${\displaystyle {\bmod {q}}}$، القيمة الأكبر${\displaystyle f}$يمكن أن يأخذ (على)${\displaystyle \mathbb {Z} }$) يكون${\displaystyle M=d^{m}(q-1)^{dm}}$باستخدام نظرية الباقي الصينية ، يكفي تقييم${\displaystyle f}$modulo different primes${\displaystyle p_{1},\dots ,p_{\ell }}$مع منتج على الأقل${\displaystyle M}$يمكن اعتبار كل عدد أولي تقريبًا${\displaystyle \log M=O(dm\log q)}$وعدد الأعداد الأولية المطلوبة،${\displaystyle \ell }$، وهو ما يقارب نفس الشيء. وبتكرار هذه العملية، يمكننا الحصول على أعداد أولية صغيرة مثل${\displaystyle \log \log q}$وهذا يعني أنه يمكننا الحساب والتخزين${\displaystyle f}$على جميع القيم الممكنة في${\displaystyle T=(\log \log q)^{m}}$الزمان والمكان. إذا أخذنا${\displaystyle d=\log q}$، نحصل${\displaystyle m={\tfrac {\log n}{\log \log q}}}$لذا فإن متطلبات الوقت/المساحة هي${\displaystyle n^{\frac {\log \log q}{\log \log \log q}}.}$

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

ومن أنواع كثيرات الحدود المثيرة للاهتمام بشكل خاص القوى مثل${\displaystyle x^{n}}$يمكن دائمًا حساب هذه كثيرات الحدود في${\displaystyle O(\log n)}$العمليات. لنفترض، على سبيل المثال، أننا بحاجة إلى حساب${\displaystyle x^{16}}$يمكننا ببساطة أن نبدأ بـ${\displaystyle x}$واضرب في${\displaystyle x}$للحصول على${\displaystyle x^{2}}$ثم يمكننا ضرب ذلك في نفسه لنحصل على${\displaystyle x^{4}}$وهكذا دواليك للحصول على${\displaystyle x^{8}}$و${\displaystyle x^{16}}$في أربع عمليات ضرب فقط. قوى أخرى مثل${\displaystyle x^{5}}$ويمكن حسابها بكفاءة مماثلة عن طريق الحساب أولاً${\displaystyle x^{4}}$عن طريق عمليتي ضرب ثم الضرب في${\displaystyle x}$.

الطريقة الأكثر فعالية لحساب قوة معينة${\displaystyle x^{n}}$يتم توفيرها عن طريق الأسس المتسلسلة للجمع . ومع ذلك، يتطلب هذا تصميم خوارزمية محددة لكل أس، والحسابات اللازمة لتصميم هذه الخوارزميات صعبة ( NP-complete ^{[ 9 ]} )، لذلك يُفضل عمومًا الأسس عن طريق التربيع لإجراء حسابات فعالة.

غالباً ما تظهر كثيرات الحدود في شكل مختلف عن الشكل المعروف${\displaystyle a_{n}x^{n}+\dots +a_{1}x+a_{0}}$بالنسبة لكثيرات الحدود في صيغة تشيبيشيف، يمكننا استخدام خوارزمية كلينشو . أما بالنسبة لكثيرات الحدود في صيغة بيزير، فيمكننا استخدام خوارزمية دي كاستيلجو ، وبالنسبة لدوال بي-سبلاين، توجد خوارزمية دي بور .

إن حقيقة إمكانية حساب بعض كثيرات الحدود بسرعة أكبر بكثير من "كثيرات الحدود العامة" تطرح السؤال التالي: هل يمكننا تقديم مثال على كثيرة حدود بسيطة لا يمكن حسابها في وقت أقل بكثير من درجتها؟ وقد أثبت فولكر ستراسن ^{[ 10 ]} أن كثيرة الحدود

${\displaystyle P(x)=\sum _{k=0}^{n}2^{2^{kn^{3}}}x^{k}}$

لا يمكن تقييمها بأقل من${\displaystyle {\tfrac {1}{2}}n-2}$الضرب و${\displaystyle n-4}$عمليات الجمع. على الأقل، يظل هذا الحد قائماً إذا سُمح فقط بالعمليات من تلك الأنواع، مما يؤدي إلى ما يسمى "سلسلة متعددة الحدود ذات طول${\displaystyle <n^{2}/\log n}$".

تتميز متعددة الحدود التي قدمها ستراسن بمعاملات كبيرة جدًا، ولكن باستخدام الطرق الاحتمالية، يمكن إثبات وجود متعددات حدود أخرى بمعاملات تتكون من أصفار وواحدات فقط، بحيث يتطلب حسابها على الأقل${\displaystyle \Omega (n/\log n)}$عمليات الضرب. ^{[ 11 ]}

أما بالنسبة لكثيرات الحدود البسيطة الأخرى، فإن تعقيدها غير معروف.${\displaystyle (x+1)(x+2)\cdots (x+n)}$يُعتقد أنه لا يمكن حسابه في وقت${\displaystyle (\log n)^{c}}$لأي${\displaystyle c}$ويدعم ذلك حقيقة أنه إذا أمكن حسابها بسرعة، فإنه يمكن حساب تحليل الأعداد الصحيحة في وقت متعدد الحدود، مما يؤدي إلى كسر نظام التشفير RSA . ^{[ 12 ]}