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

الگوریتم 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

↑ J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, Vol. 1, No. 3, pp. 397–405, 1967. ISSN 0021-9991
↑ دانلد کنوت, هنر برنامه‌نویسی رایانه, Volume 2: Seminumerical Algorithms (3rd Edition). Addison-Wesley.
↑ 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).

پیوند به بیرون ویرایش

http://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&oldid=459414644

[1] J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, Vol. 1, No. 3, pp. 397–405, 1967. ISSN 0021-9991

[Knuth98-2] دانلد کنوت, هنر برنامه‌نویسی رایانه, Volume 2: Seminumerical Algorithms (3rd Edition). Addison-Wesley.

[3] 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).

[۱]

[۲]

[۳]