-1
$\begingroup$

We have two integers, $n$ and $d$. They are coprime (the only positive integer that is a divisor of both of them is $1$). They may be implemented as something that fits in a machine register, or they may be "big integers". Together, $n$ and $d$ represent the numerator and denominator of a rational number.

The goal is to convert the rational number into the corresponding floating-point number in a fixed-width binary floating-point format (for example, 32-bit binary IEEE 754 floating-point, known as float in the C programming language).

As long as using "big floats" (arbitrary-precision floating-point, for example with the MPFR C library) for implementing the algorithm is allowed, the solution is easy:

  1. convert both $n$ and $d$ to big floats with a precision that is high enough so both integers would be exactly represented
  2. divide the big float numerator with the big float denominator, yielding a big float number
  3. convert the above big float number to the required fixed-precision floating-point format

I wonder, however, what would a more from-first-principles solution look like, one that wouldn't use big floats?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ In 2., is it always possible to find an exact representation of the quotient? $\endgroup$
    – greybeard
    May 6 at 4:21
  • $\begingroup$ @greybeard No, but I'm assuming the result would be correctly rounded, as with MPFR. $\endgroup$
    – user2373145
    May 6 at 11:15
  • $\begingroup$ (Resisting the temptation to go grab Knuth's TAoCP volume 2 to look it up...) $\endgroup$
    – vonbrand
    May 6 at 18:17
  • $\begingroup$ Could the downvoter perhaps explain the perplexing downvote? $\endgroup$
    – user2373145
    May 7 at 15:47

1 Answer 1

Reset to default
2
$\begingroup$

Big floats are nothing but big ints with a scaling factor, which you can handle by yourself.

If the two numbers are given as big ints and you are only allowed integer division, multiply the numerator by a power of $2$ large enough that the quotient has at least $24$ (resp. $53$) significant bits. Then normalize the result to single (resp. double)-precision floating-point.

If the numbers are given as integers, you will need to resort to extended precision arithmetic, i.e. 64 bits over 32 or 128 over 64. Append a zero word to the numerator, divide and normalize the result.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The way I'm reading your answer, the algorithm requires performing multiple integer divisions until one of them produces a quotient with the required number of digits. Is there perhaps a way to solve this with a constant number of integer divisions? $\endgroup$
    – user2373145
    May 7 at 4:17
  • $\begingroup$ You say "multiply the numerator by a power of $2$ large enough that the quotient has at least $24$ significant bits. then normalize". But if I get more than $24$ significant bits, it's not clear to me how to proceed with getting rid of the extra bits. It also seems like a double-rounding problem, the integer division included the first rounding, getting rid of extra bits after that would be a second rounding. $\endgroup$
    – user2373145
    May 7 at 10:47
  • $\begingroup$ I can build an IEEE representation using ldexp, that's not a problem. $\endgroup$
    – user2373145
    May 7 at 10:50
  • $\begingroup$ @user2373145: good, solved then. Though I don't see the connection to "from-first-principles" anymore. $\endgroup$
    – Yves Daoust
    May 7 at 10:50
  • $\begingroup$ This answer is definitely wrong, or at least incomplete, as I supposed it will be above. It sometimes leads to incorrectly rounded results. $\endgroup$
    – user2373145
    May 7 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.