The Case For Biquinary
|
From: jsavard on 6 Apr 2005 20:16 Terje Mathisen wrote: > Does it really save any time and/or hw resources? Chen-Ho encoding is quite fast for converting from the encoded form to BCD. > If all your math is add/sub, then decimal is relatively efficient, but > if you have to do quite a bit of multiplication as well, i.e. rate > calculation with 5 decimals, then it would seem that you need a _lot_ of > decimal multipliers? Ah. So you are saying that base-1024 multiplication might be faster than BCD multiplication. But fast multipliers today use multi-bit methods; one old computer used the brute force method of multiplying, in parallel, one operand by each number from 2 to 9, and then adding together the required results (plus the original number, plus the possibility of not adding) under the control of the operand to form the result. So if adding in decimal is reasonable, multiplying in decimal is reasonable - it can be done quickly, even with extra transistors. John Savard
From: Terje Mathisen on 7 Apr 2005 06:08 jsavard(a)ecn.ab.ca wrote: > Terje Mathisen wrote: > >>Does it really save any time and/or hw resources? > > > Chen-Ho encoding is quite fast for converting from the encoded form to > BCD. CHen-Ho or DPD really shouldn't matter, it is effectivly either a small lookup table or a few levels of discrete logic. (CH might require a bit less logic than DPD, I haven't studied it.) Making it really fast would seem to require a full lookup table, or at least something quite close: DPD uses 4 bits for the least significant decimal digit, then three bits for the two others. The least signficant bit in each digit is always kept in the same (correct) location, while the (2+2+3) 7 remaining bits changes meaning to allow the top two decimal digits to contain 8 or 9 (i.e. 4 since the lsb is kept separate). So a piece of logic that routes 7 of the 10 bits into a lookup table with 9 output bits, while sending the last three straight through, will do DPD decoding in the time required for that 128*9 = 1152 bit table. Since a sw version of the same logic would like to avoid shifting and masking, I would use a larger table, with 9 input bits and 16 (really 11) output bits, and only the bottom bit bypassing the lookup: ; DPD value in EBX mov eax, ebx and ebx,1022 ; Mask away the bottom bit and eax,1 ; Keep it here mov ebx,dpd_2_bcd[ebx] ; 16-bit wide lookup table or eax,ebx This table requires 2 kB. > >>If all your math is add/sub, then decimal is relatively efficient, > > but > >>if you have to do quite a bit of multiplication as well, i.e. rate >>calculation with 5 decimals, then it would seem that you need a _lot_ > > of > >>decimal multipliers? > > > Ah. So you are saying that base-1024 multiplication might be faster > than BCD multiplication. > > But fast multipliers today use multi-bit methods; one old computer used > the brute force method of multiplying, in parallel, one operand by each > number from 2 to 9, and then adding together the required results (plus Nice hack! :-) > the original number, plus the possibility of not adding) under the > control of the operand to form the result. > > So if adding in decimal is reasonable, multiplying in decimal is > reasonable - it can be done quickly, even with extra transistors. Adding in decimal (BCD) isn't really fast, you probably have to start by pre-biasing one of your numbers by 6666666..., so that you can use the overflow out of each BCD digit to handle carry propagation, then subtract the bias afterwards. OTOH, for a big set of additions into a single accumulator, it should be OK to add the bias once, do all the bcd adds, then subtract it at the end. .... Hmmm, maybe not too slow after all? Terje -- - <Terje.Mathisen(a)hda.hydro.com> "almost all programming can be viewed as an exercise in caching"
From: Terje Mathisen on 7 Apr 2005 15:50 Terje Mathisen wrote: > Adding in decimal (BCD) isn't really fast, you probably have to start by > pre-biasing one of your numbers by 6666666..., so that you can use the > overflow out of each BCD digit to handle carry propagation, then > subtract the bias afterwards. > > OTOH, for a big set of additions into a single accumulator, it should be > OK to add the bias once, do all the bcd adds, then subtract it at the end. > > .... Hmmm, maybe not too slow after all? Sorry, I have to correct my own error here: Each and every carry out must also generate a new bias add into the current digit. I.e. you'll need to generate the carries into a separate register, then shift those bits back down by 2 and 3 positions (to generate the '6' value), and finally add it back in. I think this is the point in time where I could usefully do a little google for sw bcd math libraries, but that would take away all the fun. :-) Terje -- - <Terje.Mathisen(a)hda.hydro.com> "almost all programming can be viewed as an exercise in caching"
From: glen herrmannsfeldt on 18 Apr 2005 04:05 Terje Mathisen wrote: (snip) > Each and every carry out must also generate a new bias add into the > current digit. > I.e. you'll need to generate the carries into a separate register, then > shift those bits back down by 2 and 3 positions (to generate the '6' > value), and finally add it back in. > I think this is the point in time where I could usefully do a little > google for sw bcd math libraries, but that would take away all the fun. :-) Many processors, I believe starting with the 8080 have a half carry flag in their 8 bit adders. The DAA instruction, decimal adjust for addition, adds the appropriate 6 depending on that bit and the regular carry bit. -- glen
From: =?iso-8859-1?q?Torben_=C6gidius_Mogensen?= on 18 Apr 2005 07:06
glen herrmannsfeldt <gah(a)ugcs.caltech.edu> writes: > Many processors, I believe starting with the 8080 have a half carry > flag in their 8 bit adders. The DAA instruction, decimal adjust for > addition, adds the appropriate 6 depending on that bit and the regular > carry bit. The 6502 had a BCD "mode" (set and cleared with SED and CLD instructions) that made additions and subtractions use BCD. IIRC, the arithmetic operatons didn't take extra cycles when in decimal mode. Torben |