heuristics based on insightcommon case analysisand careful tuning that may solve the problem reasonably wellparallel algorithmswherein large number of computers can work on subparts simultaneously compute the greatest common divisor the greatest common divisor (gcdof nonnegative integers and is the largest integer such that divides evenlyand divides evenlyi mod and mod (when both and are take their gcd to be design an efficient algorithm for computing the gcd of two nonnegative integers without using multiplicationdivision or the modulus operators hintuse case analysisboth evenboth oddone even and one odd solutionthe straightforward algorithm is based on recursion if ygcd(xyxotherwiseassume without loss of generalitythat then gcd(xyis the gcd( yythe recursive algorithm based on the above does not use multiplicationdivision or modulusbut for some inputs it is very slow as an exampleif the input is the algorithm makes - recursive calls the time complexity can be improved by observing that the repeated subtraction amounts to divisioni when ygcd(xygcd(yx mod )but this approach uses integer division which was explicitly disallowed in the problem statement here is fast solutionwhich is also based on recursionbut does not use general multiplication or division instead it uses case-analysisspecificallythe cases of onetwoor none of the numbers being even an example is illustrative suppose we were to compute the gcd of and instead of repeatedly subtracting from we can observe that since both are eventhe result is gcd( dividing by is right shift by so we do not need general division operation since and are both evengcd( gcd( since is oddthe gcd of and is the same as the gcd of and since cannot divide the gcd of and is the gcd of and repeatedly applying the same logicgcd( gcd( gcd( gcd( gcd( gcd( this implies gcd( more generallythe base case is when the two arguments are equalin which case the gcd is that valuee gcd( or one of the arguments is zeroin which case the other is the gcde gcd( otherwisewe check if noneoneor both numbers are even if both are evenwe compute the gcd of the halves of the original numbersand return that result times if exactly one is evenwe half itand return the gcd of the resulting pairif both are oddwe subtract the smaller from the larger and return the gcd of the resulting pair multiplication by is trivially implemented with single left shift division by is done with single right shift def gcd(xy)if yreturn gcd(yxelif =