From s.wieman@student.utwente.nl Sat Aug 05 09:06:06 1995 Newsgroups: comp.sys.m68k Path: news.nic.utwente.nl!news.nic.surfnet.nl!sun4nl!EU.net!newsfeed.internetmci.com!news.uoregon.edu!news.bc.net!info.ucla.edu!news.ucdavis.edu!csus.edu!netcom.com!ludis From: ludis@netcom.com (Ludis Langens) Subject: Re: Divide by 10 in 68k-asm Message-ID: Organization: Netcom Online Communications Services (408-241-9760 login: guest) References: <1995Aug1.151745.3471@arbi.Informatik.Uni-Oldenburg.DE> <3vo0ap$19q@globe.indirect.com> Date: Thu, 3 Aug 1995 11:01:19 GMT Lines: 97 Sender: ludis@netcom16.netcom.com In article <3vo0ap$19q@globe.indirect.com> Larry Battraw wri tes: >ludis@netcom.com (Ludis Langens) wrote: >>What do you need this for? If it is for binary to decimal conversion, >>there is a better way that doesn't use any divides, multiplies, or table >>lookups. This better method is also faster unless you have a fast >>hardware divide. > > Please enlighten us with what this method is! I have yet to come across a >satisfactory way to do such a thing... I'll first describe how and why this algorithm works. Then I'll include a code fragment implementing the core of the algorithm. Lets start with an example. A binary value can be expressed as the sum of the value of each non-zero digit. Like this: %10100010 = 128 + 32 + 2 If the addition (128 + 32 + 2) is carried out in BCD, then it is simple to come up with the decimal value 162. A general solution is this: num = num[7] * 2^7 + num[6] * 2^6 + num[5] * 2^5 + ... + num[0] * 2^0 Now you are probably thinking you need a table of the powers of 2 in BCD and that you need to do many multiplies (in BCD, no less!). Lets perform some algebra on the equation: num = (((num[7] * 2 + num[6]) * 2 + num[5]) * 2 + ... num[1]) * 2 + num[0] The powers of two are no longer needed. And multiplication by two is the same as adding a value to itself. Thus, each step becomes this: result <= result + result + num[n] The 680x0 happens to have an instruction that does just this operation on BCD values! ABCD.B D0,D0 ; D0 <= D0 + D0 + X Thus, all that is needed is to shift each binary bit from msb to lsb into the X flag and then include it in the BCD result. This same algorithm can be used to convert from any radix to any other radix. Lets try converting from decimal back to binary: 162 = 100 + 60 + 2 = 1 * 100 + 6 * 10 + 2 * 1 = (1 * $A + 6) * $A + 2 In this case, the multiplies and adds are carried out in binary (the destination radix). This probably looks just like any standard decimal to binary conversion function. Performance of the binary to decimal conversion can be improvde by skipping any leading zero bits before starting the BCD doubling stage. This code example also uses an end flag bit directly in the value being converted to cause the proper number of iterations. ... ;Enter with binary value in D0 CLR.B D1 CLR.B D2 CLR.B D3 CLR.B D4 CLR.B D5 NEG.L D0 ;Check for zero BEQ.S @2 NEG.L D0 ;Restore value and set X @0 ADDX.L D0,D0 ;Left align value BCC.S @0 @1 ABCD.B D1,D1 ;Double and add X ABCD.B D2,D2 ABCD.B D3,D3 ABCD.B D4,D4 ABCD.B D5,D5 ADD.L D0,D0 ;Next bit to X BNE.S @1 @2 ... Lets compare execution speed versus an algorithm that uses divides: For each of about 32 bit positions, a software divide needs to shift the divisor or dividend, do a trial subtract, branch conditionally, shift the result and insert a 1 or 0 result bit, and finally reloop. This is five (or more) instructions which need to be repeated about 32 times. The above code fragment has seven instructions repeated as many as 32 times. However, the divide method only cranks out one decimal digit whereas the ABCD method produces all ten! (They do however need to be unpacked from BCD into ASCII and leading zeroes may need to be suppressed.) I first used this algorithm on a Z80 where divides are quite difficult. It can be easily implemented on any CPU that has BCD capabilities (6502, 80x86, etc.) It can even be done on RISC CPUs which usually lack an ABCD instruction because such an add is easy to simulate with some ANDs, ORs, and shifts. Ludis Langens ludis@netcom.com