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

الگوریتم 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. این‌ها ترکیبی از یک مرحله ساده الگوریتم اقلیدی که در هر مرحله از تفریق استفاده کرده، و کاربرد سه مرحله بالا هستند. نتیجه تقسیم بر ۲ یک عدد صحیح است چون تفریق ۲ عدد فرد، زوج است.
 مراحل ۲ و ۲ را تکرار کن (همیشه یک آرگومان فرد برگردانده می‌شود)، تا u = v یا (یک مرحله بیش‌تر) تا u = ۰. در غیر این صورت GCD برابر با ۲kv، است، که در آن k تعداد فاکتورهای مشترک ۲ هست که در مرحله ۲ پیدا شد.

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

منابع 
http://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=459414644

پیوند به بیرون 
http://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=459414644

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