Question

Describe a recursive algorithm for multiplying two nonnegative integers x and y based on the fact that xy = 2 (x . (y / 2)) when y is even and xy = 2 (x . [y / 2]) + x when y is odd, together with the initial condition xy = 0 when y = 0 .

Short answer

The recursive algorithm is,

procedure product (x,y : nonnegative integers)

if y = 0 then

return 0

else if

y is even then

return 2 . product (x, (y - 1) / 2) + x

else return 2. product (x, ()y - 1) / 2) + x

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for the multiplying two nonnegative integers x and y based on the given fact.

The fact is,

When y is even,

xy = 2 (x.(y/2))

when y is odd,

xy = 2 (x . [y/2) + x

Write the recursive algorithm for multiplying two nonnegative integers x and y based on given fact

Call the algorithm "product" and the input are two nonnegative integers x and y.

procedure product (x,y : nonnegative integers)

When one of the integers is zero, then the product is zero.

if y = 0 then

return 0

Use xy = 2 (x. (y/2)) when y is even.

else if

y is even then

return 2. product (x,y / 2)

Use xy = 2 (x. [y/2]) when y is even.

else return 2. product (x,y / 2)

Use xy = 2 (x. [y/2]) when y is even.

else return 2. product (x,y : nonnegative integers)

if y = 0 then

return = 0

else if

y is even then

return 2. product (x,y / 2)

else return 2. product (x,y - 1) / 2 ) + x

Therefore, the recursive algorithm is shown above.