c# - ユークリッド以外の最大公約数アルゴリズム

Question

基本的に、GCD (a、b) を見つけるための 3 つの異なるアルゴリズムを生成することになっています。

そのうちの 1 つは Euclid のバージョンなので、あと 2 つ必要です。

実装は C# で行われます。

提案？

Answer 1

これは代替手段の 1 つです。

public static int gcd(int x, int y) {
    int result = 0;

    if (x<0) {
        x = -x;
    }
    if (y<0) {
        y = -y;
    }
    if (x == 0){
        result = y; 
    }
    if (y == 0){
        result = x; 
    }
    for (int i = 1; i < x+1; i++) {

        if ( x % i == 0) {

            if ( y % i == 0) {
                result = i;
            }
        }   
    } 
    return result; }

Answer 2

これらは、最もよく使用される 3 つのアルゴリズムです。

public static uint FindGCDModulus(uint value1, uint value2)
{
while(value1 != 0 && value2 != 0)
{
        if (value1 > value2)
        {
                value1 %= value2;
        }
        else
        {
                value2 %= value1;
        }
}
return Math.Max(value1, value2);
   }

public static uint FindGCDEuclid(uint value1, uint value2)
  {
while(value1 != 0 && value2 != 0)
{
        if (value1 > value2)
        {
                value1 -= value2;
        }
        else
        {
                value2 -= value1;
        }
}
return Math.Max(value1, value2);
}

 public static uint FindGCDStein(uint value1, uint value2)
 {
if (value1 == 0) return value2;
if (value2 == 0) return value1;
if (value1 == value2) return value1;

bool value1IsEven = (value1 & 1u) == 0;
bool value2IsEven = (value2 & 1u) == 0;

if (value1IsEven && value2IsEven)
{
        return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
}
else if (value1IsEven && !value2IsEven)
{
        return FindGCDStein(value1 >> 1, value2);
}
else if (value2IsEven)
{
        return FindGCDStein(value1, value2 >> 1);
}
else if (value1 > value2)
{
        return FindGCDStein((value1 - value2) >> 1, value2);
}
else
{
        return FindGCDStein(value1, (value2 - value1) >> 1);
}
}

Answer 3

多かれ少なかれ直接的な方法は、Pick の定理から派生した次のコードです。

int gcd(int a, int b)
{

     if( a < 0)
     {
         a = -a;
     }

     if( b < 0)
     {
         b = -b;
     }

     if( a == b)
     {
          return a;
     }

     //swap the values to make the upper bound in the next loop minimal
     if( a > b)
     {
        int swap = a;
        a = b;
        b = swap;
     }
     

     int temp=0;

     for(int i=1; i<=a; i++)
     {
          temp += math.floor(b*i/a);
     }

     return (a*b + b - a + temp)/2;
}