14
$\begingroup$

Can an IEEE-754 floating point number < 1 (i.e. generated with a random number generator which generates a number >= 0.0 and < 1.0) ever be multiplied by some integer (in floating point form) to get a number equal to or larger than that integer due to rounding?

i.e.

double r = random() ; // generates a floating point number in [0, 1)
double n = some_int ;
if (n * r >= n) {
    print 'Rounding Happened' ;
}

This might be equivalent to saying that does there exist an N and R such that if R is the largest number less than 1 which can be represented in IEEE-754 then N * R >= N (where * and >= are appropriate IEEE-754 operators)

This comes from this question based on this documentation and the postgresql random function

$\endgroup$
  • $\begingroup$ Can you say anything about the range of N, i.e. is it small enough to be represented exactly in IEEE-754 double-precision? $\endgroup$ – Pedro Aug 14 '12 at 20:14
  • $\begingroup$ @Pedro In this particular case, yes, it would be a small integer - i.e. 10. I assume you are saying that if N is a very large integer with a very large number of significant digits it might not be able to be represented exactly? $\endgroup$ – Cade Roux Aug 14 '12 at 20:40
  • $\begingroup$ Exactly, if $fl(N) > N$, then $fl(R\times fl(N))$ may be larger than $RN$. $\endgroup$ – Pedro Aug 14 '12 at 21:46
8
$\begingroup$

Assuming round-to-nearest and that $N > 0$, then $N * R < N$ always. (Be careful not to convert an integer that's too large.)

Let $c 2^{-q} = N$, where $c \in [1, 2)$ is the significand and $q$ is the integer exponent. Let $1 - 2^{-s} = R$ and derive the bound

$$N R = c 2^{-q}(1 - 2^{-s}) \le c 2^{-q} - 2^{-q - s},$$

with equality if and only if $c = 1$. The right-hand side is less than $N$ and, since $2^{-q - s}$ is exactly $0.5$ units in the last place of $N$, either $c = 1$ and $2^{-q} - 2^{-q - s}$ is exactly representable (since $N$ is normal and not the smallest normal), or $c > 1$, and the nearest rounding is down. In both cases, $N * R$ is less than $N$.


Upward rounding can cause a problem, not that it should ever be selected in the presence of unsuspecting users. Here's some C99 that prints "0\n1\n" on my machine.

#include <fenv.h>
#include <math.h>
#include <stdio.h>

int main(void) {
    double n = 10;
    double r = nextafter(1, 0);
    printf("%d\n", n == (n * r));
    fesetround(FE_UPWARD);
    printf("%d\n", n == (n * r));
}
$\endgroup$
  • $\begingroup$ I'm sorry, I'm a little slow these days - I'm having trouble getting the part of the inequality $$- c 2^{-q} 2^{-s} \le - 2^{-q s}$$ $\endgroup$ – Cade Roux Aug 14 '12 at 22:50
  • $\begingroup$ @Cade Apparently I can't do algebra today. I meant $2^{-q - s}$. $\endgroup$ – Tyrone Aug 14 '12 at 22:57
  • $\begingroup$ Thanks, I wasn't sure if there was another step I was missing. $\endgroup$ – Cade Roux Aug 14 '12 at 23:18

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.