Challenge: Understand the algorithm for Russian multiplication given in Example 5.2.10.
(a) Execute the algorithm using A = 12 and B = 7.
(b) Now choose two different values for A,B and execute the algorithm again.
(c) When do you write down Bstep and when not?
(d) When you sum the column, what multiple of B (how many copies of B) do you obtain?
(e) Does this have anything to do with binary numbers?
(f) How exactly does this algorithm give the same result as usual multiplication?
Example 5.2.10
(of Russian-style multiplication). Believe it or not, this algorithm multiplies natural numbers! The input numbers are A and B. We have one bit of notation to explain; the floor function x returns the greatest integer less than or equal to x.