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.

$\endgroup$
  • 1
    $\begingroup$ See Ulf Adams's Ryu for an efficient algorithm that does this $\endgroup$ – David Fraser Jun 10 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 Jul 8 at 12:14
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.

$\endgroup$
  • $\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 Oct 10 '17 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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