   Converting a real number into integer nominator and denominator
  Imagine that you're given any number (only consider numbers > 0.0 for simplicity).How would you find the integer nominator and denominator that gives the closest result, that fits into N bits (for instance 32).I.e:    10477034092.58984375  =>  ------- 256Is there a know algorithm for doing this or does anyone have any ideas?Ps. This question is just out of curiosity (there's no actual problem to be solved).[Edited by - eq on September 7, 2007 8:58:00 AM]
  An interesting way of doing this is by representing the number as a continued fraction and then truncating. You can truncate when your next approximation wouldn't fit in your 32 bits, or you can stop after you find a large enough number in the continued fraction.Example:3.14159265358979323844 = 3 + 1/7.06251330593104577092 = 3 + 1/(7 + 1/15.99659440668571960053) = 3 + 1/(7 + 1/(15 + 1/1.00341723101337289383)) = 3 + 1/(7 + 1/(15 + 1/(1 + 292.63459101437060689761)))From those expressions, you can just round the last number to an integer, and reconstruct the fractions.3 + 1/7 = 22/7 = 3.142857142857142857143 + 1/(7 + 1/(15 + 1/1)) = 355/113 = 3.14159292035398230088 (the fact that the next number (292.63...) is very large means that this is a very good approximation)3 + 1/(7 + 1/(15 + 1/(1 + 293))) = 104348/33215 = 3.14159265392142104470EDIT: In your example, I get (due to limited precission) 4092+1/(1+1/(1+1/(2+1/(3+1/(1+1/(1+1/6.00000000000000007728)))))), and the next number is astronomical (1/.00000000000000007728=12939958592132505.17598343685300207039). From that you can reconstruct the fraction exactly as 1047703/256.;  The truncated continued fraction approximation is not only interesting, but it's also the best possible in the sense that among the fractions with the denominator not greater than what you get from it, it's the closest approximation of the input number.   ;Quote:Original post by eqHow would you find the integer nominator and denominator that gives the closest result, that fits into N bits (for instance 32).I think you meant, "numerator" rather than "nominator". That is:   numeratorfraction = -------------  denominator;  I have some conversion code at my Computational Geometry page.  In particular, look at the constructors for TRational that take 'float' or 'double' inputs.;  What Dave is doing is taking the individual fields of a double (sign, exponent, mantissa) and reconstructing the value as (-1)^sign * 2^(exponent-OFFSET) * 1.mantissa.Whether you use that method or the truncated continued fractions I suggested depends on whether you want Rational(1.0/3.0) to return 1/3 or 6004799503160661/18014398509481984 (which is what the double-precision value 1.0/3.0 actually represents).Also, I think Dave's code doesn't work for denormal numbers. That can be fixed, though.   ;Quote:Original post by alvaroWhat Dave is doing is taking the individual fields of a double (sign, exponent, mantissa) and reconstructing the value as (-1)^sign * 2^(exponent-OFFSET) * 1.mantissa.I do not think this is a correct description.  What my code does is take a number in the format (-1)^sign*2^(exponent-OFFSET)*1.mantissa and produces a rational number N/D, where N and D are integers of a fixed size (the size is the template parameter).  There are also functions to convert from N/D back to the sign-exponent-mantissa form, although potentially with loss of precision (N/D might have been the result of a few exact-arithmetic calculations that produces a number not exactly representable as a 'float' or 'double').Quote:Also, I think Dave's code doesn't work for denormal numbers. That can be fixed, though.It does not support denormal numbers.  I will add that to my to-do list.  Thanks.   