关于Rational类的约分

问题描述：

老师好！
我的理解这里约分其实就是求分子和分母的最大公约数，然后让分子分母同除最大公约数即可。经典的数论问题了，用辗转相除法可以求出最大公约数。
如果还有其它方法，或者更工程化的方法，还请老师批评指正~

相关代码：

int gcd(int x, int y) {
    return y ? gcd(y, x%y) : x;
}

李谌 2023-06-19

源自：函数和表达式本质 1-5 Rational类的运算符重载实现

收起

1回答

quickzhao 回答被采纳获得+3积分 2023-06-20 09:24:48

是的。这里可以使用求最大公约数的方法进行约分。求最大公约数最简单的方式就是使用欧几里得的辗转相除法。但是你这里的gcd有几个明显的缺陷：首先这里一般来说x是需要大于y的，你没有做判断；再者这里的x%y效率比较低，可以有优化算法；并且使用递归来实现这个有天然的缺陷，递归层数不能太深。这方面有待修正和优化。加油。

收起回答

李谌提问者 #1

谢谢老师~
老师说的取余效率较低，我查询了一些资料。其中提到，“求余虽然只有一条指令但这条指令要耗费100多个周期。”因此，将 a % b 操作转换为 a - a / b * b是个通用的优化做法。老师说的优化是指这个吗？

2023-06-20 09:46:34
quickzhao 回复提问者李谌 #2

你这样的优化也仅仅停留在工程角度。其实算法优化需要首先从数学角度考虑，最大公约数有性质(a,b) = (a-b, b) 其中(a >b，a、b为正整数)，所以你其实可以可以使用这个特性将最大公约数的运算规模不断减小，这样既不会使用同余也不会使用乘除法，效果高很多。当然了，从工程的角度来看其实乘除法也有办法优化，至少你可以采用移位运算这样的位运算，代替你的乘除法，效率更高些。

2023-06-20 10:08:31
李谌提问者回复 quickzhao #3

谢谢老师！

2023-06-20 11:44:24