1
$\begingroup$

Suppose we are given two real numbers: $a, b \in \mathbb{R}$, $b > a$. Find $m \in \{1, 2, 2.5, 5\}$ and $k \in \mathbb{Z}$, satisfying the following condition: $\frac{b-a}{m10^k} \in [5,10)$.

How to solve this problem without using brute force?

  • 0
    Could you explain briefly where this problem comes from? Also, are there any conditions on $b-a$? Lastly, by $[5;10]$ do you mean $[5,10]$? (the closed interval from 5 to 10)2010-11-10

1 Answers 1

2

This is a "normalization" type operation. For simplicity we can replace the two parameters a,b with the single one c = b - a > 0.

Assuming the interpretation proposed by Eric above, you want c*(10^-k) to fall into an interval m*[5,10) where m is in {1,2,2.5,5}. In other words we want to normalize c by a power of 10 so that it belongs to (at least) one of these intervals:

[5,10), [10,20), [12.5,25), [25,50)

While the middle pair of these intervals has nonempty overlap, the union of all four intervals is [5,50) and covers exactly one order of magnitude (power of 10). It follows that the exponent k is unique, although the factor m may or may not be unique. Note that this is equivalent to pigeonholing c/5 into one of four subintervals covering [1,10).

How to find these "without using brute force" ? The best programmatic approach depends on what language and hardware is available. The IEEE standard for floating-point arithmetic (IEEE-754) allows some fairly portable assumptions to be made, but the challenge is to get a "leading digit" and characteristic exponent in base 10 when the usual representation of floating-point numbers is base 2.

If we take the "common logarithm" log_10(c/5) and break it into an integer part and a fractional part:

log_10(c/5) = iPart + fPart where fPart in [0,1)

Now iPart here is the same value we want for k in your original notation for the problem, and we can determine m from fPart by doing a bit of testing:

if ( fPart < log_10(2) ) then m = 1
else if ( fPart < log_10(2.5) ) then m = 2
else if ( fPart < log_10(5) ) then m = 2.5
else m = 5

regards, hm