Content deleted Content added
→Space complexity: Clear scenario, equations, pseudocode with bug fix and extended to non-binary |
→Long multiplication: Algorithm for traditional steps |
||
Line 53:
------------
139676498390 ( = 139,676,498,390 )
===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)
m = [1..p+q] //Allocate space for result
for bi = 1 to q
carry = 0
for ai = 1 to p
m[ai + bi - 1] += carry + a[ai] * b[bi]
carry = m[ai + bi - 1] / base
m[ai + bi - 1] = m[ai + bi - 1] mod base
m[bi + p] += carry
return m
</source>
=== Space complexity ===
| |||