Print integer coefficients of float?

Question

I have a difficult math question that breaks my brain, my board and all my pens. I am working with a file that expresses 2 values, multipicand and percentage . Both of these values ​​must be integers. These two values ​​are multiplied together to create a range. . Range is the value of the float.

My users are editing the range, and I have to calculate the new percentage and value of the animation. Not confused yet? Here is an example:

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

To complicate matters, the valid values ​​for Percentage are 0-100000. (Value 0-100%) Multiplicand is a value from 1 to 32 bits int max (presumably unsigned).

I need to allow users to enter a range, for example:

Range: .04 Apples 

And calculate the appropriate percentages and animations. 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 calculation example is simple, all that was required was a multiplier adjustment and a percentage down the scale factor of the new and old range. The problem occurs when the user changes the value to approximately 1400.00555. Suddenly, I have no clean way to adjust the two values.

I need an algorithmic approach to get the values ​​for M and P that give the highest possible value for the required range. Any suggestions?

Answer 1

To maximize the number of stored decimal points, you should use P of 1 or 0.1%. If it is an overflow M, then the increment P.

So, for your example, 1400.00555, P - 1 and M - 1400006

Your algorithm will look 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 2

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

 Multiplicand * Percentage = 100.0 

You must find another equation (constraint) to get the specific multiplicand OR Percentage value to solve this equation. Otherwise, you can choose Percentage as any number between 0-100000 and just substitute it in the first equation to get the multiplicand value. I hope I understood the question correctly :)

---

Edit: Well, then you should easily expand the range. Get range , then try decomposing it into factorization, dividing the range by percentage(2-100000) . When the division reminder is zero, you got factors. This is a quick pseudo code:

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

All you have to do is calculate your limits:

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

your maximum range is a maximum of 15 digits. double data types in most programming languages ​​can represent it. Do the calculation with doubles and just convert Multiplicand & Percentage to int at the end.

Answer 3

tell me what you have

 1) M * P = A 

then you have the second value for A, therefore, the new values ​​for M and P allow you to call M2, P2 and A2:

 2) M2 * P2 = A2 

I don’t know for sure, but this is what you seem to say to me: the attitude should remain unchanged, 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 replace that in 2)

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

so first enable P2, then M2 if I didn’t make mistakes

There must be some kind of rounding if M2 and P2 should be integers.

EDIT: I forgot about whole percentages, so say

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

so easy to solve for P2 and M2 and multiply P2 by 100000

Answer 4

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

EDIT:

There has to be a better way. Let me rephrase the problem:

You have an arbitrary floating point number. You want to represent this floating point number with two integers. Integer numbers multiplied together and then divided by 100000.0 are equal to a floating point number. The only other restriction is that one of the integers must be equal to or less than 100000.

It is clear that you cannot represent floating point exactly. In fact, you can ONLY represent numbers that are clearly expressed in 1 / 100000s, even if you have an infinite number of precision digits in the "multipicand". You can accurately represent 333.33333, with 33333333 as one number and 1 as another; you just can't get more than 3s.

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

• Multiply your float by 100000 in integer format, probably long or some BigNumber variant.
• Factor. Write down all the factors. It doesn't matter if you save them as 2 ^ 3 or 2 * 2 * 2 or what.
• Take as many factors as you can, without multiplying them by 100,000. This will be your percentage. (Do not try to do it perfectly; finding the optimal solution is NP-hard.)
• Take the remaining factors and multiply them together. This is your multiplier.

Answer 5

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

I would multiply the range by 100,000, and then choose M and P as the result factors so that they do not overflow the valid ranges.