Gcd (bc)
From LiteratePrograms
- Other implementations: bc | C
This implements the Euclidean Algorithm in the bc to find the Greatest Common Divisor of two integers 'a' and 'b'.
define gcd(a,b) { auto q,r; while(b != 0) { r=a % b; a=b; b=r; } return(a); }
Alternatively, we can write this more clearly:
define gcd(numerator,denominator) { auto quotient, remainder; scale=0; while(denominator != 0) { quotient = numerator / denominator; remainder = numerator % denominator; numerator = denominator; denominator = remainder; } return(numerator); }
The scale is set to zero so that bc will perform modulo operations correctly.
Here is another implementation of the Greatest Common Divisor that shows every step used.
define gcdsteps(a,b) { auto q,r; print "a=b*q+r\n" while(b != 0) { q=a/b; r=a%b; print a,"=",b,"*",q,"+",r,"\n"; a=b; b=r; } print "0=",b,"*",q,"+",r," -- STOP\n"; return(a); }
Download code |