خوارزميات GCD لعدادات صحيحة كبيرة

Question

أبحث عن معلومات حول خوارزميات حساب GCD بسرعة. خاصة، أود أن ألقي نظرة على تحقيقات ذلك.

الأكثر إثارة للاهتمام بالنسبة لي: - خوارزمية Lehmer GCD، - خوارزمية GCD تسريع، - خوارزمية كرى، - Nuth-Schonhage مع FFT. لدي معلومات تماما حول خوارزمية GCD المتسارعة، لقد رأيت فقط عدد قليل من المقالات حيث تم ذكرها كطريقة حساب GCD الأكثر فعالية وسريعة على المدخلات المتوسطة (~ 1000 بت)

تبدو صعبة للغاية بالنسبة لي أن أفهم من نظرية النظرية. يمكن لأي شخص أن يشارك الكود (الأفضل على C ++) مع تحقيق أي خوارزمية \ أجزاء من القائمة أو مشاركة أي تجربة للقيام بذلك. سأكون أقدر أيضا لأي معلومات وتعليقات ونصائح وأماكن النظر فيها. لدي فئة للعمل مع أعداد صحيحة كبيرة، لكن ليس لدي أي طرق للعمل معها. باستثناء، بالتأكيد، خوارزميات Euclid و Binary GCD، والتي تبدو واضحة بالنسبة لي الآن؛ لا توجد مشاكل معها. الشيء الرئيسي الذي أود الحصول عليه في النهاية: قانون تحقيق Lehmer GCD. (إنه أسهل من القائمة)

Answer 1

knuth يستكشف GCD عند فن برمجة الكمبيوتر ، المجلد 2، القسم 4.5.2. Knuth يعطي الخوارزمية E كطريقة أصلية ل Euclid، خوارزمية A كنسخة حديثة من خوارزمية Euclid، خوارزمية B كما الطريقة الثنائية وخلعات الخوارزمية L كوسيلة Lehmer، وكذلك خوارزمية Euclidean الممتدة في الخوارزمية X. أنا أبصف (مع رمز ) خوارزمية euclidean الأصلية ، خوارزمية euclidean الحديثة ، الخوارزمية الثنائية ، و خوارزمية Euclidean الممتدة في مدونتي.

p> هذه الورقة يعطي وصفا جيدا للعديد من إصدارات Schönhage الخوارزميات، بما في ذلك التعليمات البرمجية.

Answer 2

شكرا جزيلا لجابه user448810.أن الخوارزمية الثنائية مثالية بالنسبة لي وفقط بسرعة.أقوم بتحويلها إلى نموذج غير متكرر لحفظ المكالمات الذاكرة والعديدة. هنا هو تطبيقي لأجهزة Longnum Lib، وأضاف بعض Rems for Lines تختلف عن المشغلين / الوظائف القياسية

giveacodicetagpre.