อัลกอริทึม Stein สำหรับหา GCD ใน C++

โจทย์

Stein's Algorithm ใช้สำหรับหา GCD ของตัวเลข เนื่องจากมันคำนวณ greatest common divisor ของจำนวนเต็มไม่ติดลบสองจำนวน มันแทนที่การหารด้วยการเลื่อนบิต การเปรียบเทียบ และการลบ หาก a และ b ทั้งคู่เป็น 0 gcd คือศูนย์ gcd(0, 0) = 0 อัลกอริทึมสำหรับ GCD(a,b) ดังนี้

อัลกอริทึม

เริ่ม
ขั้นตอน 1: ตรวจสอบ ถ้า a และ b ทั้งคู่เป็น 0 gcd คือศูนย์ gcd(0, 0) = 0
ขั้นตอน 2: แล้ว gcd(a, 0) = a และ gcd(0, b) = b เพราะทุกอย่างหาร 0 ลงตัว
ขั้นตอน 3: ตรวจสอบ ถ้า a และ b ทั้งคู่เป็นเลขคู่ gcd(a, b) = 2*gcd(a/2, b/2) เพราะ 2 เป็นตัวหารร่วม การคูณด้วย 2 สามารถทำด้วย bitwise shift operator
ขั้นตอน 4: ถ้า a เป็นเลขคู่และ b เป็นเลขคี่ gcd(a, b) = gcd(a/2, b) ทำนองเดียวกัน ถ้า a เป็นเลขคี่และ b เป็นเลขคู่ gcd(a, b) = gcd(a, b/2) เพราะ 2 ไม่ใช่ตัวหารร่วม
ขั้นตอน 5: ถ้า a และ b ทั้งคู่เป็นเลขคี่ gcd(a, b) = gcd(|a-b|/2, b) สังเกตว่าความต่างของเลขคี่สองจำนวนเป็นเลขคู่
ขั้นตอน 6: ทำซ้ำขั้นตอน 3-5 จนกว่า a = b หรือ a = 0
สิ้นสุด

ในมุมมองของอัลกอริทึมด้านบนสำหรับคำนวณ GCD ของ 2 จำนวน โค้ด C++ ด้านล่างถูกเขียนขึ้นดังนี้

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
int funGCD(int x, int y){
  if (x == 0)
    return y;
  if (y == 0)
    return x;
  int k;
  for (k = 0; ((x | y) & 1) == 0; ++k){
    x >>= 1;
    y >>= 1;
  }
  while ((x & 1) == 0)
    x >>= 1;
  do {
    while ((y & 1) == 0)
      y >>= 1;
    if (x > y)
      swap(x, y); // Swap u and v.
    y = (y - x);
  } while (y != 0);
  return x << k;
}
int main(){
  int a = 24, b = 18;
  printf("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
  return 0;
}

ผลลัพธ์

สุดท้าย GCD ของตัวเลขที่ให้มา 24 และ 18 คำนวณได้เป็น 6 โดยใช้ Stein's Algorithm ดังนี้

Calculated GCD of numbers (24,18) is= 6