Math::gcdNum_t Math::Gcd1(Math::gcdNum_t x, Math::gcdNum_t y)
{
????//y, x%y順序不能錯；
????return y ? Gcd1(y, x % y) : x;
}
? Math::gcdNum_t Math::Gcd2(Math::gcdNum_t x, Math::gcdNum_t y)
{
????//與Gcd1相同的方式，但由于x%y計算速度較x-y要慢，但效果相同，所以換用x - y
????// 但用減法和除法不同的是，比如和，%20=10，-20=70，也就是-4×=10
????// 也就是說迭代次數較Gcd1而言通常是增加了。
????return y ? Gcd1(y, x - y) : x;
}
? Math::gcdNum_t Math::Gcd3(Math::gcdNum_t x, Math::gcdNum_t y)
{
????if(x < y)
????????return Gcd3(y, x);
????if(y == 0)
????????return x;
????else
????{
????????if(IsEven(x))
????????{
????????????if(IsEven(y))
????????????????return (Gcd3(x >> 1, y >> 1) << 1);
????????????else
????????????????return Gcd3(x >> 1, y);
????????}
????????else
????????{
????????????if(IsEven(y))
????????????????return Gcd3(x, y >> 1);
????????????else
????????????????return Gcd3(y, x - y);
????????}
????}
}
? bool Math::IsEven(Math::gcdNum_t x)
{
????return !(bool)x & 0x0001;
} |