Prove that Russian multiplication does what it needs to do, i.e. the result is the product...

 

Transcribed Image Text:

Prove that Russian multiplication does what it needs to do, i.e. the result is the product of the two integers. Do not use the proof of the book. It is mainly an exercise in understanding the binary system and that is what you need to do - analyze the product of the two natural written in binary. See below. Let a, b = N To calculate the product a. b: P+0 While = if a 1 a [ a 1 do (mod 2) then p+p+b bb*2 return P Example 36, b = 7 (ab=252) a = a b 36 7 0 18 14 0 9 28 28 4 56 28 2 112 28 1 224 252 Prove that Russian multiplication does what it needs to do, i.e. the result is the product of the two integers. Do not use the proof of the book. It is mainly an exercise in understanding the binary system and that is what you need to do - analyze the product of the two natural written in binary. See below. Let a, b = N To calculate the product a. b: P+0 While = if a 1 a [ a 1 do (mod 2) then p+p+b bb*2 return P Example 36, b = 7 (ab=252) a = a b 36 7 0 18 14 0 9 28 28 4 56 28 2 112 28 1 224 252