2 ms·

This worked great for cpu's as 'doubling' was just a bit shift left 'x' number of times - very fast. Except that you'd get a summation with the number of terms

by tremon 5y ago

This worked great for cpu's as 'doubling' was just a bit shift left 'x' number of times - very fast. Except that you'd get a summation with the number of terms equal to the number of bits in the source operands. Multiplication in a CPU only seems very fast because the theory is simple. Building a fast multiplier in silicon requires a lot of area and a lot of interconnect, because you don't require "just" a massive addition table, you also need carry lookahead logic to perform fast carry propagation otherwise you get no speed increase. A naive multiplier in a CPU requires 1 cycle per result bit (multiplying two 32-bit numbers requires 32 additions, then you need to wait another 32 cycles for full carry propagation). That's very slow, in CPU terms.

mech422 5y ago
not quite sure what your getting at here...on a simple 8 bit like the 6502, you were generally dealing with plain binary, not some IEEE standard, so you get at most a single addition (if the multiplicand was odd), and just threw an 'overflow error' at the end if the carry/overflow bit was set... Now arbitrary length BCD...THAT was a PITA But again, it was 30 years ago so my memory may be fuzzy. Edit: Hmm - if I recall, it was something like: and the value with x01 to check LSB, asl value, (multiplicand masked with LSB=0), if LSB check was true, add value to result, check overflow flag ? Again, this was simple binary data usually of a fixed 1 byte or 2 byte length. we used BCD for 'real work' and I can't even remember how that was done...
- tremon 5y ago
  How do you get to "at most a single addition"? Even when multiplying any N with a 4-bit number like 14 (0b1110), you'd get at least two additions: (N << 1) + (N << 2) + (N << 3). And that is assuming you already have spent the additional lookahead logic to skip the addition step if the source operand has a 0 bit (which most implementations don't do, because the zero detection logic requires even more logic gates in addition to the adder tree).
  - mech422 5y ago
    Ahh - yeah, my bad... I always remember it being much simpler then it appears it was. Guess I'm getting rusty from using fancy languages with built in multiply instructions :-)

by tremon 5y ago

mech422 5y ago

not quite sure what your getting at here...on a simple 8 bit like the 6502, you were generally dealing with plain binary, not some IEEE standard, so you get at most a single addition (if the multiplicand was odd), and just threw an 'overflow error' at the end if the carry/overflow bit was set... Now arbitrary length BCD...THAT was a PITA But again, it was 30 years ago so my memory may be fuzzy. Edit: Hmm - if I recall, it was something like: and the value with x01 to check LSB, asl value, (multiplicand masked with LSB=0), if LSB check was true, add value to result, check overflow flag ? Again, this was simple binary data usually of a fixed 1 byte or 2 byte length. we used BCD for 'real work' and I can't even remember how that was done...

tremon 5y ago
How do you get to "at most a single addition"? Even when multiplying any N with a 4-bit number like 14 (0b1110), you'd get at least two additions: (N << 1) + (N << 2) + (N << 3). And that is assuming you already have spent the additional lookahead logic to skip the addition step if the source operand has a 0 bit (which most implementations don't do, because the zero detection logic requires even more logic gates in addition to the adder tree).
- mech422 5y ago
  Ahh - yeah, my bad... I always remember it being much simpler then it appears it was. Guess I'm getting rusty from using fancy languages with built in multiply instructions :-)