COP400 C1995 RRD-B30M105 - Datasheet Archive

 

COP Brief 2 September 1986 Logarithms have long been a convenient tool for the simplification of multiplication division and root

 

National Semiconductor COP Brief 2 September 1986 Logarithms have long been a convenient tool for the simplification of multiplication division and root extraction Many assembly language programmers avoid the use of logarithms because of supposed complexity in their application to binary computers Logarithms conjure up visions of time consuming iterations during the solution of a long series The problem is far simpler than imagined and its solution yields for the applications programmer the classical benefits of logarithms 1) Multiplication can be performed by a single addition 2) Division can be performed by a single subtraction 3) Raising a number to a power involves a single multiply 4) Extracting a root involves a single divide When applied to binary computer operation logarithms yield two further important advantages First a broad range of values can be handled without resorting to floating point techniques (other than implied by the characteristic) Second it is possible to establish the significance of an answer during the body of a calculation again without resorting to floating point techniques Implementation of base10 logarithms in a binary system is cumbersome and unnecessary since logarithmic functions can be implemented in a number system of any base The techniques presented here deal only with logarithms to the base2 In Figure 1 some points on the logarithmic curve are identified and evaluated to the base2 Notice that the characteristic in each case represents the highest even power of 2 contained in the value of X This is readily seen when binary notation is used A logarithm consists of two parts an integer characteristic and a fractional mantissa X10 X2 Log2 X Log2 X Where X e 24 23 22 21 20 Characteristic Even Power of 2 3 4 8 10 0 0 0 0 0 0 U 1 1 0 U 0 0 1 U 0 0 0 1 U 0 1 0 1 FIGURE 2 Identification of the Characteristic 1000 0111 0110 0101 0100 0011 Characteristic 011 0000 TL DD 6942 ­ 1 1 0 95 2 0 00 LOG2 8 e LOG2 10 e 3 0 00 3 0 52 Value of X in Binary 0000 0001 0010 0100 1000 0000 1000 0000 0000 0000 0000 0000 Mantissa 0000 Initial First Shift Second Shift Third Shift Fourth Shift Fifth Shift Final Log2 X e 3 00 FIGURE 3 Conversion to Base2 Logarithm by Base Shift MANTISSA LOG2 3 e LOG2 4 e 010 0000 011 0000 In Figure 2 each point evaluated in Figure 1 has been repeated using binary notation An arrow subscript indicates the highest even power of 2 appearing in each value of X Notice that in X e 3 the highest even power of 2 is 21 Thus the characteristic of the log2 3 is 1 Where X e 10 the characteristic of the log2 10 is 3 To find the log2 X is very easy where X is an even power of 2 We simply shift the value of X left until a carry bit emerges from the high order position of the register This procedure is illustrated in Figure 3 This characteristic is found by counting the number of shifts required and subtracting the result from the number of bits in the register In practice it is easier to being with the number of bits and count down once prior to each shift Counter for Characteristic CHARACTERISTIC 1 2 3 3 Easy Logarithms for COP400 COP400 Easy Logarithms for COP400 COP400 Examination of the final value obtained in Figure 3 reveals no bits in the mantissa The value 3 in the characteristic however indicates that a bit did exist in the 23 position of the original number and would have to be restored in order to reconstruct the original value (antilog) FIGURE 1 The Logarithmic Function and Some Example Values CB-2 C1995 C1995 National Semiconductor Corporation TL DD 6942 RRD-B30M105 RRD-B30M105 Printed in U S A A simple flow chart and program can be devised for generating the values found in the table and as will be apparent a straight line approximation for values that are not even powers of 2 The method as already illustrated in Figure 3 involves only shifting a binary number left until the most significant bit moves into the carry position The characteristic is formed by counting Since a carry on each successive shift will yield a decreasing power of 2 we must start the characteristic count with the number of bits in the binary value (x) and count down one each shift The log of any even power of 2 can be found in this way Decimal Binary 128 64 32 4 2 1 10000000 01000000 00100000 00000100 00000010 00000001 Log2 0111 0110 0101 0010 0001 0000 00000000 00000000 00000000 00000000 00000000 00000000 FIGURE 4 Base2 Logarithms of Even Powers of 2 TL DD 6942 ­ 2 FIGURE 5 Log Flowchart 2 TL DD 6942 ­ 5 FIGURE 6 3 To reconstruct the original value of X find the antilog requires only restoration of the most significant bit and then its alignment with the power of 2 position indicated by the characteristic In the example approximation (log2 25 e 0100 1001) restoration of MSB can be accomplished by shifting the mantissa (only) one position to the right In the process a one is shifted into the MSB position Approximation of Log2 X Restoration of MSB Char Mantissa Char Mantissa 0100 10010000 0100 11001000 The value of the characteristic is 4 so the mantissa must be shifted to the right until MSB is aligned with the 24 position 27 26 25 24 23 22 21 20 The completion of this operation restores the value of X (X e 25) and is the procedure used to find an antilog Figure 8 is a flow chart for finding an antilog using this procedure Ths implementation in source code is shown in Figure 9 The program shown develops the log2 of any even power of 2 by shifting and testing as previously described Examine what happens to a value of X that is not an even power of 2 In Figure 7 the number 25 is converted to a base 2 log 2510 e 0 0 0 1 1 0 0 22 Shift left until carry e 1 Characteristic Carry Mantissa Log2 0100 1 10010000 0100 10010000 Figure 7 Straight Line Approximation of Base2 Log The resulting number when viewed as an integer characteristic and a fractional mantissa is 4 562510 The fraction 0 5625 is a straight line approximation of the logarithmic curve between the correct values for the base2 logs of 24 and 25 The accuracy of this approximation is sufficient for many applications The error can be corrected as will be seen later in this discussion but for now let's look at the problem of exponents or the conversion to an antilog TL DD 6942 ­ 3 FIGURE 8 Flow Chart for Conversion to Antilog 4 TL DD 6942 ­ 6 FIGURE 9 Using the linear approximation technique just described some error will result when converting any value of X that is not an even power of 2 Value of X 5 0 12 0 12 0 12 3 2c3e 6 4 c 3 e 12 8 c 3 e 24 Figure 10 contains a table of correct base 2 logarithms for values of X from 1 through 32 along with the error incurred for each when using linear approximation Notice that no error results for values of X that are even powers of 2 Also notice that the error incurred for multiples of even powers of 2 of any given value of X is always the same Error 5 2 c 5 e 10 4 c 5 e 20 0 15 0 15 0 15 0 15 X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 Hexadecimal Log Base 0 00 1 00 1 95 2 00 2 52 2 95 2 CE 3 00 3 2B 3 52 3 75 3 95 3 B3 3 CE 3 E8 4 00 4 16 4 2B 4 3F 4 52 4 67 4 75 4 87 4 95 4 A4 4 B3 4 C1 4 CE 4 DB 4 E8 4 F4 5 00 Linear Approximation of Log Base 2 Error Hexadecimal 0 00 1 00 1 80 2 00 2 40 2 80 2 C0 3 00 3 20 3 40 3 60 3 80 3 A0 3 C0 3 E0 4 00 4 10 4 20 4 30 4 40 4 50 4 60 4 70 4 80 4 90 4 IA0 4 B0 4 C0 4 D0 4 E0 4 F0 5 00 5 1- EM b 1 a 0 00 0 00 0 15 0 00 0 12 0 15 0 0E 0 00 0 0B 0 12 0 15 0 15 0 13 0 0E 0 08 0 00 0 06 0 0B 0 0F 0 12 0 17 0 15 0 17 0 15 0 14 0 13 0 11 0 0E 0 0B 0 08 0 04 0 00 EM b EM b 1 2 0 03 0 09 0 0D 0 11 0 15 0 16 0 16 0 16 0 15 0 14 0 12 0 10 0 0D 0 0A 0 06 0 02 FIGURE 10 Error Incurred by Linear Approximation of Base 2 Logs An error that repeats in this way is easily corrected using a look-up table The greatest absolute error will occur for the least value of X not an even power of 2 X e 3 is about 8% A 4 point correction table will eliminate this error but will move the greatest uncompensated error to X e 9 where it will be about 4% This process continues until at 16 correction points the maximum error for the absolute value of the logarithm is less than 1 percent This can be reduced to 0 3 percent by distributing the error Interpolated error values are listed in Figure 10 and are repeated in Figure 11 as a binary table 6 High Order 4 Mantissa Bits 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Binary Correction Value 0000 0000 0000 0001 0001 0001 0001 0001 0001 0001 0001 0001 0000 0000 0000 0000 Notice in Figure 10 that left justification of the mantissa causes its high order four bits to form a binary sequence that always corresponds to the proper correction value This works to advantage when combined with the COP400 COP400 LQID instruction LQID implements a table look-up function using the contents of a memory location as the address pointer Thus we can perform the required table look-up without disturbing the mantissa Hexadecimal Correction Value 0000 1001 1101 0001 0101 0110 0110 0110 0101 0100 0010 0000 1101 1010 0110 0010 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 9 3 1 5 6 6 6 5 4 2 0 D A 6 2 Figure 12 is the flow chart for correction of a logarithm found by linear approximation Figure 13 is its implementation in COP400 COP400 assembly language Notice that there are two entry points into the program One is for correction of logs (LADJ ) the other is for correction of a value prior to its conversion to an antilog (AADJ ) FIGURE 11 Correction Table for L2 X Linear Approximations TL DD 6942 ­ 4 FIGURE 12 Flow Chart for Correction of a Value Found by Straight Line Approximation 7 TL DD 6942 ­ 7 FIGURE 13 8 Subroutines Used by the Log and Antilog Programs TL DD 6942 ­ 8 9 TL DD 6942 ­ 9 10 TL DD 6942 ­ 10 11 Easy Logarithms for COP400 COP400 LIFE SUPPORT POLICY NATIONAL'S PRODUCTS ARE NOT AUTHORIZED FOR USE AS CRITICAL COMPONENTS IN LIFE SUPPORT DEVICES OR SYSTEMS WITHOUT THE EXPRESS WRITTEN APPROVAL OF THE PRESIDENT OF NATIONAL SEMICONDUCTOR CORPORATION As used herein CB-2 1 Life support devices or systems are devices or systems which (a) are intended for surgical implant into the body or (b) support or sustain life and whose failure to perform when properly used in accordance with instructions for use provided in the labeling can be reasonably expected to result in a significant injury to the user National Semiconductor Corporation 1111 West Bardin Road Arlington TX 76017 Tel 1(800) 272-9959 Fax 1(800) 737-7018 2 A critical component is any component of a life support device or system whose failure to perform can be reasonably expected to cause the failure of the life support device or system or to affect its safety or effectiveness National Semiconductor Europe Fax (a49) 0-180-530 85 86 Email cnjwge tevm2 nsc com Deutsch Tel (a49) 0-180-530 85 85 English Tel (a49) 0-180-532 78 32 Fran ais Tel (a49) 0-180-532 93 58 Italiano Tel (a49) 0-180-534 16 80 National Semiconductor Hong Kong Ltd 13th Floor Straight Block Ocean Centre 5 Canton Rd Tsimshatsui Kowloon Hong Kong Tel (852) 2737-1600 Fax (852) 2736-9960 National Semiconductor Japan Ltd Tel 81-043-299-2309 Fax 81-043-299-2408 National does not assume any responsibility for use of any circuitry described no circuit patent licenses are implied and National reserves the right at any time without notice to change said circuitry and specifications