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;
} |