Thomas Koenig wrote:
How do computers nowadays actually perform decimal arithmetic,
and how did they do it in the past?
For adding, the first microprocessors used the "if the result of
A+B is larger than nine, then add six to the result and set carry"
method. If one wanted to speed this up with today's possibilities,
then the two additions could be done in parallel, with the carry
of A+B+6 selecting the result. This could then be integrated into
a conditional sum adder. If A+B+6 could be calculated efficiently
with a modified carry lookahead method, this method could work well.
The above describes a suite of methods applicable to decimal arithmetic.
For multiplication... I am not sure that the method outlined above
for addition would be efficient.
Basically, you make a decimal multiplier cell 2×4-bits in 8-bits out
and feed these into a 3-input decimal carry save adder. By restricting
the input values to the set {0..9} instead of {0..15} you save a whole
bunch of gates. It is equivalent to a 100 cell ROM after the Verilog
gate muncher gets rid of excess logic.
{ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } // [*,0]
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } // [*,1]
{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 } // [*,2]
{ 0, 3, 6, 9, 12, 15, 18, 21, 24, 27 } // [*,3]
..
{ 0, 9, 18, 27, 26, 45, 54, 63, 72, 81 } // [*,9]
}
You route the leading digit to the next column of significance.
You route the trailing digit to this column of significance.
My (uninformed) guess would be that people would re-encode the BCD
numbers to something with different weights than the traditional
8-4-2-1 (maybe 4-2-2-1) and then make modified Wallace or Dadda
trees, which would deliver the indificual digits in that encoding,
from which they could then be converted to BCD or another format
as desired.
TI has a bunch of patents circa mid 1980s on decimal multiplication.
Does anybody know how this is actually done?
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)