Fractional Counting Via Integers

Question

I receive an integer that represents a dollar amount in fractional denominations. I would like an algorithm that can add those numbers without parsing and converting them into doubles or decimals.

For example, I receive the integer 50155, which means 50 and 15.5/32 dollars. I then receive 10210 which is 10 and 21/32 dollars. So 50 15.5/32 + 10 21/32 = 61 4.5/32, thus:

50155 + 10210 = 61045

Again, I want to avoid this:

int a = 50155;
int b = a / 1000;
float c = a % 1000;
float d = b;
d += c / 320f;
// d = 50.484375

I would much prefer this:

int a = 50155;
int b = 10210;
int c = MyClass.Add(a.b); // c = 61045
...
public int Add(int a, int b)
{
    // ?????
}

Thanks in advance for the help!

Answer 1

Looks like a strange encoding to me.

Anyway, if the format is in 10-base Nxxx where N is an integer denoting whole dollars and xxx is interpreted as

(xxx / 320)

and you want to add them together, the only thing you need to handle is to do carry when xxx exceeds 320:

int a = ..., b = ...; // dollar amounts
int c = (a + b); // add together
// Calculate carry
int carry = (c % 1000) / 320; // integer division
c += carry * 1000;
c -= carry * 320;
// done

Note: this works because if a and b are encoded correctly, the fractional parts add together to 638 at most and thus there is no "overflow" to the whole dollars part.

Answer 2

Well I don't think you need to use floating point...

public static int Add(int a, int b)
{
    int firstWhole = a / 1000;
    int secondWhole = b / 1000;
    int firstFraction = a % 1000; 
    int secondFraction = b % 1000;
    int totalFraction = firstFraction + secondFraction;
    int totalWhole = firstWhole + secondWhole + (totalFraction / 320);
    return totalWhole * 1000 + (totalFraction % 320);
}

Alternatively, you might want to create a custom struct that can convert to and from your integer format, and overloads the + operator. That would allow you to write more readable code which didn't accidentally lead to other integers being treated as this slightly odd format.

EDIT: If you're forced to stick with a "single integer" format but get to adjust it somewhat you may want to consider using 512 instead of 1000. That way you can use simple mask and shift:

public static int Add(int a, int b)
{
    int firstWhole = a >> 9;
    int secondWhole = b >> 9;
    int firstFraction = a & 0x1ff
    int secondFraction = b & 0x1ff;
    int totalFraction = firstFraction + secondFraction;
    int totalWhole = firstWhole + secondWhole + (totalFraction / 320);
    return (totalWhole << 9) + (totalFraction % 320);
}

There's still the messing around with 320, but it's at least somewhat better.

Answer 3

Break the string up in the part that represents whole dollars, and the part that represents fractions of dollars. For the latter, instead of treating it as 10.5 thirty-seconds of a dollar, it's probably easier to treat it as 105 three hundred and twentieths of a dollar (i.e. multiply both by ten to the numerator is always an integer).

From there, doing math is fairly simple (if somewhat tedious to write): add the fractions. If that exceeds a whole dollar, carry a dollar (and subtract 320 from the fraction part). Then add the whole dollars. Subtraction likewise -- though in this case you need to take borrowing into account instead of carrying.

Answer 4

Hi

If you insist on working in ints you can't solve your problem without parsing -- after all your data is not integer. I call into evidence the (so far) 3 answers which all parse your ints into their components before performing arithmetic.

An alternative would be to use rational numbers with 2 (integer) components, one for the whole part, and one for the number of 320ths in the fractional part. Then implement the appropriate rational arithmetic. As ever, choose your representations of data carefully and your algorithms become much easier to implement.

I can't say that I think this alternative is particularly better on any axis of comparison but it might satisfy your urge not to parse.

Regards

Mark

Answer 5

As a point for learning, this representation is called "fixed point". There are a number of implementations that you can look at. I would strongly suggest that you do NOT use int as your top level data type, but instead create a type called Fixed that encapsulates the operations. It will keep your bug count down when you mistakenly add a plain int to a fixed point number without scaling it first, or scale a number and forget to unscale it.

Answer 6

Edit:
This answer suggests that one "stays away" from float arithmetic. Surprisingly, the OP indicated that his float-based logic (not shown for proprietary reasons) was twice as fast as the integer-modulo solution below! Comes to show that FPUs are not that bad after all...

Definitively, stay away from floats (for this particular problem). Integer arithmetic is both more efficient and doesn't introduce rounding error issues.

Something like the following should do the trick
Note: As written, assumes A and B are positive.

int AddMyOddlyEncodedDollars (int A, int B) {
  int sum;
  sum = A + B
  if (sum % 1000 < 320);
     return sum
  else
     return sum + 1000 - 320;
}

Edit: On the efficiency of the modulo operator in C
I depends very much on the compiler... Since the modulo value is known at compile time, I'd expect most modern compilers to go the "multiply [by reciprocal] and shift" approach, and this is fast.
This concern about performance (with this rather contrived format) is a calling for premature optimization, but then again, I've seen software in the financial industry mightily optimized (to put it politely), and justifiably so.

Answer 7

BEWARE: This post is wrong, wrong, wrong. I will remove it as soon as I stop feeling a fool for trying it.

Here is my go: You can trade space for time.

Construct a mapping for the first 10 bits to a tuple: count of dollars, count of piecesof32. Then use bit manipulation on your integer:

• ignore bits 11 and above, apply map.
• shift the whole number 10 times, add small change dollars from mapping above
• you now have the dollar amoung and the piecesof32 amount
• add both
  • move overflow to dollar amount

Next, to convert back to "canonical" notation, you need a reverse lookup map for your piecesof32 and "borrow" dollars to fill up the bits. Unshift the dollars 10 times and add the piecesof32.

EDIT: I should remove this, but I am too ashamed. Of course, it cannot work. I'm so stupid :(

The reason being: shifting by 10 to the right is the same as dividing by 1024 - it's not as if some of the lower bits have a dollar amount and some a piecesof32 amount. Decimal and binary notation just don't split up nicely. Thats why we use hexadecimal notation (grouping of 4 bits). Bummer.