gcd(a: ,b: ) : ==

1ifa=bthenreturna

2ifa0 mod2andb0 mod2thenreturngcd(a/2,b/2)

3ifa0 mod2andb1 mod2thenreturngcd(a/2,b)

3ifa1 mod2andb0 mod2thenreturngcd(a,b/2)

4ifa>bthenreturngcd((a-b)/2,b)elsereturngcd((b-a)/2,a)

- Let
*n*_{a}and*n*_{b}the number of bits (in binary-expansion) of*a*and*b*respectively. Give an upper bound for the number of reursive calls needed to compute gcd(*a*,*b*)? - Give an upper bound for the number of machine word operations needed for
computing
gcd(
*a*,*b*).

2006-01-09