2

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.

1 Answer 1

1

When we do large%small it gives remainder which can be 0 if it is fully divided but if we do small%large it only gonna give us small. Suppose if _a=65 and _b=784 then

  1. first loop temp=784, _b=65, _a=temp
  2. second loop temp=65, _b=4 , _a=temp
  3. third loop temp=4, _b=1 , _a=temp
  4. fourth loop temp=1, _b=0, _a=temp

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.