Reputation: 1557

C How to calculate a percentage(perthousands) without floating point precision

How do you calculate a percentage from 2 int values into a int value that represents a percentage(perthousands for more accuracy)?

Background/purpose: using a processor that doesn't have a FPU, floating point computations take 100's of times longer.

int x = 25;
int y = 75;
int resultPercentage; // desire is 250 which would mean 25.0 percent

resultPercentage = (x/(x+y))*1000; // used 1000 instead of 100 for accuracy
printf("Result= ");
printf(resultPercentage);

output:

Result= 0

When really what I need is 250. and I can't use ANY Floating point computation.

Example of normal fpu computation:

int x = 25;
int y = 75;
int resultPercentage; // desire is 250 which would mean 25.0 percent

resultPercentage = (int)( ( ((double)x)/(double(x+y)) ) *1000); //Uses FPU slow

printf("Result= ");
printf(resultPercentage);

output:

Result= 250

But the output came at the cost of using floating point computations.

Upvotes: 7

Answers (7)

chux

Reputation: 153517

resultPercentage = (x/(x+y))*1000; does not work as (x/(x+y)) is likely 0 or 1 before the multiplication *1000 occurs. Instead:

For a rounded unsigned integer calculation of x/(x+y), let a = x and b = x+y then to find a/b use:

result = (a + b/2)/b;

For a rounded unsigned integer percent % calculation of a/b use

result = (100*a + b/2)/b;

For a rounded unsigned integer permil ‰ calculation of a/b use

result = (1000*a + b/2)/b;

For a rounded unsigned integer permyriad ‱ calculation of a/b use

result = (10000*a + b/2)/b;

Concerns about eating up the integer range: use wider integer math (unsigned long long) for the multiplication and maybe x+y.

result = (100ULL*a + b/2)/b;

For signed a, b, it is more complicated as b/2 needs to match the sign of a/b.

if (b > 0) {
  if (a >= 0) { 
    result = (a + b/2)/b;
  } else {
    result = (a - b/2)/b;
  }
} else {
  if (a >= 0) { 
    result = (a - b/2)/b;
  } else {
    result = (a + b/2)/b;
  }
}

Possible to code a one liner:

result = (a + (((a < 0)==(b < 0)) ? b/2 : b/-2))/b;

b/-2 better than -b/2 to prevent UB with b == INT_MIN. Or use -(b/2).

Of course, replace

// printf(resultPercentage);
printf("%d\n", resultPercentage);
// or for unsigned
printf("%u\n", resultPercentage);

Upvotes: 12

Floris

Reputation: 46385

A solution using long division

And now for the pencil-and-paper answer… Not sure if this will be faster than your processor's built in floating point arithmetic, but it's a fun thing to look at (and maybe improve upon). This is an implementation of long division (remember that?) - in principle it is "infinitely precise", a bit like BigDecimal math - in practice it is limited because a finite amount of space is allocated for the string (you could change that with a malloc/free). If you have trouble with (code) space on your processor (as well as the lack of a dedicated floating point unit) then this is definitely not the way to go; also I am assuming that all division (even integer) would be slow, and using only multiplication, addition and subtraction.

Final bonus - the result comes out as a string, saving the need for a separate printf style conversion later. There are many ways conceivable for speeding this up; for now it's just fun to see how you can solve this problem with only limited precision integers, yet get a "very good" answer. Incidentally, according to my pedestrian timing code, the result is faster than a divide-and-sprintf routine (which was pretty gratifying). Almost certainly due to the fact that the conversion to a string of digits is happening "almost for free" (if you think about how that is normally done, it takes lots of division/modulo math…).

EDIT in its current form, this code even takes account of rounding (computing one additional digit, and then making the necessary adjustments). One caveat: it only works for positive integers.

Play with it and tell me if you like it!

#include <stdio.h>
#include <time.h>

void doRound(char *s, int n) {
  // round the number string in s
  // from the nth digit backwards.
  // first digit = #0
  int ii;
  int N = n;
  if(s[n] - '0' < 5) {
    s[N] = '\0';
    return; // remove last digit
  }
  while (n-- > 0) {
    if(s[n] == '.') {
      n--;
    }
    if(s[n] - '0' < 9) {
      s[n]++;
      s[N] = '\0';
      return;
    }
    s[n] = '0';
  }
  if (n == -1) {
    for (ii = N-1; ii >=0; ii--) {
     s[ii+1] = s[ii];
    }
    s[0] = '1';
  }
  else s[N] = '\0';
}

void longDivision(unsigned int a, unsigned int b, char* r, int n) {
// implement b / a using only integer add/subtract/multiply
  char temp[20];  // temporary location for result without decimal point
  char c = '0';   // current character (digit) of result
  int ci = 0;     // character index - location in temp where we write c
  int t = n + 1;  // precision - no more than n digits
  int dMult = 0;  // scale factor (log10) to be applied at the end
  int di = 0;

  // first get numbers to correct relative scaling:
  while( a > b) {
    dMult++;
    b *=10;
  }
  while (10 * a < b) {
    dMult --;
    a*=10;
  }

  // now a >= b: find first digit with addition and subtraction only
  while( b > a ) {
    c++;
    b -= a;
  }
  t--;
  temp[ci++] = c; // copy first digit
  c = '0';

  // now keep going; stop when we hit required number of digits
  while( b > 0 && t > 0) {
    b *= 10;
    t--;
    while( b > a ) {
      c++;
      b -= a;
    }
    temp[ ci++ ] = c;
    c = '0';
  }

  // copy the result to the output string:
  temp[ ci ] = '\0'; // terminate temp string
  if (dMult > 0) {
    r[ di++ ] = '0';
    r[ di++ ] = '.';
    while( --dMult > 0 ) {
      r[ di++ ] = '0';
    }
    ci = 0;
    while( temp[ ci ] != '\0' ) {
     r[ di++ ] = temp[ ci++ ];
    }
  }
  else {
    ci = 0;
    while( temp[ ci ] != '\0') {
      r[ di++ ] = temp[ ci++ ];
      if( dMult++ == 0 ) r[ di++ ] = '.';
    }
  }
  r[ di ] = '\0';

  // finally, do rounding:
  doRound(r, n+1);

}


int main(void) {
  int a, b;
  time_t startT, endT;
  char result[20];
  int ii;

  a = 123; b = 700;
  longDivision(a, b, result, 5);
  printf("the result of %d / %d is %s\n", b, a, result);

  printf("the actual result with floating point is %.5f\n", (float) b / (float) a );

  a = 7; b = 7000;
  longDivision(a, b, result, 5);
  printf("the result of %d / %d is %s\n", b, a, result);

  a = 3000; b = 29999999;
  longDivision(a, b, result, 5);
  printf("the result of %d / %d is %s\n", b, a, result);

  startT = clock();
  for(ii = 1; ii < 100000; ii++) longDivision(a, ii, result, 5);
  endT = clock();
  printf("time taken: %.2f ms\n", (endT - startT) * 1000.0 / CLOCKS_PER_SEC);
  // and using floating point:
  startT = clock();
  for(ii = 1; ii < 100000; ii++) sprintf(result, "%.4f", (float) ii / (float) a);
  endT = clock();
  printf("with floating point, time taken: %.2f ms\n", (endT - startT) * 1000.0 / CLOCKS_PER_SEC);
  return 0;
}

The result (without optimization turned on):

the result of 700 / 123 is 5.6911
the actual result with floating point is 5.69106
the result of 7000 / 7 is 1000.00
the result of 29999999 / 3000 is 10000.0
time taken: 16.95 ms
with floating point, time taken: 35.97 ms

Upvotes: 2

0xAB1E

Reputation: 801

If your requirement is just to find a value which gives the relation between two numbers then instead of using 1000 you may use 1024

The multiplication with 1000 will take several cycles but instead you may use

resultRelation = (x<<10)/(x+y);

It will take only 10 cycle for multiplication. Even the result will not have very large variation with 1000. After you find the percentage you may be doing some thresholding with the percentage you got, just change the comparing values.

Suppose you are using

if(resultPercentage > 500) do something

instead of that use

if(resultRelation > 512) do something

This way you can find the corresponding mapped values and replace it with them. If you are very strict on both cycles and accuracy then go for a saved lookup table which converts 0-1024 into 0-1000 but it uses a lot of RAM

Upvotes: 1

user529758

Reputation:

You could just write

(x * 1000 + 5) / (10 * (x + y))

if you care about correct rounding, and

(x * 100) / (x + y)

if you don't.

You are talking about "percentages", but I noticed that you are multiplying by 1000, which results in perthousands. If that's what you meant, then of course you'll need to change the multiplication factors to 10000 and 1000, respectively.

Furthermore, using integers significantly reduces the valid range of values to perform the computation on. This can be a bit widened if you force the intermediate results to be of a longer type, notably (signed or unsigned) long long:

(x * 1000ll + 5) / (10ll * (x + y))

should do the trick (due to integer promotion).

Upvotes: 3

T McKeown

Reputation: 12857

try this:

int x = 25;
int y = 75;
int resultPercentage; // desire is 250 which would mean 25.0 percent

resultPercentage = (x*1000)/(x+y);

printf("Result= ");
printf(resultPercentage);

Upvotes: 1