PROBLEMS, AVAILABLE TOOLS & ALGORITHMS

In order to explain an important point in respect of the available tools, of which one must take care while designing an algorithm for a given problem, we consider some alternative algorithms for finding the product m*n of two natural numbers m and n.



First Algorithm:

The usual method of multiplication, in which table of products of pair of digits x, y (i.e.; 0 <_ x, y <_9) are presumed to be available to the system that is required to compute the product m*n.

 For example, the product of two numbers 426 and 37 can be obtained as shown below, using multiplication tables for numbers from 0 to 9.

..

Second Algorithm:

For this algorithm, we assume that the only arithmetic capabilities the system is endowed with, are

(i) that of counting and
(ii) that of comparing two integers w.r.t. ‘less than or equal to’ relation.

With only these two capabilities, the First Algorithm is meaningless.

For such a system having only these two capabilities, one possible algorithm to calculate m*n, as given below, uses two separate portions of a paper (or any other storage devices). One of the portions is used to accommodate marks upto n, the multiplier, and the other to accommodate marks upto m*n, the resultant product.

The algorithm constitutes the following steps:

Step 1: Initially make a mark on First Portion of the paper.

Step 2: For each new mark on the First Portion, make m new marks on the Second Elementary Algorithmics Portion.

Step 3: Count the number of marks in First Portion. If the count equals n, then count
the number of all marks in the Second Portion and return the last count as the result.
However, if the count in the First Portion is less than n, then make one more mark in
the First Portion and go to Step 2.

 Third Algorithm:

The algorithm to be discussed, is known a’la russe method. In this method, it is
presumed that the system has the only capability of multiplying and dividing any
integer by 2, in addition to the capabilities of Second Algorithm. The division must
result in an integer as quotient, with remainder as either a 0 or 1.

The algorithm using only these capabilities for multiplying two positive integers m
and n, is based on the observations that

(i)      If m is even then if we divide m by 2 to get (m/2) and multiply n by 2 to get
         (2n) then (m/2) . (2 n) = m . n.

(ii)    However, if m is odd then (m/2) is not an integer. In this case, we write
         m = (m ─ 1) + 1, so that (m ─ 1) is even and (m ─ 1)/2 is an integer.
        Then
        m . n = ((m ─ 1) + 1) . n = (m – 1)n + n
        = ((m ─ 1)/2) . (2n) + n.
        where (m ─ 1)/2 is an integer as m is an odd integer.

        For example, m = 7 and n = 12

        Then
      
..
Therefore, if at some stage, m is even, we halve m and double n and multiply the two
numbers so obtained and repeat the process. But, if m is odd at some stage, then we
halve (m – 1), double n and multiply the two numbers so obtained and then add to the
product so obtained the odd value of m which we had before halving (m ─1).

Next, we describe the a’la russe method/algorithm.

 The algorithm that uses four variables, viz., First, Second, Remainder and
Partial-Result, may be described as follows:

Step 1: Initialize the variables First, Second and Partial-Result respectively with m
(the first given number), n (the second given number) and 0.

Step 2: If First or Second* is zero, return Partial-result as the final result and then
stop.

# If, initially, Second #0, then Second # 0 in the subsequent calculations also.

Else, set the value of the Remainder as 1 if First is odd, else set Remainder as 0. If Remainder is 1 then add Second to Partial-Result to get the new value of Partial Result.

Step 3: New value of First is the quotient obtained on (integer) division of the current value of First by 2. New value of Second is obtained by multiplying Second by 2. Go to Step 2.

Example 1.5.1: The logic behind the a’la russe method, consisting of Step 1, Step 2 and Step 3 given above, may be better understood, in addition to the argument given the box above, through the following explanation:

Let First = 9 and Second = 16

Then First * Second = 9 * 16 = (4 * 2 + 1) * 16
                                 = 4 * (2 * 16) + 1 * 16

where 4 = [9/2] = [first/2], 1 = Remainder
Substituting the values back, we
                    first * second = [first/2] * ( 2 * Second) + Second.

Let us take First1 = [First/2] = 4
Second1 = 2 * Second = 32 and
Partial-Result = First1 * Second 1.
Then from the above argument, we get
                  First * Second = First1 * Second1 + Second
                                          = Partial-Result1 + Second.
Here, we may note that as First = 9 is odd and hence Second is added to Partial-Result. Also
                                                   Partial-Result1 = 4*32 = (2 * 2 + 0) * 32 = (2 * 2) * 32 + 0 * 32 = 2* (2 * 32) = First 2 * Second 2.

       Again we may note that First1 = 4 is even and we do not add Second2 to Partial-Result2, where Partial-Result2 = First2 * Second2.

Next, we execute the a’la russe algorithm to compute 45 * 19.

..
 As the value of the First is 0, the value 855 of Partial Result is returned as the result and stop.

 Ex. 3) A system has ONLY the following arithmetic capabilities:

(i) that of counting,
(ii) that of comparing two integers w.r.t. ‘less than or equal to’ relation and
(iii) those of both multiplying and dividing by 2 as well as 3.

Design an algorithm that multiplies two integers, and fully exploits the capabilities of
the system. Using the algorithm, find the product.