Multiplication algorithm: Difference between revisions

Revision as of 03:18, 2 October 2015

Revision as of 07:37, 9 November 2015

Line 53:

———————————————

139676498390 ( = 139,676,498,390 )

Below pseudocode describes the process of above multiplication. It keeps only one row to maintain sum which finally becomes the result. Note that we usethe '+=' operator is used to denote sum to existing value and store operation (akin to languages such as Java and C) for compactness.

===Pseudocode===

Below pseudocode describes the process of above multiplication. It keeps only one row to maintain sum which finally becomes the result. Note that we use '+=' operator to denote sum to existing value and store operation (akin to languages such as Java and C) for compactness.

<source lang="pascal">

multiply(a[1..p], b[1..q], base) // Operands containing rightmost digits at index 1

mproduct = [1..p+q] //Allocate space for result

for b_i = 1 to q // for all digits in b

for bi = 1 to q

carry = 0

for aia_i = 1 to p //for all digits in a

mproduct[aia_i + bib_i - 1] += carry + a[ai] * b[bi]

carry = mproduct[ai + bi - 1] / base

mproduct[aia_i + bib_i - 1] = mproduct[ai + bi - 1] mod base

resultproduct[pb_i +q p] ←+= sumcarry mod base //Last digit of the result // last digit comes from lastfinal carry

m[bi + p] += carry

return mproduct

</source>

Line 82 ⟶ 80:

A simple inductive argument shows that the carry can never exceed ''n'' and the total sum for ''r''_''i'' can never exceed ''D'' * ''n'': the carry into the first column is zero, and for all other columns, there are at most ''n'' digits in the column, and a carry of at most ''n'' from the previous column (by the induction hypothesis). The sum is at most ''D'' * ''n'', and the carry to the next column is at most ''D'' * ''n'' / ''D'', or ''n''. Thus both these values can be stored in O(log ''n'') digits.

In pseudocode, the log-space algorithm is:<syntaxhighlight lang="pascal">

'''multiply'''(a[1..p], b[1..q], base) // Operands containing rightmost digits at index 1

tot sum ←= 0

'''multiply'''(a[1..p], b[1..q], base) // Operands containing rightmost digits at index 1

for ri = 1 to p + q - 1 //For each digit of result

sum ← 0

''' for''' ribi = MAX(1, tori - p + q - 1) to MIN(ri, q) //Digits from b that need to be //For each digit of resultconsidered

'''for''' bi = MAX(1,ai = ri -− pbi + 1) to MIN(ri, q) //Digits from b that need toa befollow considered"symmetry"

tot ai= ← ri − bitot + 1 //Digits from (a[ai] follow* "symmetry"b[bi])

product[ri] = tot mod base

sum ← sum + (a[ai] × b[bi])

tot result[ri]= ←floor(tot sum mod/ base)

product[p+q] = tot mod base //Last digit of the result comes from last carry

sum ← floor(sum / base)

return product

result[p+q] ← sum mod base //Last digit of the result comes from last carry

</syntaxhighlight>

===Electronic usage===