Convert Rational number to p / q
by ericlin
Here is a Mathematic drill Question for 10-year-old kid:
"What is the result of ((2+3)/6+(6-2)/5) ?"
"The answer is (49/30);"
I press those digits to my calculator and the result is 1.63333333333333. But the school teacher wont accept that kind of answer. How could we get an answer
in this format: as "49/30" ?
Rational number
Rational number by definition is a number that can be represented by the form of "p/q" where p and q are non-zero integers.
The number (2/7) in Flash is 0.285714285714286. It is 0.285714 in Math world. So, the numerator p is 2 and denominator q is 7. It is a rational number.
The number (25/64) is 0.390625. The p is 25 and q is 64. It is a rational number.
Here is our project: Giving a number as 0.285714285714286, how do we convert it back to (2/7) ? Giving a number as 0.390625, how do we convert it back to (25/64) ? How do we figure out the p and q ?
There are at least 3 methods. One is absolute Math, the other two are guess by approximation.
1. By removing common factors from the fractions.
The number 0.390625. can be represented as (390625/1000000); However, this is
not what we want. We need to remove the common factors in the numerator and
denominator. In fact, our goal is to get an answer of (25/64).
How do we find the the common factors and remove it ? The brutal way is testing numbers from 2 up, If both numerator and denominator can be divided by that number, then remove it. Repeatedly doing so until the numerator is less than the number we have tested.
function RemoveFactors(a, b) {
var f = 2;
while (f<a) {
while ((a%f == 0) && (b%f == 0)) {
a /= f;
b /= f;
}
f++;
}
return (a+"/"+b);
}
//------------------------------
trace(byRemoveFactors(390625, 1000000));
//outputs: 25/64
In the example above, it need to test 2 to 25 to make (390625/1000000) to output (25/64); It is a little bit in-efficient.
Lets try another way.
get the common factor by modulo
If a common factor exists between these two numbers, then the common factor must exist in the modulo. For example, giving a number (18/42), we get the modulo 42%18=6, so a common factor must exist in (18, 6); Further division will get a modulo of 0, so the common factor of original (18/42) is 6; We can easily get the answer (3/7) by removing the common factor 6. It takes only one step instead of several loops.
For the number (390625/1000000), we do this:
1000000%390625=218750;
390625%218750=171875;
218750%171875=46875;
171875%46875=31250;
46875%31250=15625;
31250%15625=0;
So, we get the common factor 15625; The number (390625/1000000) can be easily converted to 25/64;
Here is the script to find common factor between two numbers.
function getCommonFactor(a, b) {
var cf;
while (cf=b%a) {
b=a, a=cf;
}
return a;
}
Now let's try another number. We create a number by divide 2 with 7. The number (2/7) is 0.285714 in Math world. If we ask for string representation in Flash, it display a number with 15 decimal digits, "0.285714285714286". The last digit is created by "rounding" and the rest is truncated off. So, the string representation is slightly different from the real value. The number (2/7) should not be represented by (285714285714286/1000000000000000);
My middle school teacher taught me that the number 0.285714 actually should be represented as (285714/999999). Lets try it.
999999%285714=142857;
285714%142857=0;
We can aslo use the function described above. So the common factor is 142857; Removing the common factor from (285714/999999); we get (2/7); Quick and perfect.
Here is a major pitfall.
To pick up a denominator and numerator according the base of 10 like the method above, we have two troubles .First, we need a string representation in the base of 10. Second, the representaion may be a rounded decimal of 15 digits, that is not the real value. If we dont have the real value, the method will fail.
For example: (15/17) is 0.882352941176471; This is a Flash String representation, and is a rounded value. It is not exactly (15/17), so we can not convert it back to (15/17);
We get to figure out another way. Maybe we can figure out a p/q representation that is almost "that" value but not exactly that value. So, we may accept some in-accuracy but succeed in converting the rational number back to a p/q representation.
2. By Brutal Sequential testing.
This is a brutal way. We try p from 1 up, and test q=p/num. If q is almost an integer, we stop.
For example, we get a number 0.390625. We try p from 1 and increase p until q=p/num is an integer. We get:
a=0.390625
1/2.56
2/5.12
3/7.68
.....
.....
22/56.32
23/58.88
24/61.44
25/64
When p is 25, the q is an integer 64, so we stop. We get the answer of (25/64);
Here is the code:
function getPQBrutally(num) {
var a = num-int(num);
var p = 0;
var q = a;
while (Math.abs(q-Math.round(q))>0.00001) {
p++;
q = p/a;
}
return Math.round(q*num)+"/"+Math.round(q);
}
//------------------
a = 49/30;
trace(a);
trace(getPQBrutally(a));
Obviously, to judge whether it is already an integer we could check it by "if(q-int(q)==0)" instead of "Math.abs(q-Math.round(q))>0.00001". Is that right ?
Theoretically, yes. But, in Flash computer world, it is NO. The function involves operations between floats and floats which we know is with some minute in-accuracy. The resulted integer might be in the form of 0.999995736837 instead of 1. The integer might be in the form of 1.0000057824853 instead of 1; So, the decimal part is not necessarily so beautiful as 0; So, we need to stop if it looks like an integer.
Lets check the number a=0.285714285714286, we try the p until q is almost an integer:
a=0.285714285714286;
1/3.5
2/6.99999999999999
The number 6.99999999999999 is almost an integer 7. We accept it as an integer and our answer is (2/7). Here we take "almost" instead of "exactly". One of the reasons is that, not only we can convert (2/7) back, it also accept a rounded decial number like 0.285714285714286; So, the art of "almost" is beautiful. Another reason is that, operation between float and float always result in a value with some rounding and in-accuracy. So, a script with "almost" instead of "exactly" is not a sin.
Instead of p, our function can try sequential q until p is an integer. For (49/30), if we test q, we need 30 loops. If we test p, we would have need 49 loops. However, I trim the number off and test only the decimal portion, so it need only 19 loops. (19=49%30);
You might expect some problems about "almost". If we take
accuracy too loose, then the number will be too simplified. If we take accuracy
too severe, we might miss the stop point and the function will goes infinitely.
3. By Inversion of decimal
This is a bit complex and not easy to understand. I will try to explain it step by step in possible details.
There are two things we should know first.
Rule 1: the inversion.
Invert a number: num --> 1/num , the effect is p/q -->q/p;
For a number num as p/q, p is numerator and q is denominator. When we invert num by 1/num , the representing format is q/p, the numerator is now denominator, and the denominator is now the numerator.
For example, the number num=0.4 is represented as (2/5); The inverted number (1/num) is 2.5, a number represented as (5/2);
A number num=0.35 is represented as (7/2), The inverted number (1/num) should be represented as (2/7);
For a number with numerator=1, the inversion will be an integer; For example, inversion of (1/7) will be 7;
2. Rule 2: the decimal part and modulo
For a number greater than 1, if we trim off the integer part, the decimal part is represented as modulo after division.
By script, the effect of num-int(num), to the fraction part is (p%q)/q;
For example, a number 1.4 is represented as (7/5); We trim off the integer part to get a decimal part of 0.4. That is (2/5); The numerator part is just (7%5), while the denominator remain the same;
Please note this: Trim the integer part will not affect the denominator q; The denominator for the number and the decimal are the same.In the example above, before trimming, it is (7/5), after trimming, the decimal part is (2/5); The denominators for both of them are 5;
If the number after trimming is 0, then it is an integer. It means the modulo is 0;
OK, with these two rules, lets begin our project - to get the denominator of by
inversion of decimal.
Do you believe inversion a decimal may give us the denominator ? Think about the number num=0.5. If we invert it (1/num), we get 2. That is the denominator, so
0,5 can be represented by (1/2). Again, for the number num=0.125. If we invert the number, we get
the denominator 8, so 0.125 can be represented as (1/8).
For a number num=1.5, we need only the decimal part to get the denominator through inversion. Trim 1.5, we get the decimal part as 0.5. We invert it and get the result 2 . So the denominator is 2, the number 1.5
can be represented with 2 as denominator, (3/2);
However, inversion of decimal number will not always result in an integer. For example, the decimal number 0.4, when we invert it, we get
2.5, not an integer; It is because the numerator p is 2, so we need to modify our result by
the numerator, 2.5 * 2=5. At last, we get the correct denominator q as 5. This is understandable by the equation num=p/q, so q=p*(1/num); From this equation we also understand why we dont need correction if p is 1.
Since , we need the numerator p to modify our q to get correct denominator , how do we calculate out the p ?
Rember that ? If num=p/q, then (1/num)=q/p. If we get the denominator from the inverted number, we get the p. Easy, right ?
(Do you smell something similar to the function
getCommonFactor between two numbers ? That script is also written with module
and invert.)
Here is our function:
function getDenominator(num) {
var decimal = num-int(num);
if (Math.abs(decimal)<0.00001) {
// treat too small decima as 0
return 1;
}
num = 1/decimal;
// invert the decimal
return num*getDenominator(num);
//a recursive call
}
//----------------------
a = 43697/405293;
trace(a);
q = getDenominator(a);
trace(Math.round(q*a)+"/"+Math.round(q));
a = 49/30;
trace(a);
q = getDenominator(a);
trace(Math.round(q*a)+"/"+Math.round(q));
You can see that, getDenominator is a recursive function, because we might not get p in one step. To avoid a recursion over the limit of 256 stacks, we can easily change the code to a while-loop. I am not going to discuss that. Anyway, it is not difficult.
To get p/q by the function getDenominator is very fast. It involes modulo for p and q. The tested p and q drop quickly by trim-modulo
processes. To convert 49/30, it need 8 loops. To convert 43697/405293, it needs
13 loops.
The biggest pitfall is that, each steps involves float-float calculation with in-accuracy. The in-accuracy might accumulate to a significant amount, so that we can never get a beautiful form of "integer".
If we miss the catch, the computer might hang up. In such condition we need to accept it as an integer if decimal is <0.00001;
Which method is the best ?
The first one involves only integer operation and is always correct. But, this method starts with two numbers in the base of 10 is impratical. We have little chance to "see" the decimal value by "human eye". We can only apply this method to our home work when our teacher gives us a decimal number in the base of 10. It only answers questions like "What is the representation of 0.390625 ? What is the representation of 0.285714". Most of the time, our number could not be represented exactly by two 10 based decimal without rounding.
Practically, we use the other two methods to solve the representating p/q. We calculate out the acceptable p/q representation, although not necessarily "exact" accurate.
The second one, solution by Brutal way, involves minor float calculation. We need to pick out the stop point, when we "meet" an integer. There is only one step involving interger-float calculation, so the in-accuracy is more limited and stop point is easier to guess.
The third one, solution by inverting decimals, is very fast. However, there involves several major float-float calculation. The in-accuracy could accumulate to a significant amout. It is more difficult to know when we "meet" integer. If we miss the stop point, the computer might hang there to an infinite loop.
The scripts are just for demo, not for practical use. It might crash and hang up your computer if you test them with un-reasonable numbers. If you want to use those functions, you get to add "guard" codes to make it robot. Otherwise, you can freely to modify and use those script as you wish.
Be careful ! If you want to test those functions, please test it with a limited denominator. If you try to test it by 1/345735, then you get a sorry result. The number is 2.89238867919071e-6. It is treated as 0 and wont be converted to p/q;