Derive integer factors of float value?

Question

I have a difficult mathematical question that is breaking my brain, my whiteboard, and all my pens. I am working with a file that expresses 2 values, a multiplicand and a percentage. Both of those values must be integers. These two values are multiplied together to produce a range. Range is a float value.

My users edit the range, and I have to calculate a new percentage and multiplicand value. Confused yet? Here's an example:

    Multiplicand: 25000 Apples
    Percentage: 400 (This works out to .4% or .004)
    Range: 100.0 Apples (Calculated by Multiplicand * Percentage)

To complicate things, the allowable values for Percentage are 0-100000. (Meaning 0-100%) Multiplicand is a value between 1 and 32bit int max (presumably unsigned).

I need to allow for users to input a range, like so:

Range: .04 Apples

And calculate the appropriate Percentage and Multiplicand. Using the first example:

    OriginalMultiplicand: 25000 Apples
    OriginalPercentage: 400 (This works out to .4% or .004)
    OriginalRange: 100.0 Apples (Calculated by Multiplicand * Percentage)
    NewRange: .01 Apples
    NewPercentage: 40
    NewMultiplicand: 25 Apples

The example calculation is easy, all that was required was adjusting down the multiplicand and percentage down by the scale factor of the new and old range. The problem arises when the user changes the value to something like 1400.00555. Suddenly I don't have a clean way to adjust the two values.

I need an algorithmic approach to getting values for M & P that produce the closest possible value to the desired range. Any suggestions?

Answer 1

As I understand from your example, you could represent the range in 100000 different multiplicand * percentage. any choice of multiplicand will give you a satisfying value of percentage, and vice versa. So you have this equation in two variables:

Multiplicand * Percentage = 100.0

You should figure out another equation(constraint), to get a specific value of Multiplicand OR Percentage to solve this equation. Otherwise, you could choose Percentage to be any number between 0-100000 and just substitute it in the first equation to get the value of Multiplicand. I hope I understood the question correctly :)

---

Edit: OK, then you should factorize the range easily. Get the range, then try to factorize it by dividing range by percentage(2-100000). Once the reminder of division is zero you got the factors. This is a quick pseudo-code:

get range;
percentage = 2;
while(range % percentage != 0)
{
    percentage++;
}

multiplicand = range / percentage;

All what you have to do now is to calculate your limits:

max of percentage = 100000;
max of multiplicand = 4294967295;

Max of range = 4294967295 * 100000 = 429496729500000 (15-digit);

your Max range consists of 15 digit at a maximum. double data types in most programming languages can represent it. Do the calculation using doubles and just convert the Multiplicand & Percentage to int at the end.

Answer 2

say you have

1) M * P = A

then you have a second value for A, so also new values for M and P, lets call then M2, P2 and A2:

2) M2 * P2 = A2

This I dont know for sure, but that is what you seem to be saying imho: the ratio has to stay the same, then

3) M/P = M2/P2

Now we have 3 equations and 2 unknowns M2 and P2

---

One way to solve it:

3) becomes

M/P = M2/P2
=>M2 = (M/P)*P2

than substitute that in 2)

(M/P)*P2*P2 = A2
=> P2*P2 = A2 * (P/M)
=> P2 = sqrt(A2 * (P/M))

so first solve P2, then M2 if i didn't make any mistakes

There will have to be some rounding if M2 and P2 have to be integers.

EDIT: i forgot about the integer percentage, so say

P = percentage/100000 or P*100000 = percentage
P2 = percentage2/100000 or P2*100000 = percentage2

so just solve for P2 and M2, and multiply P2 with 100000

Answer 3

(I had a bad method here, but I erased it because it sucked.)

EDIT:

There's got to be a better way than that. Let's rephrase the problem:

What you have is an arbitrary floating-point number. You want to represent this floating-point number with two integers. The integers, when multiplied together and then divided by 100000.0, are equal to the floating-point number. The only other constraint is that one of the integers must be equal to or less than 100000.

It's clear that you can't actually represent floating-point numbers accurately. In fact, you can ONLY represent numbers that are expressible in 1/100000s accurately, even if you have an infinite number of digits of precision in "multiplicand". You can represent 333.33333 accurately, with 33333333 as one number and 1 as the other; you just can't get any more 3s.

Given this limitation, I think your best bet is the following:

1. Multiply your float by 100000 in an integer format, probably a long or some variant of BigNumber.
2. Factor it. Record all the factors. It doesn't matter if you store them as 2^3 or 2*2*2 or what.
3. Grab as many factors as you can without the multiplication of them all exceeding 100000. That becomes your percent. (Don't try to do this perfectly; finding the optimal solution is an NP-hard problem.)
4. Take the rest of the factors and multiply them together. That's your multiplicand.

Answer 4

To maximize the numbers of decimal points stored, you should use a P of 1, or 0.1%. If that overflows M, then increment P.

So for your example of 1400.00555, P is 1 and M is 1400006

Your algorithm would search for the lowest P such that M does not overflow. And you can do a binary search here.

public int binarySearch(int P0, int P1) {
   P = (P1 - P0)/2;
   if(P == P0) {
     if(R/(P0/100f) does not overflows 32-bit int) {
       return P0;
     } else {
       return P1;
     }
   }
   if(R/(P/100f) does not overflows 32-bit int) {
     return binarySearch(P0, P);
   } else {
     return binarSearch(P, P1);
   }
}

P = binarySearch(1, 100000);
M = round(R/(P/100f));

Answer 5

It seems you want to choose M and P such that R = (M * P) / 100000. So M * P = 100000 * R, where you have to round the right-hand side to an integer.

I'd multiply the range by 100000, and then choose M and P as factors of the result so that they don't overflow their allowed ranges.