|
=== Space complexity ===
{{unreferenced section|date=September 2012}}
Let ''n'' be the total number of bitsdigits in the two input numbers in [[Radix|base]] ''D''. LongIf the result must be kept in memory then the space complexity is trivially Θ(''n''). However in certain applications, entire result need not be kept in memory and instead digits of results can be streamed out as they are computed (for example, to system console or file). In these scenarios, long multiplication has the advantage that it can easily be formulated as a [[FL (complexity)|log space]] algorithm; that is, an algorithm that only needs working space proportional to the logarithm of the number of digits in the input (Θ(log ''n'')). This is the ''double'' logarithm of the numbers being multiplied themselves (log log ''N''). We don't include the input or output bits in this measurement, sinceNote that wouldoperands triviallythemselves makestill theneeds spaceto requirementbe linear;kept insteadin we make the input bits read-onlymemory and the output bits write-only.their Θ(This''n'') justspace means that input and output bits areis not countedconsidered asin wethis count only read- AND writable bitsanalysis.)
The method is simple:based we addon the columnsobservation right-to-left,that keepingeach trackdigit of the carryresult ascan webe go.computed Wefrom don't haveright to storeleft thewith columnsonly toknowing do this. To show this, let the ''i''th bitcarry from the rightprevious ofstep. the first and second operands be denotedLet ''a''<sub>''i''</sub> and ''b''<sub>''i''</sub> respectively,be both starting atthe ''i'' = 0,-th anddigit letof the operand, ''r''<sub>''i''</sub> be the ''i''-th bitdigit fromof the rightresult ofand ''c''<sub>''i''</sub> be the result.carry generated for ''r''<sub>''i''</sub> (i=1 is the right most digit) Thenthen
:<math>r_i = c( c_{i-1} + \sum_{j+k=i} a_j b_k, ) \mod D</math>
:<math>c_i = \lfloor (c_{i-1} + \sum_{j+k=i} a_j b_k) / D \rfloor</math>
:<math>c_0 = 0</math>
A simple inductive argument shows that the carry can never exceed ''n'' and the total sum for ''r''<sub>''i''</sub> can never exceed 2''D'' * ''n'': the carry into the first column is zero, and for all other columns, there are at most ''n'' bitsdigits in the column, and a carry of at most ''n'' coming in from the previous column (by the induction hypothesis). TheirThe sum is at most 2''D'' * ''n'', and the carry to the next column is at most half''D'' of* this''n'' / ''D'', or ''n''. Thus both these values can be stored in O(log ''n'') bitsdigits. ▼where ''c'' is the carry from the previous column. Provided neither ''c'' nor the total sum exceed log space, we can implement this formula in log space, since the indexes ''j'' and ''k'' each have O(log ''n'') bits.
▲A simple inductive argument shows that the carry can never exceed ''n'' and the total sum for ''r''<sub>''i''</sub> can never exceed 2''n'': the carry into the first column is zero, and for all other columns, there are at most ''n'' bits in the column, and a carry of at most ''n'' coming in from the previous column (by the induction hypothesis). Their sum is at most 2''n'', and the carry to the next column is at most half of this, or ''n''. Thus both these values can be stored in O(log ''n'') bits.
In pseudocode, the log-space algorithm is:
'''multiply'''(a[01..n−1p], b[01..n−1q], base) // ArraysOperands containing rightmost representingdigits theat binaryindex representations1
xsum ← 0
'''for''' iri from= 01 to 2n−1p + q - 1 //For each digit of result
'''for''' jbi from= maxMAX(01,i ri - p +1−n 1) to minMIN(iri,n−1 q) //Digits Columnfrom b that needs to multiplicationconsidered
kai ← iri − jbi + 1 //Digits from a follow "symmetry"
xsum ← xsum + (a[jai] × b[kbi])
result[iri] ← xsum mod 2base
xsum ← floor(xsum /2 base)
result[p+q] ← sum mod base //Last digit of the result comes from last carry
=== Electronic usage ===
| 