= Carry normalization of a digit array
{title2=$a_i=qb+r\quad\mapsto\quad a_i=r,\ a_{i+1}\mathrel{+}=q$}
Process a <digit-array integer representation> from low to high positions. The <integer division> supplies $q=\lfloor a_i/b\rfloor$ and $0\leq r<b$. Replacing the current digit by $r$ and adding $q$ to the next position preserves the represented value. Append zero storage when a positive carry leaves the allocated array. The processed prefix remains normalized and the value stays fixed.
This also works with signed temporary digits when the represented value is nonnegative. A negative carry cannot leave the final allocated position: the normalized lower digits represent a value less than that position's next radix power, which could not offset that negative carry. Positive carries eventually stop beyond the value's finite radix expansion. Thus the usual nonnegative-digit algorithm admits this useful extension without interpreting truncated division as floor division.
Back to article page
