Content deleted Content added
Reverted 2 edits by 114.179.104.71 (talk). (TW) |
→Space complexity: grammar |
||
Line 72:
=== Space complexity ===
{{unreferenced section|date=September 2012}}
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 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''). Note that operands themselves still
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, ''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>r_i = ( c_{i-1} + \sum_{j+k=i} a_j b_k ) \mod D</math>
Line 87:
sum ← 0
'''for''' ri = 1 to p + q - 1 //For each digit of result
'''for''' bi = MAX(1, ri - p + 1) to MIN(ri, q) //Digits from b that
ai ← ri − bi + 1 //Digits from a follow "symmetry"
sum ← sum + (a[ai] × b[bi])
|