Question

Consider multiplying the integers m = 443 and n = 1023 using the

Russian algorithm. What is the exact number of times the while-loop
is executed?
a. 11
b. 10
c. 9
d. infinite

Answer 1

When multiplying the integers 443 and 1023 using the Russian algorithm, the while-loop that halves the larger number, n = 1023, is executed 10 times before reaching 1, which terminates the loop.

The Russian Peasant Algorithm is a method of multiplication that involves halving one number and doubling the other, then adding up the numbers that are opposite an odd number. If we multiply the integers m = 443 and n = 1023 using the Russian algorithm, we can determine the exact number of times the while-loop is executed by observing the halving process of the larger number, n. Starting with n = 1023, it will take 10 halvings for the number to reduce to 1:

• 1023 → 511.5 (ignore the decimal)
• 511 → 255.5 (ignore the decimal)
• 255 → 127.5 (ignore the decimal)
• 127 → 63.5 (ignore the decimal)
• 63 → 31.5 (ignore the decimal)
• 31 → 15.5 (ignore the decimal)
• 15 → 7.5 (ignore the decimal)
• 7 → 3.5 (ignore the decimal)
• 3 → 1.5 (ignore the decimal)
• 1 → termination of the loop as we've reached the base case.

So, the while-loop is executed 10 times.