Content deleted Content added
→Fourier transform methods: suggest to link Theta in each section, as these links are hard to find due to their shortness |
|||
Line 72:
Let ''n'' be the total number of digits in the two input numbers in [[Radix|base]] ''D''. If the result must be kept in memory then the space complexity is trivially Θ(''n''). However, in certain applications, the entire result need not be kept in memory and instead the digits of the result 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 ([[Bachmann-Landau notation|Θ]](log ''n'')). This is the ''double'' logarithm of the numbers being multiplied themselves (log log ''N''). Note that operands themselves still need to be kept in memory and their Θ(''n'') space is not considered in this analysis.
The method is based on the observation that each digit of the result can be computed from right to left with only knowing the carry from the previous step. Let ''a''<sub>''i''</sub> and ''b''<sub>''i''</sub> be the ''i''-th digit of the operand, with ''a'' and ''b'' padded on the left by zeros to be length ''n'', ''r''<sub>''i''</sub> be the ''i''-th digit of the result and ''c''<sub>''i''</sub> be the carry generated for ''r''<sub>''i''</sub> (i=1 is the right most digit) then
:<math>\begin{align}
r_i &= \left( c_{i-1} + \sum_{j+k=i+1} a_j b_k \right) \mod D \\
c_i &= \left\lfloor (c_{i-1} + \sum_{j+k=i} a_j b_k) / D \right\rfloor \\
c_0 &= 0
\end{align}</math>
or
:<math>
c_i = \left( \sum_{m = 0}^{i - 2} \sum_{j + k = i - m} a_j b_k \right) / D.
</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 ''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.
| |||