A simple inductive argument shows that the carry can never exceed "n" and the total sum for "r""i" 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.