Let's say we have 0.33, we need to output "1/3".
If we have "0.4", we need to output "2/5".
The idea is to make it human-readable to make the user understand "x parts out of y" as a better way of understanding data.
I know that percentages is a good substitute but I was wondering if there was a simple way to do this?
You might want to read What Every Computer Scientist Should Know about Floating Point Arithmetic.
You'll have to specify some precision by multiplying by a large number:
3.141592 * 1000000 = 3141592
then you can make a fraction:
3 + (141592 / 1000000)
and reduce via GCD...
3 + (17699 / 125000)
but there is no way to get the intended fraction out. You might want to always use fractions throughout your code instead --just remember to reduce fractions when you can to avoid overflow!
Here's a link explaining the math behind converting a decimal to a fraction:
http://www.webmath.com/dec2fract.html
And here's an example function for how to actually do it using VB (from www.freevbcode.com/ShowCode.asp?ID=582):
Public Function Dec2Frac(ByVal f As Double) As String
Dim df As Double
Dim lUpperPart As Long
Dim lLowerPart As Long
lUpperPart = 1
lLowerPart = 1
df = lUpperPart / lLowerPart
While (df <> f)
If (df < f) Then
lUpperPart = lUpperPart + 1
Else
lLowerPart = lLowerPart + 1
lUpperPart = f * lLowerPart
End If
df = lUpperPart / lLowerPart
Wend
Dec2Frac = CStr(lUpperPart) & "/" & CStr(lLowerPart)
End Function
(From google searches: convert decimal to fraction, convert decimal to fraction code)
You are going to have two basic problems that will make this hard:
1) Floating point isn't an exact representation which means that if you have a fraction of "x/y" which results in a value of "z", your fraction algorithm may return a result other than "x/y".
2) There are infinity many more irrational numbers than rational. A rational number is one that can be represented as a fraction. Irrational being ones that can not.
However, in a cheap sort of way, since floating point has limit accuracy, then you can always represent it as some form of faction. (I think...)
Part of the problem is that so many fractions aren't actually easily construed as fractions. E.g. 0.33 isn't 1/3, it's 33/100. But if you remember your elementary school training, then there is a process of converting decimal values into fractions, however it's unlikely to give you what you want since most of the time decimal numbers aren't stored at 0.33, but 0.329999999999998 or some such.
Do yourself a favor and don't bother with this, but if you need to then you can do the following:
Multiply the original value by 10 until you remove the fractional part. Keep that number, and use it as the divisor. Then do a series of simplifications by looking for common denominators.
So 0.4 would be 4/10. You would then look for common divisors starting with low values, probably prime numbers. Starting with 2, you would see if 2 divides both the numerator and denominator evenly by checking if the floor of division is the same as the division itself.
floor(5/2) = 2
5/2 = 2.5
So 5 does not divide 2 evenly. So then you check the next number, say 3. You do this until you hit at or above the square root of the smaller number.
After you do that then you need
You'll have to figure out what level of error you're willing to accept. Not all decimal fractions will reduce to a simple fraction. I'd probably pick an easily-divisible number, like 60, and figure out how many 60ths is closest to the value, then simplify the fraction.
I have no idea of the actual algorithm, but this pointer http://edoshin.skeletonkey.com/2006/01/fraction_approx.html could be of some help.
"Let's say we have 0.33, we need to output "1/3". "
What precision do you expect the "solution" to have? 0.33 is not equal to 1/3. How do you recognize a "good" (easy to read) answer?
No matter what, a possible algorithm could be:
If you expect to find a nearest fraction in a form X/Y where Y is less then 10, then you can loop though all 9 possible Ys, for each Y compute X, and then select the most accurate one.
You can do this in any programming language using the following steps:
Example: 0.2 =0.2 x 10^1/10^1 =2/10 =1/5
So, that can be read as '1 part out of 5'
As many people have stated you really can't convert a floating point back to a fraction (unless its extremely exact like .25). Of course you could create some type of look up for a large array of fractions and use some sort of fuzzy logic to produce the result you are looking for. Again this wouldn't be exact though and you would need to define a lower bounds of how large your want the denominator to go.
.32 < x < .34 = 1/3 or something like that.
I have found David Eppstein's find rational approximation to given real number C code to be exactly what you are asking for. Its based on the theory of continued fractions and very fast and fairly compact.
I have used versions of this customized for specific numerator and denominator limits.
/*
** find rational approximation to given real number
** David Eppstein / UC Irvine / 8 Aug 1993
**
** With corrections from Arno Formella, May 2008
**
** usage: a.out r d
** r is real number to approx
** d is the maximum denominator allowed
**
** based on the theory of continued fractions
** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
** then best approximation is found by truncating this series
** (with some adjustments in the last term).
**
** Note the fraction can be recovered as the first column of the matrix
** ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
** ( 1 0 ) ( 1 0 ) ( 1 0 )
** Instead of keeping the sequence of continued fraction terms,
** we just keep the last partial product of these matrices.
*/
#include <stdio.h>
main(ac, av)
int ac;
char ** av;
{
double atof();
int atoi();
void exit();
long m[2][2];
double x, startx;
long maxden;
long ai;
/* read command line arguments */
if (ac != 3) {
fprintf(stderr, "usage: %s r d\n",av[0]); // AF: argument missing
exit(1);
}
startx = x = atof(av[1]);
maxden = atoi(av[2]);
/* initialize matrix */
m[0][0] = m[1][1] = 1;
m[0][1] = m[1][0] = 0;
/* loop finding terms until denom gets too big */
while (m[1][0] * ( ai = (long)x ) + m[1][1] <= maxden) {
long t;
t = m[0][0] * ai + m[0][1];
m[0][1] = m[0][0];
m[0][0] = t;
t = m[1][0] * ai + m[1][1];
m[1][1] = m[1][0];
m[1][0] = t;
if(x==(double)ai) break; // AF: division by zero
x = 1/(x - (double) ai);
if(x>(double)0x7FFFFFFF) break; // AF: representation failure
}
/* now remaining x is between 0 and 1/ai */
/* approx as either 0 or 1/m where m is max that will fit in maxden */
/* first try zero */
printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
startx - ((double) m[0][0] / (double) m[1][0]));
/* now try other possibility */
ai = (maxden - m[1][1]) / m[1][0];
m[0][0] = m[0][0] * ai + m[0][1];
m[1][0] = m[1][0] * ai + m[1][1];
printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
startx - ((double) m[0][0] / (double) m[1][0]));
}
If the the output is to give a human reader a fast impression of the order of the result, it makes no sense return something like "113/211", so the output should limit itself to using one-digit numbers (and maybe 1/10 and 9/10). If so, you can observe that there are only 27 different fractions.
Since the underlying math for generating the output will never change, a solution could be to simply hard-code a binary search tree, so that the function would perform at most log(27) ~= 4 3/4 comparisons. Here as haXe code:
static function toFrac( f : Float ) : String
{
// TODO: Extract the sign and whole-number part first if f > 0.0 or f < 1.0.
return
if( f < 0.47 )
if( f < 0.25 )
if( f < 0.16 )
if( f < 0.13 )
if( f < 0.11 )
"1/10";
else
"1/9";
else
if( f < 0.14 )
"1/8";
else
"1/7";
else
if( f < 0.19 )
"1/6";
else
if( f < 0.22 )
"1/5";
else
"2/9";
else
if( f < 0.38 )
if( f < 0.29 )
"1/4";
else
if( f < 0.31 )
"2/7";
else
"1/3";
else
if( f < 0.43 )
if( f < 0.40 )
"3/8";
else
"2/5";
else
if( f < 0.44 )
"3/7";
else
"4/9";
else
if( f < 0.71 )
if( f < 0.60 )
if( f < 0.56 )
"1/2";
else
if( f < 0.57 )
"5/9";
else
"4/7";
else
if( f < 0.63 )
"3/5";
else
if( f < 0.66 )
"5/8";
else
"2/3";
else
if( f < 0.80 )
if( f < 0.74 )
"5/7";
else
if(f < 0.78 )
"3/4";
else
"7/9";
else
if( f < 0.86 )
if( f < 0.83 )
"4/5";
else
"5/6";
else
if( f < 0.88 )
"6/7";
else
if( f < 0.89 )
"7/8";
else
if( f < 0.90 )
"8/9";
else
"9/10";
}
One solution is to just store all numbers as rational numbers in the first place. There are libraries for rational number arithmetic (eg GMP). If using an OO language you may be able to just use a rational number class library to replace your number class.
Finance programs, among others, would use such a solution to be able to make exact calculations and preserve precision that may be lost using a plain float.
Of course it will be a lot slower so it may not be practical for you. Depends on how much calculations you need to do, and how important the precision is for you.
a = rational(1);
b = rational(3);
c = a / b;
print (c.asFraction) ---> "1/3"
print (c.asFloat) ----> "0.333333"
The Stern-Brocot Tree induces a fairly natural way to approximate real numbers by fractions with simple denominators.
Here are Perl and Javascript versions of the VB code suggested by devinmoore:
Perl:
sub dec2frac {
my $d = shift;
my $df = 1;
my $top = 1;
my $bot = 1;
while ($df != $d) {
if ($df < $d) {
$top += 1;
}
else {
$bot += 1;
$top = int($d * $bot);
}
$df = $top / $bot;
}
return "$top/$bot";
}
And the almost identical javascript:
function dec2frac(d) {
var df = 1;
var top = 1;
var bot = 1;
while (df != d) {
if (df < d) {
top += 1;
}
else {
bot += 1;
top = parseInt(d * bot);
}
df = top / bot;
}
return top + '/' + bot;
}
this is not an "algorithm", just a python solution: http://docs.python.org/library/fractions.html
from fractions import Fraction Fraction('3.1415926535897932').limit_denominator(1000) Fraction(355, 113)
Completed the above code and converted it to as3
public static function toFrac(f:Number) : String
{
if (f>1)
{
var parte1:int;
var parte2:Number;
var resultado:String;
var loc:int = String(f).indexOf(".");
parte2 = Number(String(f).slice(loc, String(f).length));
parte1 = int(String(f).slice(0,loc));
resultado = toFrac(parte2);
parte1 *= int(resultado.slice(resultado.indexOf("/") + 1, resultado.length)) + int(resultado.slice(0, resultado.indexOf("/")));
resultado = String(parte1) + resultado.slice(resultado.indexOf("/"), resultado.length)
return resultado;
}
if( f < 0.47 )
if( f < 0.25 )
if( f < 0.16 )
if( f < 0.13 )
if( f < 0.11 )
return "1/10";
else
return "1/9";
else
if( f < 0.14 )
return "1/8";
else
return "1/7";
else
if( f < 0.19 )
return "1/6";
else
if( f < 0.22 )
return "1/5";
else
return "2/9";
else
if( f < 0.38 )
if( f < 0.29 )
return "1/4";
else
if( f < 0.31 )
return "2/7";
else
return "1/3";
else
if( f < 0.43 )
if( f < 0.40 )
return "3/8";
else
return "2/5";
else
if( f < 0.44 )
return "3/7";
else
return "4/9";
else
if( f < 0.71 )
if( f < 0.60 )
if( f < 0.56 )
return "1/2";
else
if( f < 0.57 )
return "5/9";
else
return "4/7";
else
if( f < 0.63 )
return "3/5";
else
if( f < 0.66 )
return "5/8";
else
return "2/3";
else
if( f < 0.80 )
if( f < 0.74 )
return "5/7";
else
if(f < 0.78 )
return "3/4";
else
return "7/9";
else
if( f < 0.86 )
if( f < 0.83 )
return "4/5";
else
return "5/6";
else
if( f < 0.88 )
return "6/7";
else
if( f < 0.89 )
return "7/8";
else
if( f < 0.90 )
return "8/9";
else
return "9/10";
}
From Python 2.6 on there is the fractions module.
(Quoting from the docs.)
>>> from fractions import Fraction
>>> Fraction('3.1415926535897932').limit_denominator(1000)
Fraction(355, 113)
>>> from math import pi, cos
>>> Fraction.from_float(cos(pi/3))
Fraction(4503599627370497, 9007199254740992)
>>> Fraction.from_float(cos(pi/3)).limit_denominator()
Fraction(1, 2)
You can check Chapter 5.2 of Numerical Recipes in C, which shows three algorithms for solving your problem, with even a modification to the third to make it more stable.
Here is implementation for ruby http://github.com/valodzka/frac
Math.frac(0.2, 100) # => (1/5)
Math.frac(0.33, 10) # => (1/3)
Math.frac(0.33, 100) # => (33/100)