 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""i" and "b""i" be the "i"-th digit of the operand, with "a" and "b" padded on the left by zeros to be length "n", "r""i" be the "i"-th digit of the result and "c""i" be the carry generated for "r""i" (i=1 is the right most digit) then

or

A simple inductive argument shows that the carry can never exceed "n" and the total sum for "r""i" can never exceed "D" * "n"