I'm working on a harmonic ratio program and part of what I want a user to be able to do is plug in various ratios and have the decimal-valued frequency that's playing show you more ratio-locked frequencies that are higher or lower.
Anyway, on this webpage there is a javascript algorithm to show fractional values (ratios) from given decimals.
http://www.mindspring.com/~alanh/fracs.html
How does it work? I am interested in implementing it myself, but I don't really understand how it functions. If you try out some fractions, it gives you many options (some with extra decimals) so it's not exactly just GCD.
edit: if this algorithm question would be better suited for programmers.se just let me know and I'll repost there and delete this.
It is calculating the continued fraction and displaying that. Each term in the continued fraction gives you another fraction that is an order of magnitude better.
See Algorithm for simplifying decimal to fractions for more detailed explanations and alternative algorithms that you could choose to use.
You can exploit IEEE 754 as your decimal value is most likely stored in it and it use integral binary representation where mantissa is integer and exponent can be converted to integer division too so you can extract a/b form from it directly. For 32 bit float we got:
1 bit sign
8 bit exponent (with bias 127)
23+1 bit mantissa (the highest bit is not present in binary but it is 1).
Now for example take float 3.14159265358979. If I read this float content as integer type then it is stored as:
0x40490FDB hex
0100 0000 0100 1001 0000 1111 1101 1011 bin
0 10000000 10010010000111111011011 bin
s exponent mantissa
so:
3.14159265358979 = +1.10010010000111111011011b*2^(10000000b-01111111b)
3.14159265358979 = +110010010000111111011011b/2^(23-(10000000b-01111111b))
3.14159265358979 = +110010010000111111011011b/2^(23-(10000000b-01111111b))
3.14159265358979 = +110010010000111111011011b/2^22
3.14159265358979 = +110010010000111111011011b/2^22
3.14159265358979 = 13176795 / 4194304 = 3.1415927410125732421875
If I define it as "algebraic" equation I got:
float = (sign) (mantissa+2^23) / 2^(23-(exp-127))
Now you can apply GCD or what ever you want ... Here simple C++ code for this:
void fraction(int &a,int &b,float c) // a/b ~= c
{
union // convert between float and integer representation
{
float f32;
unsigned int u32;
} x;
x.f32=c;
int s,e;
s =x.u32&0x80000000; // sign bit
a =x.u32&0x007FFFFF; // mantisa
a|= 0x00800000; // add MSB in mantisa (not present in float representation)
e =(x.u32>>23)&0xFF; // exponent
e-= 0x7F; // exponent bias to make exponent signed again
// (optional) divide by 2 while you can (too lazy for GCD as b will be always power of 2 ...) it is better to do it on e instead of b to avoid possible overflows
while ((a>=2)&&((a&1)==0)) { a>>=1; e++; }
b=1<<(23-e); // b= 2^(23-exp)
if (s) a=-a; // sign
}
As we got binary exponent the b will always be a power of 2. That means that instead of GCD is enough to divide a by 2 while we can and either increase exponent e or divide b first and only after apply GCD on usually much smaller numbers. Better to apply this on e to avoid overflows as final exponent is e=<-104,151> and the resulting b is just integer so it has much much less bits as it needs. In such case b does not fit into integer do the opposite (multiply a by 2 and decrement e or multiply b by 2 until it fits and or cut some low bits of mantissa ...)
Here examples from the page you linked:
a b a / b c
13176795 / 4194304 = 3.141593 ~= 3.141593
11863283 / 8388608 = 1.414214 ~= 1.414214
13573053 / 8388608 = 1.618034 ~= 1.618034
46751 / 128 = 365.242188 ~= 365.242188
Unless you are computing this on strings or arbitrary precision than you can not get any better than this due to floating rounding problems. So just chose floating precision you want (32bit float, 64bit double, 80bit extended,...) extract mantissa,exponent and convert to a/b
Hope it is clear enough now. In case you want to know how we can get the IEEE 754 form from (string/value) it boils down to conversion to binary. We need just the fractional part and that is done by successive multiplication by target base (2) in source base (10 or 2^8,2^16,2^32,...). So in each iteration multiply the value, the integer part of result is new digit and use fractional part for next iteration ... repeat until the value is non zero or max number of digits was used.
0.123 0b
0.246 -> 0.0b
0.492 -> 0.00b
0.984 -> 0.000b
1.968 -> 0.0001b
1.936 -> 0.00011b
1.872 -> 0.000111b
1.744 -> 0.0001111b
1.488 -> 0.00011111b
0.976 -> 0.000111110b
