Subtraction:

Multiplication:

Division:

Unpacked BCD Unsigned Addition

Unpacked BCD Addition adds the number in the (X) register to the number in the (Y) register.

This is easily done by mimicking the way you would add up two numbers on paper.

Here's How:

Example: X = 12345, Y = 56789

    56789 (Y register value)
  +12345 (X register value)
  ---------
    69134 (sum)

Begin by using the PIC ADD instruction to add 5 + 9 (one's digit column). Since the processor deals with HEXADECIMAL numbers, the result of this operation will be hex 0x0E. But we need DECIMAL numbers. Since the highest decimal number that can result from the addition of two single digit decimal numbers is 18, the fastest way to convert the hex number into a packed BCD decimal number would be to use a lookup table. So a small binary-to-packed BCD lookup table based subroutine is implemented. Hex 0x0E translates to decimal 14. 14 is a packed BCD number. This is OK because we are going to separate these two nibbles in the next step.

In regular paper addition, you would "bring down" the 4 and "carry" the 1. So let's do the same thing by masking off the high nibble using a logical AND operation, then move the 4 back into the (X1) register. Then swap the nibbles (you would have 41 instead of 14), mask off the high nibble again, leaving the 1. Then add the 1 to the next (Y) register up (the (Y2) register or the 10's place in the (Y) register. So now, the (X) register would read 56784 and the (Y) register would be 12355. The "4" is the answer to the 1's digit addition. The rest of the digits in the (X) register are unaffected at this time. The (Y) register's 1's place has already been manipulated and is not ever going to be looked at again. The (Y) register's 10's place now reflects any carry that may have occurred (in our example, it has gone up in value by 1) and is ready to be processed by the same routine in the next loop.

Even if this "carry" operation resulted in a binary number, this would be OK because the same routine will be done on the 10's digit and the eventual binary addition will be converted to packed BCD once again, and once again separated and added to the next decimal place upward.

The process is then repeated for each of the eight decimal places. Each time the process is completed another one of the (X) registers place values will be replaced with the sum of the (X) and (Y) corresponding place values. The eventual result will be an 8-digit mantissa with a 9th digit calculated for overflow purposes. It will take 8 complete cycles through this routine to complete the addition task.

In the following code example, you can see just how fast this process is. Even if you run the PIC at 4MHz, the result is so fast that the time is virtually neglegable.

Here's the PIC code for how this is done:

Registers/memory locations affected:

INDR--PIC Indirect Addressing Register
FSR--PIC File Select Register
Xx--(X) Register file
Yy--(Y) Register file
FSRx--a temporary register holding the File Select data pointer for the (X) register
FSRy--a temporary register holding the File Select data pointer for the (Y) register
TEMP--a scratchpad register
DIGCTR--loop counter

;8-DIGIT UNPACKED UNSIGNED ADDITION SUBROUTINE
;(C) 1994 LUPINE SYSTEMS, LTD., SKT
;CODE FOR PIC16C6x DEVICES
;RAM USEAGE: 20 BYTES
;ROM USEAGE: 31 BYTES
;PROCESSOR LOAD:  231 CYCLES, @ 4MHz 231uS, @ 12MHz 77uS
;THIS ROUTINE ADDS TWO UNSIGNED UNPACKED 8-DIGIT BCD NUMBERS
;IN SEQUENTIAL FILE REGISTERS X1-X8, Y1-Y8
;RESULTS IN X1-X8, OVERFLOW IF X9 IS NOT ZERO

ADDER	CLRF	X9		;BE SURE CARRY/STATUS REG IS CLEAR!

	MOVLW	X1		;SET UP FSRX, FSRY POINTERS
	MOVWF	FSRX
	MOVLW	Y1
	MOVWF	FSRY

	MOVLW	08
	MOVWF	ADDCNTR		;LOOP COUNTER

NXSUM	MOVF	FSRY,0
	MOVWF	FSR

	MOVF	INDR,0		;GET Y DIGIT
	MOVWF	TEMP2		;SAVE

	MOVF	FSRX,0		;SETUP X DIGIT
	MOVWF	FSR
	
	MOVF	TEMP2,0		;RETRIEVE Y DIGIT FROM TEMP	
	ADDWF	INDR,0		;ADD TO X
	CALL	ADDBCD		;CONVERT
	MOVWF	INDR		;SAVE ON X
	SWAPF	INDR,0		;SWAP TO FIND CARRY IF ANY
	ANDLW	B'00001111'	;MASK OUT HIGH NIBBLE
	INCF	FSR,1		;POINT TO NEXT BYTE IN X
	ADDWF	INDR,1		;ADD!
	DECF	FSR,1		;RESTORE X POINTER
	MOVLW	B'00001111'	;CORRECT CARRY BITS IN X REG
	ANDWF	INDR,1		;SAVE FINAL X VALUE
	
	INCF	FSRX,1		;INCREMENT DATA POINTERS
	INCF	FSRY,1
	DECFSZ	ADDCNTR,1	;LOOP 8 DIGITS
	GOTO	NXSUM
	
	CLRF	XSIGN		;ALWAYS POSITIVE
	MOVF	X9,0		;OVERFLOW?
	BTFSC	Z
	RETURN			;NO OVERFLOW
	MOVLW	0x01
	MOVWF	X9		;ERROR CODE FOR OVERFLOW
	RETURN

Unpacked BCD Subtraction subtracts the number in the (X) register from the number in the (Y) register.

It is done in exactly the same manner as Unpacked BCD Addition is done, except for when the difference between Y and X forms a negative number. In this case, the subtraction has to be done twice in order to reverse the negativity of the difference, or in other words, convert the 2's compliment into a positive integer.

Here's How:

Example: X = 56789, Y = 12345

    12345 (Y register value)
  -56789 (X register value)
  ---------
  -44444 (difference)

Notice that the difference above (-44444) is the same as if you "got rid of the signs, reversed the two terms and subtracted, then made the sign negative". This would work but ONLY if (Y) were always positive. So if we simply went ahead and subtracted the larger number from the smaller number, the software can essentially "borrow on credit" a "1" at the top of the (Y) register stack, leaving the (Y9) register in "underflow" state, and the (Y1) through (Y8) registers representing a 2's compliment result.

Therefore to solve this problem, unlike addition, the rules MUST be considered before the subtraction routine is called. If (X) is numerically greater than (Y) then the subtraction subroutine must be called TWICE -- the first time to subtract the greater number from the lesser, and the second time to subtract the 2's compliment from zero and "borrow on credit" the necessary "1" in the (Y) MSB to complete the subtraction.

Once the second subtraction is completed, then the RULES will assign the sign to the difference.

Remember, if (X) is numerically less than (Y) the subtraction subroutine only has to be run ONCE.

Here's the PIC code for how this is done:

Registers/memory locations affected:

INDR--PIC Indirect Addressing Register
FSR--PIC File Select Register
Xx--X-Register file
Yy--Y-Register file
FSRx--a temporary register holding the File Select data pointer for the X register
FSRy--a temporary register holding the File Select data pointer for the Y register
TEMP--a scratchpad register
DIGCTR--loop counter

;8-DIGIT UNPACKED UNSIGNED SUBTRACTION SUBROUTINE
;(C) 1994 LUPINE SYSTEMS, LTD., SKT
;CODE FOR PIC16C6x DEVICES
;RAM USEAGE: 20 BYTES
;ROM USEAGE: 37 BYTES
;PROCESSOR LOAD:  255 CYCLES, @ 4MHz 255uS, @ 12MHz 85uS
;THIS ROUTINE SUBTRACTS TWO UNSIGNED UNPACKED 8-DIGIT BCD NUMBERS Y-X
;IN SEQUENTIAL FILE REGISTERS X1-X8, Y1-Y8
;RESULTS IN X1-X8, UNDERFLOW IF X9 IS NOT ZERO
;CODE MUST BE RUN TWICE IF X>Y

SUBTCTR	CLRF	X9		;CLEAR OVERFLOW REGISTERS
	CLRF	Y9		
	CLRF	XSIGN
	CLRF	YSIGN		;CLEAR SIGN REGISTERS TOO!

	CALL	SUBT1S		;DO UNSIGNED SUBTRACTION

	MOVF	Y9,0		;IF Y9 IS ZERO THEN WE'RE DONE!

	BTFSC	Z
	RETURN			;ANSWER POSITIVE, IN X REGISTER		

	CLRF	Y1
	CLRF	Y2
	CLRF	Y3
	CLRF	Y4
	CLRF	Y5
	CLRF	Y6
	CLRF	Y7
	CLRF	Y8
	CLRF	Y9		;CLEAR ENTIRE Y REGISTER

	CALL	SUBT1S		;SUBTRACT FROM ZERO

	MOVF	Y9,0
	BTFSC	Z
	GOTO	SUBUNDR		;UNDERFLOW

	CLRF	XSIGN
	BSF	XSIGN,0		;SET SIGN BIT NEGATIVE
	CLRF	X9		;CLEAR ERROR REGISTER
	RETURN
	
SUBUNDR	CLRF	XSIGN
	BSF	XSIGN,0		;SET SIGN BIT NEGATIVE
	MOVLW	0x01		;SHOW UNDERFLOW ERROR
	MOVWF	X9
	RETURN	

;*************************************************************
;8-DIGIT SUBTRACTOR--SUBTRACTS X FROM Y UNSIGNED
;*************************************************************

SUBT1S	MOVLW	X1		;SET UP FSRX, FSRY POINTERS
	MOVWF	FSRX
	MOVLW	Y1
	MOVWF	FSRY

	MOVLW	08
	MOVWF	ADDCNTR		;LOOP COUNTER

NXSUB	MOVF	FSRX,0
	MOVWF	FSR		;SET UP X POINTER

	MOVF	INDR,0
	MOVWF	TEMP2		;SAVE X VALUE

	MOVF	FSRY,0
	MOVWF	FSR		;SET UP Y POINTER

	MOVF	TEMP2,0
	SUBWF	INDR,0		;SUBTRACT!
	CALL	SUBBCD		;CONVERT

	MOVWF	TEMP2		;SAVE CONVERTED DATA

	MOVF	FSRX,0
	MOVWF	FSR		;SET UP X POINTER

	MOVF	TEMP2,0
	MOVWF	INDR		;SAVE ON X REGISTER

	SWAPF	INDR,0
	ANDLW	B'00001111'
	MOVWF	TEMP2		;SAVE MASKED DATA
	
	MOVF	FSRY,0
	MOVWF	FSR		;SET UP Y POINTER
	INCF	FSR,1

	MOVF	TEMP2,0
	SUBWF	INDR,1		;UPDATE Y REGISTER

	MOVF	FSRX,0
	MOVWF	FSR		;SET UP X POINTER
		
	MOVLW	B'00001111'
	ANDWF	INDR,1		;CLEAR OFF CARRY BITS

	INCF	FSRX,1		;UPDATE FSR POINTERS
	INCF	FSRY,1
	DECFSZ	ADDCNTR,1
	GOTO	NXSUB		;LOOP

	RETURN

Unpacked BCD Unsigned Multiplication

Multiplication is the least complicated of the two most complex of the basic functions. Multiplication can consume a lot of processor resources and if not done cleverly, it can also take quite a bit of time (as processors go).

Microprocessors can multiply in many different ways. More recent processors have a hardware multiply feature built-in that can save a lot of time. But most processors do not have such a feature so multiplication must be done the old-fashioned LONG way.

The most common form of processor multiplication is "repetitious addition". This technique adds (X) to itself over and over again until it has added (X) to itself (Y) times. This works fine for small single or double-digit numbers, but when you start multiplying larger numbers repetitious addition eats up an insane number of CPU cycles, and that means that this process may take quite a bit of time.

But there is a much better way of doing this....

Much like when you were in the 3rd Grade and the teacher taught you the multiplication tables, you can teach the processor the multiplication tables too! Once the processor knows the multiplication tables, it can then multiply just as you would with a piece of paper and a pencil.

Multiplication tables are stored in data tables and are accessed using packed term lookup numbers. Example: To find the answer to the common multiplication table value 5 x 9, first compress the two terms into a single "packed" byte -->0x59 (which represents 5 x 9). Then you add this HEX value to the program counter and return with the packed BCD answer 0x45 (representing "40" in the high nibble and "5" in the low nibble).

Here's How:

Example: X = 567, Y = 123

    123 (Y register value)
  x567 (X register value)
  ---------
 69741 (product)

The first step is to multiply 7 x 3 to get 21. On paper you would "bring down" the 1 and "carry" the "2". The "2" would be added to the product of the next step, which would be 7 x 2 for a value of 14, then add the carried "2" for 16. Repeat, bring down the "6" and "carry" the 1. This process would continue until you have multiplied the one's digit of the (X) times each digit in the (Y).

The next step would be to form another line underneath the previous line and enter a "0" in at the 1's place. Then do the same thing as was done before. Beginning with 6 x 3 = 18, bring down the "8", carry the "1". Then 6 x 2 = 12, plus the "1" = 13, bring down the 3 and carry the "1". Keep on going until you have multiplied the 10's digit of the (X) times all of the digits in the (Y).

This process can be simplified. Let's use the same example...

Look at the two numbers: 123 x 567

You will see that each time you do a digit-to-digit multiply, bring down the 1's from that multiply and carry the 10's a pattern emerges:

Do the 1's digit first:

(Remember the numbers are UNPACKED BCD numbers and the most significant byte is ALWAYS zero!

Numbers in RED represent steps that do not have to be done at this time, or represent the zero place value "holder" or "filler" used to fill the lower place values as the multiplication starts moving up the decimal ladder.

This is the exact same thing as if you did regular multiplication on paper bringing down the 1's from each multiply and carrying the 10's. It is just "stretched out" in its most simple form.

The "paper" used by the processor each time one place value in (X) is multiplied times (Y) is the (T) register. Notice in the chart above that the final row of numbers resembles one row of numbers below the line in a paper multiplication.

Now if this is done for each and every place value in the (X) register, then all of the columns added together, you would wind up multiplying (Y)*(X).

Notice that each time the (Y) register place goes up to the next place, a "filler zero" is inserted to hold the previous decimal place. This is because each time (Yz) goes up the value is 10 times the previous place's value (decimal place value system at work!)

Let's now do the 10's digit:

The processor must now add the sums of the first two operations together in a "product" register, or the (P) register. As you can see from the chart, the (P) register can wind up being quite lengthy. In this project, the (P) register is 20-bytes wide.

In the above example, the processor has only completed two of the (X) register digits and has already used the (T5) register. Once all of the (T) register bytes have been totalized into the product (P) register, the (P) register winds up being very lengthy.

Due to the due-dilligence of the processor, the totalization process takes place after each and every set of products. In other words, once the processor finished multiplying (X1)*(Y) it then added the sums to the product register. It can get away with this process because the product (P) register is cleared prior to beginning the multiply routine. So in a sense, after the (X1)*(Y) operation, the totalizer routine adds the sums of the first set of products to zero.

The totalization process is handled by a separate subroutine and is called at the end of the main multiplier subroutine and is part of the process to complete each of the eight passes the multiplier has to pass through to complete the multiplication of an 8-digit number.

The (P) register is now ready to sum with the (X2)*(Y) sequence.

So to catch up, let's add the totals from the first two operations together to form a "running" total, or what would currently be in the (P) register. Add only the green numbers:

You can see that the processor breaks down any "packed" BCD that may occur during the column addition into two unpacked bytes respective of place value. Then it places each byte in the appropriate "cell" within the (P) register. This process needs to take place only once because there are NEVER more than 2 single-digit numbers plus carry added together within any cell at any one given time, and the sum of any two single digit numbers PLUS carry cannot exceed 19 (the CARRY value cannot ever be greater than 1 because the sum of two single digit numbers cannot ever be greater than 18, and the "carry" would be the "1", or 10's digit of this sum). Therefore, since a "running total" is created after each place value has been multiplied, there will always be only TWO single digit numbers plus carry to have to deal with within each cell, which means there cannot EVER be a second carry to have to deal with during the totalization routine.

Since our sample equation is a three-digit number times another three-digit number, the processor only needs to go through one more step. However, the processor will go through all of the stages, including multiplying all of the leading zeros each time, all the way up to 8 digits. The exact same sequence events take place in each stage, only shifted to the LEFT by one decimal position each time a new stage is begun. In this project, this can continue up to 16 times (8 digits x 8 digits). Although this would cause an overflow most of the time, it still has to be done in case someone tries to multiply 1 x 99999999 (remember that 1 is actually 00000001 in a calculator and is 8-digits long). 16 stages of (Xx)*(Yy) results in the need for 20 cells in the (P) register. This is because the cells "overlap" (see the charts above). Although it would actually take 32 cells to fully calculate out 8 digits x 8 digits, anything over 20 cells would be an 8-digit overflow and would be pointless and a waste of processor resources to continue on beyond that point.

So now let's complete the example and do the 100's digit:

Now update the product (P) register and we'll have the final answer.

Therefore, once you pack the BCD digits back together you get the product 69741.

It takes two subroutines to complete the multiplication task. The first routine is the MULTPX subroutine and actually performs the digit-by-digit multiplication. The second subroutine is the totalizer and is called by the main MULTPX routine.

There are several "utility" subroutines also used during the multiply routine. These routines are used to clear the working registers by setting each internal RAM location within the given register to zero.

Here's the PIC code for how the multiplier component is done:

Registers/memory locations affected:

INDR--PIC Indirect Addressing Register
FSR--PIC File Select Register
Xx--(X) Register file
Yy--(Y) Register file
T--(T) Multiplication Line Register File
P--(P) Product Register File
FSRx--a temporary register holding the File Select data pointer for the X register
FSRy--a temporary register holding the File Select data pointer for the Y register
FSTx--a temporary register holding the File Select data pointer for the T register
FSPy--a temporary register holding the File Select data pointer for the P register
DIGCTR--Digit counter used to count which (X) register digit is currently in use
FSRTX--Counter for which (T) register is to be pointed to
M1CTR--Loop counter counting how many times the main core program has been run
TEMP--Temporary data storage scratchpad register
MXCNTR--Loop counter used to point to which stage (1's or 10's) the totalizer is at

SUBROUTINES USED BY THE MULTPX ROUTINE

PCLEAR--Clears the (P) register
TCLEAR--Clears the (T) register
MULTAB--Multiplication Table lookup
SAVFSR--Saves the FSRn registers
ADDTP--Totalizer subroutine, adds up to final product
RESTFSR--Restores FSRn registers from saved values
PXCOPY--Copies value in (P) register to (X) register

;8-DIGIT UNPACKED UNSIGNED MULTIPLICATION SUBROUTINE
;(C) 1994 LUPINE SYSTEMS, LTD., SKT
;CODE FOR PIC16C6x DEVICES
;RAM USEAGE: 93 BYTES (INCLDES INTERNAL SUBROUTINES)
;ROM USEAGE: 102 BYTES (DOES NOT INCLUDE LOOKUP TABLES)
;PROCESSOR LOAD:  1155 CYCLES (INCLUDES ALL INTERNAL SUBROUTINES, @ 4MHz 1.155mS, @ 12MHz 385uS
;THIS ROUTINE MULTIPLIES TWO UNSIGNED UNPACKED 8-DIGIT BCD NUMBERS
;IN SEQUENTIAL FILE REGISTERS X1-X8, Y1-Y8
;RESULTS IN X1-X8, OVERFLOW IF X9 IS NOT ZERO

MULTPX	CALL	PCLEAR		;CLEAR P REGISTER
	CALL	TCLEAR		;CLEAR T REGISTER
	
	MOVLW	X1
	MOVWF	FSRX		;FSR X REGISTER
	
	MOVLW	00
	MOVWF	FSRTX		;FSRT COUNTER REGISTER

	MOVLW	08
	MOVWF	DIGCTR		;SET UP FOR 8 DIGITS

XPLYRR	CALL	TCLEAR		;CLEAR T REGISTER
	MOVLW	(T1-1)
	MOVWF	FSRT		;SET UP FSRT
	INCF	FSRTX,1
	MOVF	FSRTX,0
	ADDWF	FSRT,1		;SET UP FSRT

	MOVLW	08
	MOVWF	M1CTR		;LOOP COUNTER

	MOVLW	Y1
	MOVWF	FSRY		;FSR Y REGISTER
	
MLXLOOP	MOVF	FSRY,0
	MOVWF	FSR
	SWAPF	INDR,0
	ANDLW	B'11110000'	;BE SURE MASKED
	MOVWF	TEMP		;MIX INTO PACKED BCD

	MOVF	FSRX,0
	MOVWF	FSR
	MOVF	INDR,0
	ANDLW	B'00001111'
	IORWF	TEMP,0
	CALL	MULTAB
	MOVWF	TEMP
	MOVF	FSRT,0
	MOVWF	FSR
	MOVF	TEMP,0
	MOVWF	INDR		;SAVE IN T REG FILE
	INCF	FSRY,1
	INCF	FSRT,1
	DECFSZ	M1CTR,1
	GOTO	MLXLOOP
	
	CALL	SAVEFSR		;SAVE FSR'S
	CALL	ADDTP		;ADD T TO P
	CALL	RESTFSR		;RESTORE FSR'S
	INCF	FSRX,1		;NEXT X

	DECFSZ	DIGCTR,1
	GOTO	XPLYRR

	CALL	PXCOPY		;COPY PRODUCT REG TO X REG

	MOVF	X9,0		;CHECK FOR OVERFLOW
	BTFSS	Z
	GOTO	FCERR
		
	CLRF	TEMP		;CLEAR TEMP REG

	MOVLW	10
	MOVWF	DIGCTR		;LOOP

	MOVLW	P10
	MOVWF	FSR

ERDET	MOVF	INDR,0		;CHECK FOR OVERFLOW
	ADDWF	TEMP,1
	INCF	FSR,1
	DECFSZ	DIGCTR,1
	GOTO	ERDET

	MOVF	TEMP,0
	BTFSS	Z
	GOTO	FCERR
	CLRF	X9		;NO ERROR
	RETURN

FCERR	MOVLW	0x01		;UNDERFLOW ERROR CODE
	MOVWF	X9
	
	RETURN

;*************************************************************
;TOTALIZER-PRODUCT GENERATOR SUBROUTINE
;*************************************************************
	
ADDTP	MOVLW	T1		;SET UP FSRT, FSRP POINTERS
	MOVWF	FSRT
	MOVLW	P1
	MOVWF	FSRP

	MOVLW	16
	MOVWF	ADDCNTR		;LOOP COUNTER

NMX	MOVLW	02
	MOVWF	MXCNTR		;STAGE COUNTER
	
CXTP	MOVF	FSRT,0
	MOVWF	FSR		;SET UP FSRT
	
	MOVF	INDR,0		;GRAB Tx
	MOVWF	TEMP2

	MOVF	FSRP,0
	MOVWF	FSR		;SET UP FSRP

	MOVF	TEMP2,0		;GET Tx DATA
	BTFSS	MXCNTR,1	;FIRST OR SECOND STAGE?
	SWAPF	TEMP2,0

	ANDLW	B'00001111'
	ADDWF	INDR,0		;INDR POINTS TO P REGISTER
	CALL	ADDBCD		;CONVERT
	MOVWF	INDR		;SAVE IN Px
	SWAPF	INDR,0		;SWAP Px NIBBLES
	ANDLW	B'00001111'
	INCF	FSR,1		;POINT TO Px+1
	ADDWF	INDR,1		;CARRY!
	DECF	FSR,1		;RESTORE Px
	MOVLW	B'00001111'
	ANDWF	INDR,1		;MASK OUT CARRY BITS FROM PREV ADD

	INCF	FSRP,1		

	DECFSZ	MXCNTR,1
	GOTO	CXTP
	
	INCF	FSRT,1		;NEXT SET OF BYTES...

	DECF	FSRP,1		;RESTORE FSRP FOR NEXT PHASE
	DECFSZ	ADDCNTR,1
	GOTO	NMX

	RETURN

Wow! OK, you've made it through that tough multiply subroutine. But to the processor it was a cinch! Are you ready to explore division?? The most difficult of the four basic functions???

Unpacked BCD Unsigned Division

Division is by far the most complicated of the four basic functions. As I heard in a computer seminar back in the 1970's...

"There is no easy way to teach a microprocessor how to do division."

And that says it all. It is NOT an easy task. To most programmers, addition, subtraction and multiplication are child's play. But division has been a stick in the mud for many-a-programmer over the years. Many of the issues has to do with peculiar processor archetecture. Other problems stem from the simple fact that there are so many "assumed" steps to go through that by the time the processor completes each of these steps, well, it's tomorrow.

One method of doing division is "repetitious subtraction". This is where the divisor is subtracted from the dividend over and over again, counted each time, and keeps on going until the result goes negative. The number of successful subtractions makes up the quotient and whatever is left over is the remainder.

But as you can probably guess this takes an eternity in processor time and is simply impractical when it comes to large numbers divided by small numbers.

But, as always, there is an easier way around all of this. Use logarithms.

The basic idea is to first figure out how many significant digits there are in the dividend (Y). Then, locate the HIGHEST 2's log (2⁰, 2¹, 2², 2³, etc. You are looking for the exponent part) that has that same number of digits. Then, multiply the divisor (X) times that log and subtract the product from the dividend (Y). If the results of the subtraction is negative, then reduce the log by 1 and try again. Eventually you will land on some log of 2 that, when multiplied times the divisor (X), will subtract from the dividend (Y) and give a POSITIVE number. When that happens, the current value of 2^(exp) becomes "part" of the quotient. The difference from the dividend-log subtraction now becomes the dividend (Y), and the process repeats. Each time you land on a log of 2 that "fits" the log value is added to the quotient. Eventually you will wind up at 2⁰, which is 1. If the divisor (X) is less than the current dividend (Y), add 1 to the quotient, and whatever is left over in the (Y) register after subtracting the divisor (X) is the remainder. If this subtraction is negative, then the quotient has already been found and whatever happens to be left over in the (Y) register is the remainder. Sound simple enough huh??

The fastest way to realize this process when working with unpacked BCD numbers is to store the logarithms of 2 in a data table. Also, the "high log" information is stored in a data table. Use of these data tables means the processor does not have to calculate the log each time around and thus saves precious clock cycles.

Here's How:

First, let's present to you for your reference a table of logarithms of 2. Refer to this table throughout this explination.

For our example, let's use the following equation:

	679394
	------	= 97,056 remainder 2
	7

The number 679394 is the value of the (Y) register and 7 is the value of the (X) register.

The first step is to figure out how many significant digits there are in the (Y) register. This is done by first setting up a loop counter starting with the value of 8 (8 because there are 8 digits), then using the value of the loop counter as a data pointer to point to one of the internal RAM cells of the (Y) register. The test begins by testing the highest byte of the (Y) register (Y8) for zero, then the next byte (Y7), then (Y6), etc. until a non-zero digit is found. Once a non-zero digit is found, the value currently in the loop counter will be the number of significant digits. This number is then passed off to a subroutine that "looks up" the highest logarithm with the same number of significant digits. This would be the highest possible logarithm that could be subtracted from (Y) without going negative.

Example: 679394 is actually 0 0 6 7 9 3 9 4 to the calculator (the leading zeros are simply blanked on the display). The loop routine would start out with 8 in it's loop counter so it would test Y(8) first, which is zero, so it would then decrement the loop counter once. Now the loop counter is 7 so the next cell to test would be (Y7), which is also zero. Then it would once again decrement the loop counter once. Now the loop counter is 6 so the next (Y) register cell to test would be (Y6). This time the routine would find the (Y6) register to be non-zero. The routine would then exit, leaving the data value in it's loop counter 6, which is the number of significant digits in the (Y) register.

This data is then passed along to the HIGHLOG subroutine to determine what log of 2 is the highest for 6 significant digits. The highest log of 2 with 6 significant digits is 524,288, or 2¹⁹. So the HIGHLOG subroutine would return to the main program with the value 19, representing 2¹⁹. This value is now saved in a register named LOGREG.

Now the fun begins....

Since the software deals with unpacked BCD digits, AND the MULTIPLY routine has to be used, some housekeeping must be done so that the multiply routine can be called without destroying the current (X) and (Y) registers' data entered by the user on the keyboard.

Remember that the multiply routine uses the (X), (Y), (P) and (T) registers so none of these registers can be used to "save" the arguements during the divide routine.

So several new registers are created along with their service routines. The service routines move data between the registers and/or clear them to zero.

Logarithms of 2 up to 2²⁶ are saved in log tables in unpacked BCD format. A retrival subroutine (LOG2X) is used to move the log from the data table into the (X) register.

Now that we can copy the registers back and forth and read logs from a data table, the PIC can perform the necessary math to figure out our division example.

Before anything else is done, the values contained in (X) and (Y) must be saved. (X) is saved in the (Z) register. (Y) is saved to the (B) register.

Begin by multiplying the highest log determined by the HIGHLOG subroutine with (X) and subtract from (Y). If negative, the log is too big. If zero or greater, then the log "fits".

Example: HIGHLOG says the highest log that matches the number of significant digits in (Y) is 2¹⁹ or 524,288. So let's multiply 524,288 * (X).

Currently (X) value is saved in (Z). It needs to be moved to the (Y) register.

Now get the value of the log into the (X) register.

Now multiply (X)*(Y) by calling the MULTPX subroutine. This is the RAW multiplier subroutine.

The value in (X) is now the divisor times the highest log for the number of significant digits in (Y).

The next step would be to subtract this newly multiplied value from the dividend. (Y) is saved in the (B) register.

In our example, this subtraction is NEGATIVE. So from this it can be determined that:

2¹⁹ is too high. Try again!

The next step is to decrement the value in LOGREG and run through the process again and repeat doing so until a POSITIVE result is reached.

This process will continue until the software hits paydirt at 2¹⁶, or 65536. Remember that the number "being subtracted from the dividend" is "the log times the divisor", not the "exponent" of the log.

At this time, the LOG value (2¹⁶ or 65,536) is now part of the quotient but not all of it. The process must continue until each and every log all the way down to 2⁰ has been tested. Each time the product of the (log value )* (divisor) can be subtracted from the running dividend without going negative, the log value is added to the quotient (Q) register.

Now the software must ADD the log to the quotient register. But first, the difference found in the subtraction above now becomes the new dividend, or the new (Y) value. Earlier this difference was saved on the (P) register, so:

The new (Y) value in this example is 220642.

The software will now repeat this entire process over and over again, each time modifying the contents of the (Y) register and adding logs to the (Q) register until 2⁰ is reached.

The first log that fit was 2¹⁶ or 65,536. After the first loop, the value in (Y) is 220642. The value in (Q) is 65,536.

Log 2¹⁵ does not fit. The difference goes negative.

The next log that fits is 2¹⁴ or 16,384. After the loop, the value in (Y) is 105954. The value in (Q) is 81,920.

The next log that fits is 2¹³ or 8192. After the loop, the value in (Y) is 48610. The value in (Q) is 90,112.

The next log that fits is 2¹². After the loop, the value in (Y) is 19938. The value in (Q) is 94,208.

The next log that fits is 2¹¹. After the loop, the value in (Y) is 5602. The value in (Q) is 96,256.

Log 2¹⁰ does not fit. The difference goes negative.

The next log that fits is 2⁹. After the loop, the value in (Y) is 2018. The value of (Q) is 96,768.

The next log that fits is 2⁸. After the loop, the value in (Y) is 226. The value in (Q) is 97,024.

Logs 2⁷ and 2⁶do not fit. The differences go negative.

The next log that fits is 2⁵. After the loop, the value in (Y) is 2. The value in (Q) is 97,056.

2⁴ does not fit. Neither does 2³, nor does 2². Nor does 2¹. When LOGREG reaches zero, a set of steering bits will direct the code to run the log 2⁰. Since 2⁰ equals 1, the result would be to see if the actual divisor can be subtracted "one more time" from the running dividend. If so, then the quotient register is incremented by 1 and what's left over is moved to the (Y) register and represents the "remainder" in the final quotient-remainder answer. If not, then the process is complete.

In the example, the difference goes negative. Therefore, the value in (Q) is the quotient and the value in (P) is the remainder. The value in (P) is then copied to the (Y) register.

The final step is to move the data in the (Q) register to the (X) register and set the quotient bit so that the display handling routine can display the remainder symbol on the display when the (x<>y) key is pressed.

Here is the PIC code for how this is done:

Registers/memory locations affected:

INDR--PIC Indirect Addressing Register
FSR--PIC File Select Register
Xx--(X) Register file
Yy--(Y) Register file
P--(P) Product Register File
Q--(Q) Quotient Register File
B--(B) Baseline Register File
Z--(Z) Scratchpad Register File
FLAGS--Steering Flags Register
DIGCTR--Digit counter
TEMP--Temporary data storage scratchpad register, loop counter
LOGREG--Register to hold current logarithm
All registers associated with the MULTPX subroutine
All registers associated with the ADDER subroutine
All registers associated with the SUBT2S subroutine

SUBROUTINES USED BY THE DIVIDER ROUTINE

PCLEAR--Clears the (P) register
TCLEAR--Clears the (T) register
QCLEAR--Clears the (Q) register
BCLEAR--Clears the (B) register
ZCLEAR--Clears the (Z) register
MULTPX--Multiplication Subroutine
SUBT2S--Subtraction Subroutine
ADDER--Addition Subroutine
LOG2X--Logarithm Retrieval to (X) Subroutine
HILOG--Looks up highest log for given significant digits
BYCOPY--Copies value in (B) register to (Y) register
QXCOPY--Copies value in (Q) register to (X) register
QYCOPY--Copies value in (Q) register to (Y) register
YBCOPY--Copies value in (Y) register to (B) register
XPCOPY--Copies value in (X) register to (P) register
XQCOPY--Copies value in (X) register to (Q) register
XZCOPY--Copies value in (X) register to (Z) register
ZXCOPY--Copies value in (Z) register to (X) register
PXCOPY--Copies value in (P) register to (X) register
XYSWAP--Swaps the values between (X) and (Y) registers

;8-DIGIT UNPACKED UNSIGNED DIVISION SUBROUTINE
;(C) 1994 LUPINE SYSTEMS, LTD., SKT
;CODE FOR PIC16C6x DEVICES
;RAM USEAGE: VARIABLE, MINIMUM 92 BYTES
;ROM USEAGE: 88 BYTES (DOES NOT INCLUDE LOOKUP TABLES)
;PROCESSOR LOAD:  VARIABLE (LONGEST TIME @4MHz 264mS @12MHz 88mS TYP 982uS
;THIS ROUTINE DIVIDES TWO UNSIGNED UNPACKED 8-DIGIT BCD NUMBERS (Y)/(X)
;IN SEQUENTIAL FILE REGISTERS X1-X8, Y1-Y8
;QUOTIENT IN X1-X8, REMAINDER IN Y1-Y8, ERROR BIT IN X10

DIVDR	CLRF	X9
	CLRF	XSIGN
	CLRF	Y9
	CLRF	YSIGN			;UNSIGN ALL OPERANDS

	CALL	TCLEAR
	CALL	PCLEAR			;CLEAR WORK REGISTERS
	CALL	QCLEAR			
	CALL	ZCLEAR
	CALL	BCLEAR
	BCF	ZEROLOG			;RESET ZERO LOG BIT

	MOVLW	08
	MOVWF	DIGCTR			;DIVIDE BY ZERO CHECK
	
	CLRF	TEMP			;USE TEMP AS CHECKSUM REG
	
	MOVLW	X1
	MOVWF	FSR			;DO X REGISTER CHECKSUM

XZCHECK	MOVF	INDR,0
	ADDWF	TEMP,1			;ADD IT UP!
	INCF	FSR,1			;NEXT BYTE
	
	DECFSZ	DIGCTR,1
	GOTO	XZCHECK			;LOOP AROUND...

	MOVF	TEMP,0
	BTFSC	Z			;IF ZERO, THEN X=0, NO GO!
	GOTO	DIVERROR		;EXIT IN ERROR
	
	CALL	YBCOPY			;SAVE OPERANDS
	CALL	XZCOPY			

	MOVLW	08
	MOVWF	DIGCTR			;LOOP

	MOVLW	Y8
	MOVWF	FSR			;FIGURE OUT HIGHEST DIGIT

TFH	MOVF	INDR,0
	
	BTFSS	Z
	GOTO	HIGHDIG			;HIGHEST DIGIT FOUND NOT Z

	DECF	FSR,1			;NEXT DIGIT
	DECFSZ	DIGCTR,1		;LOOP
	GOTO	TFH			;TEST FOR HIGH DIGIT

	GOTO	DIVZERO 		;ALL DIGITS ZERO -- 0/? IS ALWAYS ZERO (EXCEPT ZERO)		

HIGHDIG	MOVF	DIGCTR,0
	ANDLW	B'00001111'		;BE SURE MASKED!
	CALL	HILOG			;HIGHEST LOG POSSIBLE!
	MOVWF	LOGREG			;SAVE IN LOG REGISTER

NWLOG	CALL	ZXCOPY			;MOVE SAVED DIVISOR TO Y
	CALL	XYSWAP			;MOVES X TO Y
	CLRF	Y9
	
	CALL	XCLEAR			;CLEAR X REGISTER
	CALL	LOG2X			;MOVE LOG TO X REGISTER
	CALL	MULTPX			;MULTIPLY LOG TIMES DIVISOR
	MOVF	X9,0
	BTFSS	Z
	GOTO	NEXTLOG			;THIS LOG WAY TOO BIG!

	CALL	BYCOPY			;RESTORE DIVIDEND
	CLRF	Y9
	CLRF	X9
	CLRF	XSIGN
	CLRF	YSIGN
	CALL	SUBT1S			;SUBTRACT!
	CALL	XPCOPY			;SAVE IN P REG

	MOVF	Y9,0
	BTFSS	Z
	GOTO	NEXTLOG			;OVERFLOW

	CALL	QYCOPY			;COPY Q TO Y
	CALL	XCLEAR
	CALL	LOG2X			;GET LOG AGAIN
	CALL	ADDER
	CALL	XQCOPY			;SAVE QUOTIENT BUILD
	
	CALL	PXCOPY
	CALL	XYSWAP
	CALL	YBCOPY			;RESTORE DIVIDENDS!

NEXTLOG	BTFSC	ZEROLOG			;ZERO LOG BIT
	GOTO	ZLOG
	DECFSZ	LOGREG,1
	GOTO	NWLOG
	BSF	ZEROLOG			;SET ZERO LOG BIT
	GOTO	NWLOG			;DO THE SAME FOR ZERO

ZLOG	BCF	ZEROLOG			;RESET ZERO LOG BIT

	CALL	QYCOPY			;GET QUOTIENT
	CALL	XCLEAR
	
	CALL	BYCOPY			;REMAINDER IN Y REG
	CALL	QXCOPY			;QUOTIENT IN X REG
	
DIVEX
	CLRF	X9
	CLRF	XSIGN
	CLRF	Y9
	CLRF	YSIGN
	BSF	DIVXFLAG		;DIVISION

	RETURN	

DIVZERO	
	CALL	XCLEAR		;QUOTIENT IS ZERO
	CALL	YCLEAR		;NO REMAINDER
	GOTO	DIVEX		;DO HOUSEKEEPING AND EXIT

Steering Software

Now that all four of the math functions have been dealt with it's time to piece it all together into a functional machine. Since steering software is basic in nature, I will only provide a brief overview of the steering software.

A series of steering routines hold it all together. The first of these routines is a keyboard scan routine. The keyboard is matrixed into a 4-row x 6-column array with columns driving and rows receiving. The PIC sequences through each column, setting the active column LOW. Then it scans each row to see if it is LOW at the time of the scan. If so, the scan stops and the software assigns a key "code" to a keycode register to represent the closed key. Then the key is debounced to prevent false and/or repeat entries.

The command interpreter component reads the keycode returned from the keyscan routine and determines whether it was a number key or a function key. This is easily accomplished by assigning all number keys to have zero as the most-significant nibble in the keycode. All other keys have 1 as the most-significant nibble. The code is discriminated and the processor is sent to an appropriate handling routine to process the given command. Since the calculator uses algebraic entry, the command is saved by setting a series of flag bits and awaits either the equals key or another command before it actually executes the given command. This way you can enter numbers as you would write them on paper and do hand-arithmetic.

Finally, the display. The display outputs the contents of the (X) register. Display multiplexing is handled by using the interrupts. The interrupt is generated by an overflow of the PIC TMR0 register. TMR0 is set up for internal clock with a 1:4 prescaler. When the interrupt service routine is entered, all of the working registers and FSR pointer registers are saved, then the routine outputs data to the display beginning with the 10th or furthest left display. A set of steering instructions determine whether the particular readout is the overflow or error display, and another set of steering instructions complete the leading-zero-blanking function.

Data Tables

This project is made possible by the use of data tables. The calculator relies on these data tables much like you rely on your memory to do math in your head or on paper.

The code incorporates the following data tables:

Some programmers have it in their head that data tables are a way to cheat. But in reality there is no such thing as "cheating" when doing computer software. What some label as cheating is actually another programmer's clever ability to solve a code problem in an elegant fashion. In the case here, the need is SPEED. Math routines are classically slow. PCs, for example, do not even do them!! In early PCs, all of the math was done by the main processor using routines like the ones demonstrated here. More advanced PC processors allowed for the addition of a "math co-processor", or "processor calculator" chip to be added to the system. If the software detected this chip, a different set of math routines were used -- new routines that would pass off the math to the co-processor, thus speeding up the PC greatly. The early Pentium processors were the first PC processors to have a built-in math co-processor that was a genuine hardware calculator and Windows95 was the first PC software to take this to full advantage. So many folks thought that the new 70MHz machines got their speed from the fast clock. It was not just the faster clock, it was the fact that the processor no longer had to do math the long way.

A Final Note

The routines outlined in this section can and could be modified for processor effiency, however these routines were written for speed at the expense of processor resources.

Let me suggest that you play around with the code, maybe even figure out for yourself how to add a floating-point decimal (which will be explained in a future article). You can copy the code over to a larger PIC, one with more memory and use this calculator as the "core" for a much bigger machine. Or you can modify the display routine to handle direct LCD, or maybe, if you are nostalgic, Nixie tubes!