التعقيد الحسابي للعمليات الرياضية

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 91 صور
الموسوعة الحرة
رسوم بيانية للدوال شائعة الاستخدام في تحليل الخوارزميات، توضح عدد العملياتشمال{\displaystyle N}مقارنة بحجم الإدخالن{\displaystyle n}لكل وظيفة

تسرد الجداول التالية التعقيد الحسابي لخوارزميات مختلفة للعمليات الرياضية الشائعة .

هنا، تشير التعقيدية إلى التعقيد الزمني لإجراء العمليات الحسابية على آلة تورينج متعددة الأشرطة . [ 1 ] انظر إلى ترميز Big O للحصول على شرح للترميز المستخدم.

ملاحظة: نظراً لتنوع خوارزميات الضرب،م(ن){\displaystyle M(n)}يمثل ما يلي مدى تعقيد خوارزمية الضرب المختارة.

الدوال الحسابية

يسرد هذا الجدول مدى تعقيد العمليات الحسابية على الأعداد الصحيحة.

عمليةمدخلالناتجالخوارزميةتعقيد
إضافةاثنينن{\displaystyle n}أرقام مكونة من خاناتواحدن+1{\displaystyle n+1}رقم مكون من خاناتإضافة كتاب مدرسي مع إمكانية الحمليا(ن){\displaystyle O{\mathord {\left(n\right)}}}
الطرحاثنينن{\displaystyle n}أرقام مكونة من خاناتواحدن{\displaystyle n}رقم مكون من خاناتطرح الكتب المدرسية باستخدام الاستلافيا(ن){\displaystyle O{\mathord {\left(n\right)}}}
الضرباثنينن{\displaystyle n}أرقام مكونة من خاناتواحد2ن{\displaystyle 2n}رقم مكون من خاناتكتاب المدرسة عن الضرب الطويليا(ن2){\displaystyle O{\mathord {\left(n^{2}\right)}}}
خوارزمية كاراتسوبايا(ن1.585){\displaystyle O{\mathord {\left(n^{1.585}\right)}}}
عملية ضرب توم-كوك ثلاثية الاتجاهاتيا(ن1.465){\displaystyle O{\mathord {\left(n^{1.465}\right)}}}
ك{\displaystyle k}الضرب بطريقة توم-كوكيا(نسجل⁡(2ك-1)سجل⁡ك){\displaystyle O{\mathord {\left(n^{\frac {\log(2k-1)}{\log k}}\right)}}}
Toom–Cook متعدد المستويات (Knuth 4.3.3-T) [ 2 ]يا(ن22سجل⁡نسجل⁡ن){\displaystyle O{\mathord {\left(n\,2^{\sqrt {2\log n}}\,\log n\right)}}}
خوارزمية شونهيج-ستراسنيا(نسجل⁡نسجل⁡سجل⁡ن){\displaystyle O{\mathord {\left(n\log n\log \log n\right)}}}
خوارزمية هارفي هوفن [ 3 ] [ 4 ]يا(نسجل⁡ن){\displaystyle O(n\log n)}
قسماثنينن{\displaystyle n}أرقام مكونة من خاناتواحدن{\displaystyle n}رقم مكون من خاناتالقسمة المطولة في الكتب المدرسيةيا(ن2){\displaystyle O{\mathord {\left(n^{2}\right)}}}
تقسيم بورنيكل - زيغلر بتقسيم الفرق إلى 5يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
تقسيم نيوتن-رافسونيا(م(ن)){\displaystyle O(M(n))}
الجذر التربيعيواحدن{\displaystyle n}رقم مكون من خاناتواحدن/2{\displaystyle n/2}رقم مكون من خاناتطريقة نيوتنيا(م(ن)){\displaystyle O(M(n))}
الأس المعيارياثنينن{\displaystyle n}الأعداد الصحيحة المكونة من خانة واحدة وك{\displaystyle k}الأس ذو البتواحدن{\displaystyle n}عدد صحيح مكون من خاناتالضرب والاختزال المتكرريا(م(ن)2ك){\displaystyle O{\mathord {\left(M(n)\,2^{k}\right)}}}
الأسس بالتربيعيا(م(ن)ك){\displaystyle O(M(n)\,k)}
الأسس مع اختزال مونتغمرييا(م(ن)ك){\displaystyle O(M(n)\,k)}

في نماذج حسابية أقوى، وتحديداً آلة المؤشر وبالتالي أيضاً آلة الوصول العشوائي ذات التكلفة الموحدة، من الممكن ضرب عددين من n بت في وقت O ( n ). [ 6 ]

الدوال الجبرية

هنا نتناول العمليات على كثيرات الحدود، حيث يرمز n إلى درجتها؛ أما بالنسبة للمعاملات، فنستخدم نموذج التكلفة الموحدة ، متجاهلين عدد البتات في العدد. عمليًا، يعني هذا أننا نفترض أنها أعداد صحيحة على مستوى الآلة. في هذا القسمم(ن){\displaystyle M(n)}يشير إلى الوقت اللازم لضرب كثيرتي حدود من الدرجة على الأكثرن{\displaystyle n}[ 7 ] : 242​

عمليةمدخلالناتجالخوارزميةتعقيد
التقييم متعدد الحدودكثير حدود واحد من الدرجةن{\displaystyle n}بمعاملات صحيحةرقم واحدالتقييم المباشرΘ(ن){\displaystyle \Theta (n)}
طريقة هورنرΘ(ن){\displaystyle \Theta (n)}
التقييم متعدد النقاط متعدد الحدودكثير حدود واحد من الدرجة أقل منن{\displaystyle n}بمعاملات صحيحة ون{\displaystyle n}الأرقام كنقاط تقييمن{\displaystyle n}أرقامالتقييم المباشرΘ(ن2){\displaystyle \Theta (n^{2})}
التقييم السريع متعدد النقاط [ 7 ] : 295يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
القاسم المشترك الأكبر لكثير الحدود (علىZ[x]{\displaystyle \mathbb {Z} [x]}أوF[x]{\displaystyle F[x]})كثيرتا حدود من الدرجةن{\displaystyle n}بمعاملات صحيحةكثير حدود واحد من الدرجة على الأكثرن{\displaystyle n}خوارزمية إقليديةيا(ن2){\displaystyle O{\mathord {\left(n^{2}\right)}}}
خوارزمية إقليدية سريعة [ 7 ] : 318 (ليمر [ 7 ] : 324 )يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}

وظائف خاصة

تم تقديم العديد من الطرق الواردة في هذا القسم في كتاب بورواين وبورواين. [ 8 ]

الدوال الأولية

تُبنى الدوال الأولية من خلال تركيب العمليات الحسابية ، والدالة الأسية (خبرة{\displaystyle \exp }), اللوغاريتم الطبيعي (سجل{\displaystyle \log }), الدوال المثلثية (الخطيئة،كوس{\displaystyle \sin ,\cos }، ومعكوساتها. تعقيد الدالة الأولية مكافئ لتعقيد معكوسها، لأن جميع الدوال الأولية تحليلية ، وبالتالي قابلة للعكس باستخدام طريقة نيوتن. على وجه الخصوص، إذا كان أي منهماخبرة{\displaystyle \exp }أوسجل{\displaystyle \log }في المجال المركب، يمكن حسابها ببعض التعقيد، ثم يكون هذا التعقيد قابلاً للتحقيق لجميع الدوال الأولية الأخرى.

فيما يلي، الحجمن{\displaystyle n}يشير إلى عدد أرقام الدقة التي سيتم تقييم الدالة عندها.

الخوارزميةقابلية التطبيقتعقيد
متسلسلة تايلور ؛ اختزال الوسائط المتكررة (مثلاًخبرة⁡(2x)=[خبرة⁡(x)]2{\displaystyle \exp(2x)=[\exp(x)]^{2}}) والجمع المباشرخبرة،سجل،الخطيئة،كوس،دالة الظل العكسي{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }يا(م(ن)ن1/2){\displaystyle O{\mathord {\left(M(n)n^{1/2}\right)}}}
متسلسلة تايلور؛ تسريع قائم على تحويل فورييه السريعخبرة،سجل،الخطيئة،كوس،دالة الظل العكسي{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }يا(م(ن)ن1/3(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)n^{1/3}(\log n)^{2}\right)}}}
متسلسلة تايلور؛ خوارزمية تقسيم ثنائي + خوارزمية انفجار البتات [ 9 ]خبرة،سجل،الخطيئة،كوس،دالة الظل العكسي{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }يا(م(ن)(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}
التكرار الحسابي الهندسي [ 10 ]خبرة،سجل،الخطيئة،كوس،دالة الظل العكسي{\displaystyle \exp ,\log ,\sin ,\cos ,\arctan }يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}

من غير المعروف ما إذا كانيا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}يمثل هذا التعقيد الأمثل للدوال الأولية. وأفضل حد أدنى معروف هو الحد التافه. Ω{\displaystyle \Omega }(م(ن)){\displaystyle (M(n))}.

الدوال غير الأولية

وظيفةمدخلالخوارزميةتعقيد
دالة غاماعدد صحيحن{\displaystyle n}تقريب متسلسلة لدالة غاما غير الكاملةيا(م(ن)ن1/2(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}}
عدد نسبي ثابتمتسلسلة فرط هندسيةيا(م(ن)(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}
م/24{\displaystyle m/24}، لم{\displaystyle m}عدد صحيح.التكرار الحسابي الهندسييا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
دالة فوق هندسيةصFq{\displaystyle {}_{p}\!F_{q}}ن{\displaystyle n}رقم مكون من خانات(كما هو موضح في كتاب بورواين وبورواين)يا(م(ن)ن1/2(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)n^{1/2}(\log n)^{2}\right)}}}
عدد نسبي ثابتمتسلسلة فرط هندسيةيا(م(ن)(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}

الثوابت الرياضية

يوضح هذا الجدول مدى تعقيد حساب التقريبات للثوابت المعطاة لـن{\displaystyle n}الأرقام الصحيحة.

ثابتالخوارزميةتعقيد
النسبة الذهبية ،ϕ{\displaystyle \phi }طريقة نيوتنيا(م(ن)){\displaystyle O(M(n))}
الجذر التربيعي للعدد 2 ،2{\displaystyle {\sqrt {2}}}طريقة نيوتنيا(م(ن)){\displaystyle O(M(n))}
عدد أويلر ،هـ{\displaystyle e}التقسيم الثنائي لسلسلة تايلور للدالة الأسيةيا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
انعكاس نيوتن للوغاريتم الطبيعييا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
باي ،π{\displaystyle \pi }التقسيم الثنائي لسلسلة arctan في صيغة ماشينيا(م(ن)(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}[ 11 ]
خوارزمية جاوس-ليجندريا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}[ 11 ]
ثابت أويلر ،γ{\displaystyle \gamma }طريقة سويني (التقريب بدلالة التكامل الأسي )يا(م(ن)(سجل⁡ن)2){\displaystyle O{\mathord {\left(M(n)(\log n)^{2}\right)}}}

نظرية الأعداد

تُدرس الخوارزميات الخاصة بالحسابات النظرية للأعداد في نظرية الأعداد الحاسوبية .

عمليةمدخلالناتجالخوارزميةتعقيد
القاسم المشترك الأكبراثنينن{\displaystyle n}الأعداد الصحيحة المكونة من خانة واحدةعدد صحيح واحد يحتوي على أكثر منن{\displaystyle n}أرقامخوارزمية إقليديةيا(ن2){\displaystyle O{\mathord {\left(n^{2}\right)}}}
خوارزمية القاسم المشترك الأكبر الثنائييا(ن2){\displaystyle O{\mathord {\left(n^{2}\right)}}}
خوارزمية القاسم المشترك الأكبر الثنائي k -ary الأيسر/الأيمن [ 12 ]يا(ن2سجل⁡ن){\displaystyle O{\mathord {\left({\frac {n^{2}}{\log n}}\right)}}}
خوارزمية ستيله-زيمرمان [ 13 ]يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
خوارزمية النزول الإقليدي المتحكم بها بواسطة شونهاج [ 14 ]يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
رموز جاكوبياثنينن{\displaystyle n}الأعداد الصحيحة المكونة من خانة واحدة0{\displaystyle 0}،-1{\displaystyle -1}أو1{\displaystyle 1}خوارزمية النزول الإقليدي المتحكم بها بواسطة شونهاج [ 15 ]يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
خوارزمية ستيله-زيمرمان [ 16 ]يا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}
مضروبعدد صحيح موجب أقل منم{\displaystyle m}واحديا(مسجل⁡م){\displaystyle O(m\log m)}عدد صحيح مكون من خاناتالضرب من الأسفل إلى الأعلىيا(م(م2)سجل⁡م){\displaystyle O{\mathord {\left(M\left(m^{2}\right)\log m\right)}}}
تقسيم ثنائييا(م(مسجل⁡م)سجل⁡م){\displaystyle O(M(m\log m)\log m)}
تهيئة العوامل الأولية لـم{\displaystyle m}يا(م(مسجل⁡م)سجل⁡سجل⁡م){\displaystyle O(M(m\log m)\log \log m)}, [ 17 ]يا(م(مسجل⁡م)){\displaystyle O(M(m\log m))}[ 1 ]
اختبار الأسبقيةأن{\displaystyle n}عدد صحيح مكون من خاناتصواب أم خطأاختبار AKS الأولييا(ن6+o(1)){\displaystyle O{\mathord {\left(n^{6+o(1)}\right)}}}[ 18 ] [ 19 ]يا(ن3){\displaystyle O(n^{3})}، بافتراض صحة تخمين أغراوال
إثبات أولية المنحنى الإهليلجييا(ن4+ε){\displaystyle O{\mathord {\left(n^{4+\varepsilon }\right)}}}بشكل استدلالي [ 20 ]
اختبار بايلي-PSW للأولييةيا(ن2+ε){\displaystyle O{\mathord {\left(n^{2+\varepsilon }\right)}}}[ 21 ] [ 22 ]
اختبار ميلر-رابين للأولويةيا(كن2+ε){\displaystyle O{\mathord {\left(kn^{2+\varepsilon }\right)}}}[ 23 ]
اختبار سولوفاي-ستراسين للبدائيةيا(كن2+ε){\displaystyle O{\mathord {\left(kn^{2+\varepsilon }\right)}}}[ 23 ]
تحليل الأعداد الصحيحة إلى عواملها الأوليةأب{\displaystyle b}عدد صحيح مُدخل ذو بتمجموعة من العواملغربال حقل الأرقام العاميا((1+ε)ب){\displaystyle O{\mathord {\left((1+\varepsilon )^{b}\right)}}}[ ملاحظة 1 ]
خوارزمية شوريا(م(ب)ب){\displaystyle O(M(b)b)}، على حاسوب كمومي

جبر المصفوفات

تفترض أرقام التعقيد التالية أن العمليات الحسابية مع العناصر الفردية لها تعقيد O (1)، كما هو الحال مع العمليات الحسابية ذات الدقة الثابتة أو العمليات على حقل محدود .

عمليةمدخلالناتجالخوارزميةتعقيد
ضرب المصفوفاتاثنينن×ن{\displaystyle n\times n}المصفوفاتواحدن×ن{\displaystyle n\times n}مصفوفةضرب المصفوفات في الكتب المدرسيةيا(ن3){\displaystyle O(n^{3})}
خوارزمية ستراسنيا(ن2.807){\displaystyle O{\mathord {\left(n^{2.807}\right)}}}
خوارزمية كوبرسميث-وينوغراد ( الخوارزمية المجرة )يا(ن2.376){\displaystyle O{\mathord {\left(n^{2.376}\right)}}}
خوارزميات محسّنة شبيهة بخوارزمية CW [ 24 ] [ 25 ] [ 26 ] [ 27 ] ( خوارزميات مجرية )يا(نψ=2.3728596){\displaystyle O{\mathord {\left(n^{\psi =2.3728596}\right)}}}
واحدن×م{\displaystyle n\times m}مصفوفة، وواحدم×ص{\displaystyle m\times p}مصفوفةواحدن×ص{\displaystyle n\times p}مصفوفةضرب المصفوفات في الكتب المدرسيةيا(نمص){\displaystyle O(nmp)}
واحدن×⌈نك⌉{\displaystyle n\times \left\lceil n^{k}\right\rceil }مصفوفة، وواحد⌈نك⌉×ن{\displaystyle \left\lceil n^{k}\right\rceil \times n}مصفوفة، لبعضك≥0{\displaystyle k\geq 0}واحدن×ن{\displaystyle n\times n}مصفوفةالخوارزميات الواردة في [ 28 ]يا(نω(ك)+ϵ){\displaystyle O(n^{\omega (k)+\epsilon })}، حيث الحدود العليا علىω(ك){\displaystyle \omega (k)}تم تقديمها في [ 28 ]
قلب المصفوفةواحدن×ن{\displaystyle n\times n}مصفوفةواحدن×ن{\displaystyle n\times n}مصفوفةحذف جاوس-جوردانيا(ن3){\displaystyle O{\mathord {\left(n^{3}\right)}}}
خوارزمية ستراسنيا(ن2.807){\displaystyle O{\mathord {\left(n^{2.807}\right)}}}
خوارزمية كوبرسميث-وينوغراديا(ن2.376){\displaystyle O{\mathord {\left(n^{2.376}\right)}}}
خوارزميات سريعة لضرب المصفوفاتيا(نω){\displaystyle O({n^{\omega }})}ل 2.37≤ω<3{\displaystyle ~2.37\leq \omega <3}[ 29 ] ، القسم 11، الصفحات 413-414.
تحليل القيم المفردةواحدم×ن{\displaystyle m\times n}مصفوفةواحدم×م{\displaystyle m\times m}مصفوفة، واحدم×ن{\displaystyle m\times n}مصفوفة، وواحدن×ن{\displaystyle n\times n}مصفوفةخوارزمية ثنائية القطر و QRيا(م2ن){\displaystyle O{\mathord {\left(m^{2}n\right)}}} (م≥ن{\displaystyle m\geq n})
واحدم×ن{\displaystyle m\times n}مصفوفة، واحدن×ن{\displaystyle n\times n}مصفوفة، وواحدن×ن{\displaystyle n\times n}مصفوفةخوارزمية ثنائية القطر و QRيا(من2){\displaystyle O{\mathord {\left(mn^{2}\right)}}} (م≤ن{\displaystyle m\leq n})
تحليل QRواحدم×ن{\displaystyle m\times n}مصفوفةواحدم×ن{\displaystyle m\times n}مصفوفة، وواحدن×ن{\displaystyle n\times n}مصفوفةالخوارزميات في [ 30 ] عن طريق ضرب المصفوفات السريعيا(من1+14-ω){\displaystyle O{\mathord {\left(mn^{1+{\frac {1}{4-\omega }}}\right)}}} (م≥ن{\displaystyle m\geq n})
المحددواحدن×ن{\displaystyle n\times n}مصفوفةرقم واحدتوسيع لابلاسيا(ن!){\displaystyle O(n!)}
خوارزمية خالية من القسمة [ 31 ]يا(ن4){\displaystyle O{\mathord {\left(n^{4}\right)}}}

يا(ن2.697263){\displaystyle O{\mathord {\left(n^{2.697263}\right)}}}[ 32 ]

تحليل LUيا(ن3){\displaystyle O(n^{3})}
خوارزمية بارايسيا(ن3){\displaystyle O{\mathord {\left(n^{3}\right)}}}
الضرب السريع للمصفوفات [ 33 ]يا(نω){\displaystyle O({n^{\omega }})}
الاستبدال الخلفيالمصفوفة المثلثيةن{\displaystyle n}حلولالاستبدال العكسي [ 34 ]يا(ن2){\displaystyle O{\mathord {\left(n^{2}\right)}}}
متعددة الحدود المميزةواحدن×ن{\displaystyle n\times n}مصفوفةدرجة واحدة-ن{\displaystyle n}متعدد الحدودخوارزمية فادييف-ليفريريا(نψ+1){\displaystyle O(n^{\psi +1})}
خوارزمية سامويلسون-بيركويتزيا(نψ+1){\displaystyle O(n^{\psi +1})}(عامل ثابت أصغر)
خوارزمية تحضير-ساروات [ 35 ] [ 36 ]يا(نψ+1/2+ن3){\displaystyle O(n^{\psi +1/2}+n^{3})}
عن طريق ضرب المصفوفات السريع [ 37 ]يا(نω){\displaystyle O({n^{\omega }})}

في عام 2005، أظهر هنري كوهن وروبرت كلاينبرغ وبالاز سيجيدي وكريس أومانز أن أيًا من التخمينين المختلفين سيؤدي إلى أن أس ضرب المصفوفات هو 2. [ 38 ]

التحويلات

تُستخدم الخوارزميات لحساب تحويلات الدوال (وخاصة التحويلات التكاملية ) على نطاق واسع في جميع مجالات الرياضيات، وخاصة التحليل ومعالجة الإشارات .

عمليةمدخلالناتجالخوارزميةتعقيد
تحويل فورييه المنفصلسلسلة بيانات محدودة بحجمن{\displaystyle n}مجموعة الأعداد المركبةكتاب مدرسييا(ن2){\displaystyle O(n^{2})}
تحويل فورييه السريعيا(نسجل⁡ن){\displaystyle O(n\log n)}

ملحوظات

  1. ↑ هذا الشكل من الزمن شبه الأسي صالح لجميعε>0{\displaystyle \varepsilon >0}ويمكن التعبير عن شكل أكثر دقة للتعقيد على النحو التالي:يا(خبرة⁡649ب(سجل⁡ب)23).{\displaystyle O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.}

مراجع

  1. 1 2 شونهاج، أ؛ جروتفيلد، AFW. فيتر، إي. (1994). الخوارزميات السريعة — تنفيذ آلة تورينج متعددة الأشرطة . BI Wissenschafts-Verlag. رقم ISBN 978-3-411-16891-0. OCLC 897602049 . 
  2. ↑ كنوت 1997
  3. ↑ هارفي، د.؛ فان دير هوفن، ج. (2021). "ضرب الأعداد الصحيحة في زمن O(n log n)" (ملف PDF) . حوليات الرياضيات . 193 (2): 563-617 . doi : 10.4007/annals.2021.193.2.4 . S2CID 109934776 . 
  4. ↑ كلاريش، إريكا (ديسمبر 2019). "الضرب يصل إلى الحد الأقصى للسرعة". مجلة الاتصالات ACM . 63 (1): 11-13 . doi : 10.1145/3371387 . S2CID 209450552 . 
  5. ^ بورنيكل، كريستوف. زيغلر، يواكيم (1998). قسم العودية السريعة . مؤسسة دراسات معاهد ماكس بلانك للمعلوماتية. ساربروكن: MPI Informatik Bibliothek & Dokumentation. او سي ال سي 246319574 . MPII-98-1-022. 
  6. ^ شونهاج ، أرنولد (1980). “آلات تعديل التخزين”. مجلة SIAM للحوسبة . 9 (3): 490-508 . دوى : 10.1137 / 0209036 .
  7. 1 2 3 4 فون زور جاثين، ج.؛ غيرهارد، J. (2013). جبر الكمبيوتر الحديث (الطبعة الثالثة ). مطبعة جامعة كامبريدج. رقم ISBN  9781139856065.
  8. ↑ بورواين، ج.؛ بورواين، ب. (1987). باي والمتوسط ​​الحسابي: دراسة في نظرية الأعداد التحليلية والتعقيد الحسابي . وايلي. ISBN 978-0-471-83138-9. OCLC 755165897 . 
  9. ↑ تشودنوفسكي، ديفيد؛ تشودنوفسكي، غريغوري (1988). "التقريبات والضرب المركب وفقًا لرامانوجان". رامانوجان مُعاد النظر فيه: وقائع مؤتمر الذكرى المئوية . دار النشر الأكاديمية. ص 375-472 . ISBN  978-0-01-205856-5.
  10. ↑ برنت، ريتشارد ب. (2014) [1975]. "طرق إيجاد الأصفار متعددة الدقة وتعقيد تقييم الدوال الأولية" . في تراوب، ج. ف. (محرر). التعقيد الحسابي التحليلي . إلسيفير. ص 151-176 . arXiv : 1004.3412 . ISBN  978-1-4832-5789-1.
  11. 1 2 ريتشارد ب. برنت (2020)، الأخوان بورواين، باي والاجتماع العام السنوي، وقائع سبرينغر في الرياضيات والإحصاء، المجلد 313، arXiv : 1802.07558 ، doi : 10.1007/978-3-030-36568-4 ، ISBN  978-3-030-36567-7، S2CID 214742997 
  12. ↑ سورنسون، ج. (1994). "خوارزميتان سريعتان لإيجاد القاسم المشترك الأكبر". مجلة الخوارزميات . 16 (1): 110-144 . doi : 10.1006/jagm.1994.1006 .
  13. ↑ كراندال، ر.؛ بوميرانس، س. (2005). "الخوارزمية 9.4.7 (ستيل-زيمرمان - القاسم المشترك الأكبر التكراري الثنائي)" . الأعداد الأولية - منظور حسابي ( الطبعة الثانية). سبرينغر. ص 471-473 . ISBN   978-0-387-28979-3.
  14. ↑ مولر ن (2008). "حول خوارزمية شونهاج وحساب القاسم المشترك الأكبر للأعداد الصحيحة شبه التربيعية" (ملف PDF) . رياضيات الحساب . 77 (261): 589-607 . Bibcode : 2008MaCom..77..589M . doi : 10.1090/S0025-5718-07-02017-0 .
  15. ↑ بيرنشتاين، دي جيه "خوارزميات أسرع لإيجاد الأعداد الصحيحة غير المربعة بتردد أسوأ الحالات" .
  16. ↑ برنت، ريتشارد ب.؛ زيمرمان، بول (2010). "أنيا(م(ن)سجل⁡ن){\displaystyle O(M(n)\log n)}خوارزمية رمز جاكوبي . ندوة نظرية الأعداد الخوارزمية الدولية . سبرينغر. الصفحات 83-95 . arXiv : 1004.2091 . doi : 10.1007/978-3-642-14518-6_10 . ISBN  978-3-642-14518-6. S2CID 7632655 . 
  17. ↑ بورواين، ب. (1985). "حول تعقيد حساب المضروب". مجلة الخوارزميات . 6 (3): 376-380 . doi : 10.1016/0196-6774(85)90006-9 .
  18. ↑ لينسترا الابن، إتش دبليو ؛ بوميرانس، كارل (2019). "اختبار الأعداد الأولية باستخدام الدورات الغاوسية" (ملف PDF) . مجلة الجمعية الرياضية الأوروبية . 21 (4): 1229-1269 . doi : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 .
  19. ↑ تاو، تيرينس (2010). "1.11 اختبار أولية AKS" . إبسيلون من المساحة، الجزء الثاني: صفحات من السنة الثالثة لمدونة رياضية . دراسات عليا في الرياضيات. المجلد 117. الجمعية الرياضية الأمريكية. الصفحات 82-86 . doi : 10.1090/gsm/117 . ISBN   978-0-8218-5280-4MR 2780010​​ 
  20. ↑ مورين، ف. (2007). "تطبيق النسخة السريعة تقاربياً من خوارزمية إثبات أولية المنحنى الإهليلجي". رياضيات الحساب . 76 (257): 493-505 . arXiv : math/0502097 . Bibcode : 2007MaCom..76..493M . doi : 10.1090/ S0025-5718-06-01890-4 . MR 2261033. S2CID 133193 .  
  21. ↑ بوميرانس، كارل ؛ سيلفريدج، جون ل .؛ واغستاف الابن، صموئيل س. (يوليو 1980). "الأعداد الأولية الزائفة حتى 25 × 10⁹ " ( ملف PDF) . رياضيات الحساب . 35 (151): 1003-1026 . doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 . 
  22. ↑ بايلي، روبرت؛ واغستاف الابن، صموئيل س. ( أكتوبر 1980). "أعداد لوكاس الأولية الزائفة" (ملف PDF) . رياضيات الحساب . 35 (152): 1391-1417 . doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406. MR 0583518 .  
  23. 1 2 مونير، لويس (1980). "تقييم ومقارنة خوارزميتين فعالتين لاختبار أولية الأعداد الاحتمالية" . علوم الحاسوب النظرية . 12 (1): 97-108 . doi : 10.1016/0304-3975(80)90007-9 . MR 0582244 . 
  24. ↑ ألمان، جوش؛ ويليامز، فيرجينيا فاسيليفسكا (2020)، "طريقة ليزر محسّنة وضرب مصفوفات أسرع"، الندوة السنوية الثانية والثلاثون لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA 2021) ، الصفحات 522-539 ، arXiv : 2010.05846 ، doi : 10.1137/1.9781611976465.32 ، ISBN  978-1-61197-646-5، S2CID 222290442 
  25. ↑ ديفي، أ.م.؛ ستوثرز، أ.ج. (2013)، "حد مُحسَّن لتعقيد ضرب المصفوفات"، وقائع الجمعية الملكية في إدنبرة ، 143أ (2): 351-370 ، doi : 10.1017/S0308210511001648 ، S2CID 113401430 
  26. ↑ فاسيلفسكا ويليامز، فيرجينيا (2014)، كسر حاجز كوبرسميث-وينوغراد: ضرب المصفوفات في زمن O(n 2.373 )
  27. ↑ لو غال، فرانسوا (2014)، "قوى الموترات وضرب المصفوفات السريع"، وقائع الندوة الدولية التاسعة والثلاثين حول الحساب الرمزي والجبري - ISSAC '14 ، ص 23، arXiv : 1401.7714 ، Bibcode : 2014arXiv1401.7714L ، doi : 10.1145/2608628.2627493 ، ISBN  9781450325011، S2CID 353236 
  28. 1 2 لو غال، فرانسوا؛ أوروتيا، فلورين (2018). "تحسين ضرب المصفوفات المستطيلة باستخدام قوى موتر كوبرسميث-وينوغراد". في تشوماج، أرتور (محرر). وقائع الندوة السنوية التاسعة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . جمعية الرياضيات الصناعية والتطبيقية. doi : 10.1137/1.9781611975031.67 . ISBN 978-1-61197-503-1. S2CID 33396059 . 
  29. ↑ بان، ف. (1984). "كيف يمكننا تسريع عملية ضرب المصفوفات؟". مجلة SIAM Review . 26 (3): 393-415 . doi : 10.1137/1026076 .
  30. ↑ نايت، فيليب أ. (مايو 1995). "الضرب السريع للمصفوفات المستطيلة وتحليل QR" . الجبر الخطي وتطبيقاته . 221 : 69-81 . doi : 10.1016/0024-3795(93)00230-w . ISSN 0024-3795 . 
  31. ↑ روت، ج. (2001). "خوارزميات خالية من القسمة للمحدد ومحدد بفاف: مناهج جبرية وتوافقية" (ملف PDF) . الرياضيات المتقطعة الحاسوبية . سبرينغر. ص 119-135 . ISBN  3-540-45506-X.
  32. ↑ كالتوفن، إريك؛ فيلار، جيل (2005). "حول تعقيد حساب المحددات" . التعقيد الحسابي . 13 ( 3-4 ): 91-130 . doi : 10.1007/s00037-004-0185-3 .
  33. ↑ بانش، جيمس ر.؛ هوبكروفت، جون إي. (1974). "تحليل المصفوفة المثلثية وعكسها عن طريق الضرب السريع للمصفوفات". رياضيات الحساب . 28 (125): 231-236 . doi : 10.1090/S0025-5718-1974-0331751-8 .
  34. ^ فرالي ، جي بي. بوريجارد، را (1987). الجبر الخطي ( الطبعة الثالثة). أديسون ويسلي. ص. 95. ردمك   978-0-201-15459-7.
  35. ↑ بريباراتا، إف بي؛ ساروات، دي في (أبريل 1978). "حد معالج متوازي مُحسَّن في عكس المصفوفة السريع" . رسائل معالجة المعلومات . 7 (3): 148-150 . doi : 10.1016/0020-0190(78)90079-0 .
  36. ↑ جاليل، تسفي؛ بان، فيكتور (16 يناير 1989). "التقييم المتوازي لمحدد ومعكوس المصفوفة" . رسائل معالجة المعلومات . 30 (1): 148-150 . doi : 10.1016/0020-0190(89)90173-7 .، حيثيا(ن3){\displaystyle O(n^{3})}يتم تقليص المدة
  37. ↑ نيجر ، فينسنت؛ بيرنيه، كليمنت (ديسمبر 2021). "الحساب الحتمي لكثير الحدود المميز في زمن ضرب المصفوفات" . مجلة التعقيد . 67. arXiv : 2010.04662 . doi : 10.1016/j.jco.2021.101572 .
  38. ↑ كوهن، هنري؛ كلاينبرغ، روبرت؛ سيجيدي، بالاز؛ أومانس، كريس (2005). "خوارزميات نظرية الزمر لضرب المصفوفات". وقائع الندوة السنوية السادسة والأربعين حول أسس علوم الحاسوب . معهد مهندسي الكهرباء والإلكترونيات. ص 379-388 . arXiv : math.GR/0511460 . doi : 10.1109/SFCS.2005.39 . ISBN  0-7695-2468-0. S2CID 6429088 . 

للمزيد من القراءة