# Challenges

« Reflections
1 reply [Last post] Edward Gentle
Member

Have any of you tried some  more challengenig programs like described in

If have tried the first three and uploaded EXE versions of my solutions .....

Problem 1: Multiplication `a la russe
The standard multiplication algorithm taught in elementary schools represents just one of
several ways to compute the product of two numbers. A different method, which was known in
ancient Egypt and is called multiplication `a la russe, more closely resembles how multiplication
is performed in electronic computers.
Using this method, we need not refer to (or memorize) the standard multiplication table (which,
for any two single-digit numbers, tells us their product). Rather, we need to know how to do four
things: add, decrement, double, and halve. Using these four operations, we can characterize
multiplication of two positive integers a and b as follows: Develop a program that, given two positive integers, multiplies them according to this method
and outputs their product as the sum of numbers obtained during the process. For the example
above, this sum is 6 + 12 + 48 + 192 + 384.
Input: The first line contains a positive integer n indicating how many instances of the problem
are described thereafter. Each of the next n lines contains a pair of positive integers a and b
to be multiplied, separated by a space.
Output: For each pair a and b given as input, display on a single line the equation
a ¤ b = t1 + t2 + · · · + tr
where the ti’s are the elements of the sum obtained by multiplying a and b using multiplication
`a la russe. The ti’s should be in ascending order.

Resultant output
----------------
214 * 3 = 6 + 12 + 48 + 192 + 384
1 * 3543 = 3543
3543 * 1 = 1 + 2 + 4 + 16 + 64 + 128 + 256 + 1024 + 2048
134 * 18 = 36 + 72 + 2304

Replies Edward Gentle
Member