EDN -- 11.23.95 fractions eliminate floating-point multiply

Design Ideas: November 23, 1995

Fractions eliminate floating-point multiply

Michael Gauland,
Tektronix Inc.
Beaverton, OR

Inexpensive µCs offer better than average performance for many applications. The devices do not include hardware to do floating-point math, however. You often need to multiply or divide an integer by a floating-point constant, such as pi, square root of 2, or such circuit-specific values as the gain of an amplifier. You are interested only in the integer portion of the result. Using a floating-point representation for the constant would entail linking in -- or, worse -- writing, large, slow library functions. Fortunately, you can achieve excellent accuracy by using the ratio of two integers to approximate the constant.

For example, 355/113 approximates pi to within (8.5E-6)%. Therefore, you can replace the statement a=b*3.1415926539 with a=(b*355)/113. You've thus substituted an integer multiply and divide for a floating-point multiply. In doing so, you generally get a substantial improvement in execution speed. The function in Listing 1 determines the best integers to use for a given word size. Table 1 gives you approximations for several mathematical constants.

Value	8-bit signed	8-bit unsigned	16-bit unsigned	16-bit unsigned
TABLE 1 -- MULTIPLY/DIVIDE INTEGERS FOR MATH CONSTANTS
pi[3.1415...]	22/7 [.04%]	245/78 [.02%]	355/113 [8.5E-6%]	65,298/20,785 [5.1E-6%]
sqrt(2) [1.414...]	99/70 [.005%]	239/169 [8.7E-4%]	19,601/13,860 [1.3-7%]	47,321/33,461 [2.2E-8%]
sqrt(3) [1.732...]	97/56 [.005%]	168/97 [.005%]	32,592/18,817 [1.4E-7%]	51,409/29,681 [3.8E-8%]
e [2.71828...]	106/39 [.01%]	193/71 [.001%]	25,946/9,545 [2.0E-7%]	49,171/18,089 [1.0E-8%]
cos(pi/6) [.866....]	84/97 [.005%]	181/209 [3.8E-4%]	18,817/21,728 [1.4E-7%]	35,113/40,545 [1.0E-8%]

Value	8-bit signed	8-bit unsigned	16-bit signed	16-bit unsigned
TABLE 2 -- MULTIPLY/DIVIDE INTEGERS FOR MATH CONSTANTS OF BINARY DENOMINATORS
pi[3.1415...]	101/32 [.5%]	201/64 [.03%]	3,217/1,024 [2.8E-4%]	3,217/1,024 [2.8E-4%]
sqrt(2) [1.414...]	91/64 [.5%]	181/128 [.01%]	11,585/8,192 [.002%]	46,341/32,768 [1.1E-4%]
sqrt(3) [1.732...]	111/64 [.13%]	111/64 [.13%]	14,189/8,192 [2.8E-4%]	14,189/8,192 [2.8E-4%]
e [2.71828...]	87/32 [.02%]	87/32 [.02%]	5,567/2,048 [7.4E-4%]	5,567/2,048 [7.4E-4%]
cos(pi/6) [.866....]	55/64 [.8%]	111/128 [.13%]	14,189/16,384 [2.8E-4%]	14,189/16,384 [2.8E-4%]

LISTING 1—OPTIMUM INTEGERS VS WORD SIZE

void div_approx(#double val, long int maxNumerator, long int
*maxX, long int*maxY) {
   long int x, y;
   double e, maxE;
   unsigned long int stop;

if (val>1)stop=maxNumerator/val+.5; else stop=maxNumerator ;
   maxE = 10;
   for (x=1; x<stop; x++){
      y = x*val+.5;
      e = fabs((float)y/x-val);
      if (e < maxE) {
         maxE = e;
         *maxX = x;
         *maxY = y;
         };
      };
}

You can realize even greater efficiency by making the denominator a power of 2 and substituting right shifts for the divide. Listing 2 gives a function to calculate ratios of this type. Table 2 shows the approximations for the constants in Table 1. (DI #1774)

LISTING 2—OPTIMUM INTEGERS FOR 2^N DENOMINATORS

void shift_approx(#double val, long int maxNumerator, int
*maxShifts, long int*maxY) {
   int shifts;
   long int x, y;
   double e, maxE;
   unsigned long int stop;

if (val>1)stop=maxNumerator/val+.5; else stop=maxNumerator ;
   maxE = 10; shifts = 0;
   for (x=1; x<stop; x<<=1){
      y = x*val+.5;
      e = fabs((float)y/x-val);
      if (e < maxE) {
         maxE = e;
         *maxShifts = shifts;
         *maxY = y;
         };
      shifts++;
      };
}