ما هي أسرع طريقة للتحقق مما إذا كان هناك رقمان محددان؟

Question

إحدى الطرق هي حساب gcd وتحقق مما إذا كان 1.

هل هناك طريقة أسرع؟

Answer 1

الخوارزمية الإقليدية (يحسب gcd) سريع جدا.عندما يتم سحب رقمين بشكل عشوائي بشكل عشوائي من [1, n], ، متوسط ​​عدد الخطوات لحسابها gcd يكون O(log n).متوسط ​​وقت الحساب المطلوب لكل خطوة هو تربيعي في عدد الأرقام.

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

Answer 2

إذا كنت تعمل على جهاز، فإن القسم / البقية أكثر تكلفة بكثير من التحولات، والنظر GCD ثنائي.