Multiplication algorithm: Difference between revisions

Revision as of 12:34, 23 September 2012

Revision as of 17:11, 28 September 2012

Line 55:

=== Space complexity ===

{{unreferenced-section|date=September 2012}}

Let ''n'' be the total number of bits in the two input numbers. 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, since that would trivially make the space requirement linear; instead we make the input bits read-only and the output bits write-only. (This just means that input and output bits are not counted as we count only read- AND writable bits.)