12

I recall reading about a CPU from the 90s which had, in addition to normal integer multiply and divide instructions, also had a special set of instructions for multiplying and dividing by ten. Does anyone know what this CPU was, if indeed it existed?

The idea was that if the compiler had such an expression with a hard coded ten - x*10 or x/10, something that would happen a lot in code, it would use the special instructions that were a lot faster than the generic instructions.

14
  • 10
    aam and aad in the 8086 instruction set are short instructions: pushbx.org/ecm/doc/insref.htm#insAAA
    – ecm
    Commented Feb 29 at 17:55
  • 2
  • 6
    @davidbak They are, at least on paper. On the 8088, using a divisor/multiplier other than 10 is officially an illegal instruction, even though they do what you’d expect and in later revisions of x86 Intel decided to support them all the same. NEC V20 even ignores the immediate operand outright. Commented Feb 29 at 19:13
  • 4
    Multiplying by small constants is quite cheap using shifts and additions, there is no need for a separate instruction for it. In x86, multiplication by 10 is done with 2 instructions, leal (%rdi,%rdi,4), %eax + addl %eax, %eax
    – Leo B.
    Commented Mar 1 at 0:12
  • 3
    The CDC160 has multiply-by-ten and multiply-by-hundred instructions, but no divide instructions and no general multiply instructions. And it's from the sixties not the nineties. Commented Mar 1 at 6:58

5 Answers 5

21

Yes. But not as you think.

The Z80 has the RLD and RRD instructions which rotate a packed BCD in memory by 4 bits left or right, that effectively results in a multiplication or division by ten of that said packed decimal.

Support for multiplication/division of binary numbers, however, is not in that CPU. You would multiply by eight (by shifting the number), then add the same number multiplied by 2 (yet another shift), ending up in a multiplication by ten.

9
  • 8
    @supercat Yep. But that was not the question.
    – tofro
    Commented Mar 1 at 16:09
  • 7
    @Raffzahn The question did neither specifically address integer nor BCD format, but rather asked "how can CPUs multiply and divide by 10". And that's specifically addressed by RRD and LLD.
    – tofro
    Commented Mar 1 at 20:49
  • 2
    To point out the obvious, the Z80 dates to 1976 and while (to the best of my knowledge) still in production it does not fit the label "CPU from the 90s". I am also doubtful that any compilers targeting the Z80 would make frequent use of RRD and RLD.
    – njuffa
    Commented Mar 1 at 21:29
  • 2
    @tofro "The question did neither specifically address integer nor BCD format, " Sure? To my understanding the words 'normal integer', as used, do very specifically ask for integers, not BCD.
    – Raffzahn
    Commented Mar 2 at 8:57
  • 2
    @paxdiablo I reverted your pseudo-assembly code change. Didn't find it more useful (rather: confusing that you used an imaginary asembly language) than my textual description.
    – tofro
    Commented Mar 2 at 10:54
11

As mentioned by others BCD operation require multiplication and division by 10 (and multiples there of) implemented as shift by 4. It is necessary when floating point numbers are represented with BCD mantissa. Floating point operations add and subtract need that mantissas be aligned which requires shifting one of the mantissas by a multiple of 4 bits. Even numbers of 4 bit shifts is simply implemented by byte copies, the odd case can be helped by a 4 bit shift instruction. A nibble swap is sometime the only requirement.

Some implementations of the Z80 in FPGA (Z80N) add a slew of instructions of which SWAPNIB (EC23) is related to this operation, it swaps the high and the low nibble of the accumulator.

  • The Z80 has the RLD and RRD instruction.

  • NEC added to the V20/V30 instructions (80186 compatible) a whole group of BCD instructions of which ROL4 (0F28) and ROR4 (0F2A) are notable.

  • Sharp's ESR-H microcontroller SC61860 used in a lot of their pocket computers have SRW and SLW instruction that shift by 4 in a loop (it also has SWP instruction that swaps low and high nibble of the accumulator). The instruction set is optimized to handle floating point BCD arithmetic.

  • Sharp's LH-5801 CPU of the PC-1500 pocket computer has similar instructions DRL, DRR and AEX (nibble swap) for the exact same reason of handling BCD floating point format.

1
  • 1
    Those are all BCD instructions, not such handling integers. Operated on integer they are (at best) divide by 16, like any shift by 4
    – Raffzahn
    Commented Mar 1 at 8:31
4

TL;DR: No, There is No Such CPU - But Compilers (may) Use Approximation

I can't come up with any CPU with an instruction fitting that description. But replacement of certain values by shift and add was common. Except not 10. More important for back then, division was usually way slower than multiplication, sometimes 3 to 5 times, so compiler did implement approximation by replacing divisions by multiplying with an inverted divisor.

This Stack Overflow question nicely shows how GCC implemented it (*1).


I recall reading about a CPU from the 90s which had, in addition to normal integer multiply and divide instructions, also had a special set of instructions for multiplying and dividing by ten.

The first one that comes to mind would be the /360, as it had decimal instructions, working on BCD strings, as well, but those were the 1960s and not just for by 10.

The only one with a dedicated instruction that would divide or multiply fixed by 10 and only 10 is the 8086 with it's AAM/AAD, intended for BCD handling. While these do divide/multiply by 10, the operations are restricted to byte operands with no way to handle overflow(*2).

  • AAM (ASCII Adjust after Multiply) divides the (unsigned 8 bit) AL by 10, bringing the quotient in AH, and the remainder in AL. It's purpose is to turn a binary value up to 99 (63h) into two decimal digits.

  • AAD (ASCII Adjust before Division) offers the inverse operation to AAM: AH is multiplied by 10 and added to AL. This turns two decimal (0..9) values into a binary 0..99 value.

While both instructions will also work on byte values outside of 0..9 or 0..99, usability with those is limited.

The idea was that if the compiler had such an expression with a hard coded ten - x*10 or x/10, something that would happen a lot in code, it would use the special instructions that were a lot faster than the generic instructions.

I would not know any CPU and compiler doing this using special instructions.

But what Compilers can do is replacing the use of costly multiplication and especially divisions by by one or more simpler instructions.

For one straight multiplication or divisions by 2, 4, 8, ... can be replaced by shift instructions. or combinations of shift and add or sub. This scales with the number of set bits, so will only produce reasonable savings for a limited range of values.

More important in this context may be the fact that divisions are way more costly than multiplications. Even with modern CPU's of the 1990s, like 586 or Pentium, a 32 bit integer multiplication (IMUL) was up to 4 times faster than a 32 bit division (IDIV). 46 vs 10 clocks on a Pentium.

Now,as everyone might remember, a division can be replaced by multiplying with the inverted divisor (1/d). So in this case, instead of doing a division by 10, we multiply by 1/10th. Nicely shown when looking at 16 bit x86 assembly:

; In:  Value to divide in DX
; Out: Result in DX
    MOV    AX,1999h         ; 1/10 as fixed point 
    IMUL   DX               ; DX:AX contains 32 bit 16:16 fixed point result

Using IDIV for this will take 30+1 clocks (*3) on a Pentium while above code takes only 11+1. This also works quite fine for other values than just 10. Except, being an approximation it carries an error, which grows with the value of the divisor. While the Error should always bee within the usual margin, it may differ.

The growing error is marked by the leading zeros of the divisor's inverse value. In fact, it's already visible with 1/10 featuring 3 leading zeroes:

0001.1001.1001.1001

That's why most compilers will replace the division by using a 'left aligned' value followed by according shifting. In case of 10 this will be

1100.1100.1100.1100

followed by a shift right by 3:

; In:  Value to divide in DX
; Out: Result in DX
    MOV    AX,0CCCCh        ; fixed point 1/10 time 8. 
    IMUL   DX               ; DX:AX contains 32 bit 16:16 fixed point result
    SHR    DX,3             ; 'normalize' result

As usual this comes as well with a drawback as now the usable range is reduced by those 3 bits.


*1 - Note that it's using 64 bit instructions, something not invented until a decade later. Function is still the same.

*2 - While the multiplier maybe changed on Intel CPUs, other implementations, like NEC's V20, will not honour this.

*3 - the +1 is for loading either constant.

4
  • Where is the "ASCII" in AAM/AAD coming from? Where these meant for ASCII digits (i.e. bytes 48 to 57)? Then you'd have to include adding/subtracting 48 to/from the number. Commented Mar 2 at 2:02
  • @PaŭloEbermann Sounds like a good question tobe asked in it's own right. My guess would be it's because BCD is, in context of (8 bit) byte handling, usually associated with two decimal digits per byte (packed BCD), which is what DAA/DAS instruction handle. The AAx instructions work only for single digit values (unpacked BCD) and ASCII being the most common unpacked format. Mnemonics are all about association. For a definitive answer one may need to ask whoever was responsible for final naming at Intel.
    – Raffzahn
    Commented Mar 2 at 7:41
  • I swore I used to use those AAD/AAM instruction way back in my TRS-80 youth, but a bit of research showed just how mushy my brain has become. They were DAA and DAS, meant to adjust BCD after addition and subtraction, not multiplication and division. But at least it made for sense than the "ASCII" acronyms, since it was decimal adjust for addition/subtraction :-)
    – paxdiablo
    Commented Mar 2 at 11:28
  • @paxdiablo Well, there are as well AAA and AAS to work on single digit add/sub. So using D as well was inappropriate.
    – Raffzahn
    Commented Mar 2 at 15:04
1

UCSD p-System

Not really a CPU per se, but some UCSD p-System reserved some space in zero page for "power of 10" constants, and compilers would generate special instructions for common cases like 10**N in code.

That is, instead of executing repetitive multiplications, the compiler would emit instructions that switch on N and load the pre-computed result.

2
  • 2
    switch on N? Did those machines not have array indexing, or do you just mean a range-check before accessing the lookup table. Commented Mar 1 at 16:43
  • @PeterCordes The p-system is an interpreter, not a CPU. Also, what he refers to are common expression optimizations.
    – Raffzahn
    Commented Mar 1 at 21:29
-1

If you look at an x86 processor there are several instructions that multiply be a constant: Left shift multiplies by 2^n for any fixed n. An indexing instruction can add x, 2x, 4x or 8x plus another value including x. A subtract operation can calculate x-x = 0*x. So in one instruction we can multiply x by any of the constants 0, 1, 2, 3, 4, 5, 8, 9, 16, 32, 64, 128 etc. 10 is not amongst them unfortunately.

If you try two consecutive instructions, or two in parallel and a third, or three consecutive instructions, then you can construct multiplications by many other constant factors that are much faster than a general multiplication.

2
  • 5
    How does this answer the asked question?
    – Justme
    Commented Mar 2 at 19:58
  • 3
    If you're going to answer about x86, you should at least mention that 386 and later can multiply by 10 with two instructions, lea eax, [eax + eax*4] (x5) / add eax, eax (x2). On many modern CPUs, this has only 2 cycles of latency, so is slightly better than imul eax, eax, 10. And on older CPUs like original 386, is vastly better because hardware multipliers were not nearly as fast as they are now, but shift-and-add via LEA was still cheap. (32-bit and 64-bit addressing-modes allow a 2-bit shift count for the "index" register.) You can do x * 10 = (x<<1) + (x<<3) but that's slower Commented Mar 2 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .