please dont rip this site

PIC Microcontoller Basic Math Methods


32-bit signed integer math routines. add, subtract, multiply, divide, round, sqrt, bin2dec, dec2bin. By Peter Hemsley.

Also, there is a stack based version that implements add, subtract, multiply, and divide in a FORTH like stack based system

32-BIT SIGNED INTEGER MATHS FOR PICS

 

Maths routines for computers, microprocessors and microcontrollers are nothing new. They have been around almost since the invention of the computer, but finding a comprehensive set of routines can be difficult. If you do not have the ability to write your own routines then you must rely on someone else's work. It may be poorly written or incomprehensible due to lack of documentation ,which is often the author's experience. The purpose of this article is to explain how various maths functions are performed and to present a complete 32-bit maths package which can handle huge numbers, and yet not take too much precious memory space. The routines presented here are: Add, Subtract, Multiply, Divide, Round (for divide), Square Root, Binary to Decimal, and Decimal to Binary conversion.

 

MULTIPLE PRECISION

 

An 8-bit register or memory is able to store numbers in the range 0 to 255. If two 8-bit numbers are added together it is quite possible that the sum will exceed 255, so how do we cope with larger numbers? The answer is to use more bits. Imagine a 16-bit register (or memory), this is able to hold numbers up to 65535. You can add numbers to this register many times so long as the total does not exceed 65535. Now split the 16-bit register down the middle into two 8-bit sections. This does not change the nature of the number it contains, but each section can now be stored in adjacent 8-bit (byte) memory locations. The two bytes are usually  referred to as High byte and Low Byte.  Of course the PIC cannot add 16-bit numbers directly, you  must program it to add each byte separately and deal with any overflow from one byte to the next. If you need numbers larger than 65535 this concept can be extended to 24 bits using three bytes for the number, or 32 bits using four bytes. The name given to this  is Multiple Precision Numbers.

 

TWO'S COMPLIMENT

 

General purpose maths routines should be able to cope with negative numbers as well as positive ones. Two's compliment is one of several method for representing both positive and negative numbers. It is a logical extension of unipolar (positive) numbers, which makes it the most widely used method. Other methods such as signed magnitude and offset (also known as biased) are to be found in floating point format numbers and are beyond the scope of this article. A disadvantage of two's compliment is that it works only for addition and subtraction, for other functions the result sign must first be calculated and the numbers made positive before calculating the result.

First we shall look at how two's complement numbers are derived. If an 8-bit register contains a value of  0, when 1 is subtracted from it the result will be FF. Logically this is -1. If 2 is subtracted from 0 the result is FE which is -2, FD is -3 and so on. With an 8-bit register it is possible to represent a numeric range of -128 to +127. For a 16-bit register, -1 = FFFF, -2 = FFFE, -3 = FFFD etc with a range of -32768 to +32767. This concept can be extended to any number of bits you wish although 32 bits is usually considered to be enough. This equates to a  numerical range of -2,147,483,648 to +2,147,483,647. The term "Two's compliment" is derived from the method used to  negate a number, i.e. change it’s sign from positive to negative or vice versa. To do this first invert all the bits of the number, this is known as one's compliment, and then add 1 to the number to obtain the two's compliment.

 

ADDITION AND SUBTRACTION

 

Where a number is more than 8 bits (one byte) long several consecutive bytes are used to store the number, this is called Multiple Precision. It is normally easy enough to add two multiple precision numbers, but the RISC instruction set of the PIC does not allow for carrying any overflow from addition into the next byte. In the author’s experience there often appears to be some confusion of how to do this. Listing 1 shows the correct method of adding two multiple precision  numbers, NUM1 and NUM2. The L, M and H at the end of the variable names refer to Low, Middle and High bytes respectively. The Carry will be correctly set on exit, indicating any overflow from the addition. Subtraction is performed in a similar manner. Another way of subtracting a number is to first negate it (two’s complement) then perform an addition. This eliminates the need for a separate subtraction routine. The arithmetic unit of microprocessors, including PICs, use two’s complement to perform subtractions.

 

Listing1

 

    movf    NUM2L,W     ;Add low bytes
    addwf   NUM1L,F

    movf    NUM2M,W     ;Add mid bytes
    skpnc               ;No carry_in, so just add
    incfsz  NUM2M,W     ;Add carry_in to NUM2
    addwf   NUM1M,F     ;Add and propagate carry_out
    movf    NUM2H,W     ;Add high bytes
    skpnc               ;No carry_in, so just add
    incfsz  NUM2H,W     ;Add carry_in to NUM2
    addwf   NUM1H,F     ;Add and propagate carry_out
    …

 

MULTPLICATION

 

You can perform binary multiplication in the same way that you do decimal long multiplication by hand. Before going into detail we will look at a worked example of multiplying 13 by 10, in binary that is 1101 and 1010.

 

        1101   (multiplicand)

      x1010   (multiplier)

        0000   (partial products)

      1101

    0000

  1101

10000010    (product)

 

Starting with the least significant digit of the multiplier, multiply the multiplicand by each multiplier digit in turn and write the results (partial products) below. Ensure the rightmost digit of each partial product lines up with it’s generating digit in the multiplier. Keep going until you run out of digits in the multiplier. Now add all the partial products together and you have the final result. A quick check of the result confirms it is correct. 128 + 2 = 130.

Now we shall look at how to write a multiply routine in assembler. Since the numbers are binary no multiplication is actually needed because multiplying by zero gives zero as a result, and multiplying by one produces the same number you started with. This just leaves the problem of whether to multiply by 0 or 1. To do this each bit of the multiplicand is shifted into the Carry for testing. If the bit is a 1 then the multiplier (or more correctly, the multiplier times one)  is added to the partial product , if the bit is a 0 then nothing is done since there is no point in adding zero to the partial product. The final task is to ensure the bits are correctly aligned at each addition, this is simply achieved by shifting the partial product in line with the multiplicand.

Listing 2 shows a simplified 8-bit x 8-bit multiply. The variables MPCAND and MPLIER are multiplied to give a 16-bit result in PRODH and PRODL. There are numerous variations of this routine. It is also possible to work from left to right, starting with the most significant digit and shifting left. The best method to choose depends on the processor for which it is written, the number of bits and the programmer’s personal preference.

 

Listing 2

 

mult            clrf    PRODL,F              ;Clear result
                clrf    PRODH,F
                movlw   0x08                 ;Bit
counter
                movwf   COUNT
                movf    MPCAND,W             ;Multiplicand in W reg
loop            rrf     MPLIER,F             ;Lsb into Carry
                skpnc                                     ;Test Carry
                addwf   PRODH,F              ;Add multiplicand to result
                rrf     PRODH,F              ;Align result
                rrf     PRODL,F
                decfsz  COUNT,F              ;Next bit
                goto    loop

                …

 

DIVISION

 

You will probably not be surprised to learn that division is pretty much the reverse of multiplication . Binary division can also be performed in the same way that you do decimal long division by hand, and  again because the numbers are binary no division is actually needed. Where multiplication uses successive shifts and addition, division is done by successive shifts and subtraction.

An example of long division in binary is shown below. Those who are familiar with decimal long division should have no problem with the format, although it has been expanded somewhat for clarity. It shows 15 divided by 3.

 

           0101            (quotient 5 )

0011 ) 1111          (divisor 3 )dividend 15 )

           1                   (partial remainders)

           11

          -11                (subtract divisor)

             0

             01

             011

            -011            (subtract divisor)

                 0             (remainder)

 

The most significant digit of the dividend is put into the partial remainder and compared with the divisor. If  the partial remainder is less than the divisor then the quotient digit is a 0. If the partial remainder is equal to or greater than the divisor, the quotient digit is a 1, the divisor is subtracted and the remainder written below. The next dividend digit is now appended to the new partial remainder and the comparison is repeated until all the dividend digits have been processed. The partial remainder must always remain less than 2 times the divisor, for this reason division is not needed for binary numbers. Unless, of course, you insist that dividing by 1 is a valid argument.

In this example the division is exact i.e. the result is an exact integer. If, for example, 14 were divided by 3 the result would be 4 with a remainder of 2 on the bottom line. Integer division always rounds down to the nearest whole number unless extra code is written to provide rounding up the result if the remainder is 0.5 or more.

Converting the division procedure into an assembler routine is very easy. Listing 3 shows a simple 8-bit by 8-bit divide. Appending to the remainder is done by shifting the msb of the dividend into the Carry and then into the lsb of the remainder. Because of their RISC instruction set PICs do not have a compare instruction so subtract is used to compare the values of the remainder and divisor, the result of the subtraction being held in the W register. Setting the quotient bit is done by shifting in the Carry which was cleared or set by the subtraction.

 

Listing 3

 

divide          clrf    QUOT                   ;Clear quotient
                clrf    REM                    ;Clear remainder
                movlw   0x08                   ;Bit count
                movwf   COUNT
loop            rlf     DIVID,F                ;Shift dividend bit
                rlf     REM,F                  ;into remainder
                movf    DIVIS,W                ;Trial subtraction
                subwf   REM,W
                skpnc
                movwf   REM                    ;Subtraction was ok
                rlf     QUOT,F                 ;Carry is result bit
                decfsz  COUNT,F                ;Next
bit
                goto    loop
                …

 

ROUND

 

As previously mentioned result of division is rounded down, or more correctly truncated, if the result is not an exact integer. We can obtain a more accurate result by rounding up or down to the nearest integer when there is a fractional part to the result. This routine adds 1 to the result if the remainder of the division is 0.1 binary or greater, which is equivalent to 0.5 decimal. This helps to minimise errors caused by multiple uses of division.

 

 

SQUARE ROOT

 

You can square a number simply by multiplying it by itself, square rooting a number is a little more difficult. There are many ways to find the square root of a number, probably the best method for large numbers was described by the same author in the August 2002 issue of EPE. It is very similar to division since the square root of a number is equal to the number divided by it’s square root. The original 24-bit routine has now been expanded to 32-bit.

 

 

GETTING IT IN AND OUT

 

You would like to see the results of all your calculations and would like it to be in decimal, similarly you want to input numbers in decimal. This makes Binary to Decimal and Decimal to Binary routines an essential part of any maths package. Many assembler programmers will at some time have attempted these conversions, usually in a crude fashion. (As were the author’s attempts many years ago) . These methods such as subtracting the binary equivalent of powers of ten are perfectly valid and can be useful, but when it comes to very large numbers there are much better methods available. The Binary to Decimal and Decimal to Binary routines presented here complement each other, they both use the same method but each is the reverse of the other. The method chosen for this package is simplicity itself and very flexible. The routine is compact and easily modified for various bit lengths. A simplified  version is shown in Listing 4. The most significant bit of BINARY is shifted into the least significant digit, ONES. If the digit has a value of 10 or more then 10 is subtracted from it and 1 is added to the next higher digit. The Carry is used to add 1 to the next digit as it will be set by the subtraction if the digit is greater than 9. The rest of the digits are shifted  and checked in a similar manner and the whole process repeated until all the bits of the binary number have been shifted out of BINARY and into the digits. The hundreds digit is not tested in this instance since it cannot overflow as the maximum decimal value for 8-bit binary is 255.

Decimal to Binary consists of the same procedure but doing it all in reverse. Shifting bits through the digits and into the Carry, adding 10 to the digits when necessary and shifting the Carry into the binary.

 

Listing 4

 

                clrf    ONES
                clrf    TENS
                clrf    HUND
                movlw   8                       ;Bit count
                movwf   BCOUNT
loop            rlf     BINARY,F                ;Shift msb into
                rlf     ONES,F                  ;first digit
                movlw   10                      ;Digit > 9 ?
                subwf   ONES,W
                skpnc
                movwf   ONES                    ;Digit = digit -10
                rlf     TENS,F                  ;Shift carry in
                movlw   10                      ;Digit > 9 ?
                subwf   TENS,W
                skpnc
                movwf   TENS                    ;Digit = digit -10
                rlf     HUND,F                  ;Shift carry in
                decfsz  BCOUNT,F                ;Next
bit
                goto    loop

 

USING THE 32-BIT ROUTINES

 

Signed 32-bit numbers have a range of -2147483648 to +2147483647. However -2147483648 does not have a positive equivalent which would needed in many cases and so the range is limited to ± 2147483647, with -2147483648 being trapped as an error. Three 32-bit pseudo-registers are defined, REGA contains the first operand, REGB contains the second operand and REGC is used as temporary storage by the routines. The result is always returned in REGA. Each pseudo-register consists of 4 consecutive bytes denoted by 0, 1, 2 and 3. 0 is the least significant byte and 3 is the most significant byte. High level languages have built-in run-time error checking but assembler has no such luxuries and the programmer must write his/her own. Comprehensive error checking is included in the routines and the Carry will be set on return from the routines if an error is found. The code required  for error checking after calling a routine is shown below.

CALL     <function>

SKPNC

GOTO    <errorhandler>

Because the PICs stack cannot be manipulated errors would usually need to be passed back to the top-most level of the program. Most errors will be caused by an overflow, i.e. the result is greater than 32 bits. When an error is encountered the result returned in REGA will be meaningless. Checking the Carry after calling a routine is optional so long as you are sure no error will occur.

The header of each routine gives a brief description of it’s function and usage. The five basic arithmetic functions are given below for reference.

 

Add:                       REGA = REGA + REGB

Subtract:               REGA = REGA - REGB

Multiply:               REGA = REGA x REGB

Divide:                   REGA = REGA / REGB

Sq Root:                                REGA = SQRT (REGA)

 

Note that multiplying two 32-bit numbers can produce a result of up to 64 bits. A limit on the number of bits has to be drawn somewhere and it is 32, so an error will be returned if the result exceeds the 32 bits of REGA.

The Round routine is intended to be called only after division, it will not round the result of Square Root. Only the simplest of rounding is used since it was considered unnecessary to use a more complex method. Check for division error (if needed) before calling this routine.

The Decimal to Binary routine was designed for flexibility and keypad input in mind. It accepts a variable length BCD string of digits. Your input routine should put the first ( most significant) digit entered in the variable DIGIT1, the next digit into DIGIT2 and so on up to a maximum of 10 digits. A count of the number of digits entered must be kept and loaded into the W register before the routine is called. The reason for this is that people are unlikely to include leading zeros when entering a number to make up the full 10 digits that would otherwise be required, it seems leading zero suppression is in human nature. If your digits are in ASCII text format they should first be converted to BCD format by subtracting 48. It is also worthwhile checking that the digits are in the range of 0 to 9 to avoid the possibility of obtaining a meaningless result. The routine also requires a sign bit to indicate whether the number is positive or negative. This is held in the variable DSIGN which should be set to 0 for a positive number or 1 for  negative.

Binary to Decimal requires little in the way of explanation. DSIGN is again used to indicate a positive or negative number. You may use this to precede the number with  a “+” or “-” in your output routine. No output formatting is included as this will be dependant upon the application.

 

The routines are contained in the file Maths32.txt and are intended to be opened with a text editor such as Notepad and then copied and pasted into your assembly program. You copy all the routines or just the ones you require. But do not forget to also copy the utility routines, most of which will be required. The variable declarations will also need to be copied and you will need supply a start address for them.

The variables require 26 contiguous bytes of data memory but if you do not have this amount available they may be split. Only the variables DIGIT1 to DIGIT10 are required to be contiguous.

 

Code:

Comments:

Questions:

See also:


file: /Techref/microchip/math/32bmath-ph.htm, 39KB, , updated: 2014/4/9 15:38, local time: 2014/12/19 02:58, owner: JMN-EFP-786,
TOP NEW HELP FIND: 
54.145.243.51:LOG IN

 ©2014 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?
Please DO link to this page! Digg it! / MAKE! / 

<A HREF="http://www.piclist.com/techref/microchip/math/32bmath-ph.htm"> 32-bit signed integer math routines. add, subtract, multiply, divide, round, sqrt, bin2dec, dec2bin. By Peter Hemsley.</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

  PICList 2014 contributors:
o List host: MIT, Site host massmind.org, Top posters @20141219 RussellMc, Richard R. Pope, IVP, John Gardner, alan.b.pearce, James Cameron, Bob Blick, David C Brown, Isaac Marino Bavaresco, Josh Koffman,
* Page Editors: James Newton, David Cary, and YOU!
* Roman Black of Black Robotics donates from sales of Linistep stepper controller kits.
* Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters.
* Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated!
* Contributors: Richard Seriani, Sr.
 

Welcome to www.piclist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .