1
$\begingroup$

Consider an interval $[x-2^n,x+2^n]$ defined by a binary float $x$ and a power of two $2^n$ typically much smaller than $x$. I would like to know whether an efficient algorithm exists to determine the shortest decimal expansion within the interval. What is the basic idea of such an algorithm? Perhaps such an algorithm has already been published?

In my own search, I have come across the work of Steele & White “How to print floating-point numbers accurately”, but it is not clear to me whether it applies in the sense that their results can be adapted to this particular case.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ See Ulf Adams's Ryu for an efficient algorithm that does this $\endgroup$
    – David Fraser
    Commented Jun 10, 2019 at 18:43
  • $\begingroup$ @DavidFraser: Thanks for the pointer. Ryu has the same goal as Steele & White's dragon. It is aimed at round-tripping and for floats or doubles, not for arbitrary $n$. So it does not provide an answer to my question. $\endgroup$
    – equaeghe
    Commented Jul 8, 2019 at 12:14

1 Answer 1

Reset to default
1
$\begingroup$

Decimal numbers with k digits to the right of the decimal point are $10^{-k}$ apart. So if you choose k large enough that $10^{-k} < 2·2^n$, then there is a decimal number with k decimals inside the interval. You can for example calculate it as $round (x·10^k) / 10^k$.

You may be lucky, and a number with fewer decimals may be inside the interval. Rounding the result to k-1 or fewer decimals may give a result in that interval.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your first paragraph is essentially my current approach, but it only gives a short expansion, not the shortest. (BTW: sign typo inside $round$ and ‘with $k$ or less digits’.) With your second paragraph, do you suggest an algorithm that successively tests cruder roundings? (Please expand your answer if that is the case.) $\endgroup$
    – equaeghe
    Commented Oct 10, 2017 at 9:02

Your Answer

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

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