I was trying to get the GCD of two numbers. This function I saw on github works fine but I have a confusion here.
The function :
function _gcd(uint256 a, uint256 b) external pure returns (uint256) {
uint256 _a = a;//65
uint256 _b = b;//784
uint256 temp;//0
while (_b > 0) {
temp = _b;//784
_b = _a % _b; // % is remainder 0
_a = temp;//784
}
return _a;
}
The confusion is in this line:
_b = _a % _b; // % is remainder
So when we modulo a smaller number with a large one it gives out zero.
In the case of this function, even if I pass the smaller number at uint a and the larger number at uint b, it gives out the correct GCD. How is it working?
I am confused about when we pass a smaller number as a
then in the first loop the _b
variable will be zero and _a
will be returned and it won't be the correct GCD, but it is returning the correct GCD.
Like how is a % b
giving out the same answer as b % a
The GitHub code: https://gist.github.com/3esmit/8c0a63f17f2f2448cc1576eb27fe5910
Please let me know if I was able to convey the problem. I will elaborate more on this if needed.