الگوریتم جی‌سی‌دی دودویی

الگوریتم GCD (بزرگترین مقسوم علیه مشترک) دودویی، که الگوریتم اشتاین هم نامیده می‌شود، الگوریتمی است که بزرگترین مقسوم علیه مشترک دو عدد صحیح نا منفی را محاسبه می‌کند. این الگوریتم یک معیار اندازه‌گیری کارآیی بر الگوریتم اقلیدسی باستانی با جابه‌جایی مقسوم علیه‌ها و مضرب‌ها با شیفت دادن (که به هنگام نمایش دودویی توسط کامپیوترهای مدرن کم هزینه‌تر هست)، به‌دست می آورد. این الگوریتم به ویژه برای سیستم عامل‌های نهانی که پردازنده‌ای برای پشتیبانی مستقیم تقسیم ندارند، حیاتی است. هرچند در ابتدا ژوزف اشتاین فیزیکدان و برنامه‌نویس اسراییلی در سال ۱۹۶۷، این الگوریتم را منتشر کرد،J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, Vol. 1, No. 3, pp. 397–405, 1967.  ممکن است در قرن یکم چین شناخته شده باشد.دانلد کنوت, هنر برنامه‌نویسی رایانه, Volume 2: Seminumerical Algorithms (3rd Edition). Addison-Wesley.
پیوند=https://en.wikipedia.org/wiki/File:Binary_GCD_algorithm_visualisation.svg|بندانگشتی|تجسم استفاده از الگوریتم GCD دودویی برای یافتن بزرگترین مقسوم علیه مشترک (GCD) اعداد ۳۶ و ۲۴. بنابراین، GCD برابر است با ۲۲ × ۳ = ۱۲.

 الگوریتم 
الگوریتم، مشکل پیدا کردن GCD را با اعمال کردن مکرر این اصل‌ها، کاهش می‌دهد:
 gcd(۰، v) = v، چون هر عددی بر صفر تقسیم‌پذیر است، و v بزرگترین عددی است که بر v تقسیم‌پذیر است. به همین ترتیب، gcd(u، ۰) = u. هرچند معمول نیست اما gcd(۰، ۰) = ۰.
 اگر u و v هر دو زوج باشند، بنابراین (gcd(u، v) = ۲.gcd(u/۲، v/۲، چون ۲ مقسوم علیه مشترک است.
 اگر u زوج و v فرد باشد، بنابراین (gcd(u، v) = gcd(u/۲،  v، چون ۲ مقسوم علیه مشترک نیست. به همین ترتیب اگر u فرد و v زوج باشد، بنابراین (gcd(u، v) = gcd(u،  v/۲. 
 اگر v و u هر دو فرد باشند و u ≥ v، بنابراین (gcd(u، v) = gcd((u − v)/۲،  v. و اگر v و u هر دو فرد باشند و u < v، بنابراین (gcd(u، v) = gcd((v − u)/۲،  u. این‌ها ترکیبی از یک مرحله ساده الگوریتم اقلیدی که در هر مرحله از تفریق استفاده کرده، و کاربرد سه مرحله بالا هستند. نتیجه تقسیم بر ۲ یک عدد صحیح است چون تفریق ۲ عدد فرد، زوج است.In fact, the algorithm might be improved by the observation that if both u and v are odd, then exactly one of u + v or u−v must be divisible by four. Specifically, assuming u ≥ v, if ((u xor v) and 2) = 2, then gcd(u, v) = gcd((u + v)/4, v), and otherwise gcd(u, v) = gcd((u − v)/4, v).
 مراحل ۲ و ۲ را تکرار کن (همیشه یک آرگومان فرد برگردانده می‌شود)، تا u = v یا (یک مرحله بیش‌تر) تا u = ۰. در غیر این صورت GCD برابر با ۲kv، است، که در آن k تعداد فاکتورهای مشترک ۲ هست که در مرحله ۲ پیدا شد.

از آنجایی که این تعریف بازگشتی ادامه‌دار است، می‌توان از یک حلقه به جای بازگشت آن استفاده کرد.

 منابع 



رده:الگوریتم‌ها
رده:الگوریتم‌های نظریه اعداد
رده:مقاله‌های ایجادشده توسط ایجادگر