|
139676498390 ( = 139,676,498,390 )
adding big mnumbers together helps youu understand the fact like when you go to 5 grade or 4 grade
=== Space complexity ===
ΒΎ ΤΑΜYΚΑ[[File:Example.jpg]]'''''Bold text
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.)
The method is simple: we add the columns right-to-left, keeping track of the carry as we go. We don't have to store the columns to do this. To show this, let the ''i''th bit from the right of the first and second operands be denoted ''a''<sub>''i''</sub> and ''b''<sub>''i''</sub> respectively, both starting at ''i'' = 0, and let ''r''<sub>''i''</sub> be the ''i''th bit from the right of the result. Then
:<math>r_i = c + \sum_{j+k=i} a_j b_k,</math>
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[0..n−1], b[0..n−1]) // Arrays representing the binary representations
x ← 0
'''for''' i from 0 to 2n−1
'''for''' j from max(0,i+1−n) to min(i,n−1)column multiplication
k ← i − j
x ← x + (a[j] × b[k])
result[i] ← x mod 2
x ← floor(x/2)
=== Electronic usage ===
| 