In what follows, including the program, I am assuming double is represented by IEEE 754 64-bit binary floating point. That is the most likely case, but not guaranteed by the C++ standard.
You can count doubles in a range in constant time, because you can count unsigned integers in a range in constant time by subtracting the start from the end and adjusting for whether the range is open or closed.
The doubles in a finite non-negative range have bit patterns that form a consecutive sequence of integers. For example, the range [1.0,2.0] contains one double for each integer in the range [0x3ff0_0000_0000_0000, 0x4000_0000_0000_0000].
Finite non-positive ranges of doubles behave the same way except the unsigned bit patterns increase in value as the doubles become more negative.
If your range includes both positive and negative numbers, split it at zero, so that you deal with one non-negative range and another non-positive range.
Most of the complications arise when you want to get the count exactly right. In that case, you need to adjust for whether the range is open or closed, and to count zero exactly once.
For your purpose, being off by one or two in a few hundred million may not matter much.
Here is a simple program that demonstrates the idea. It has received little error checking, so use at your own risk.
#include <iostream>
#include <cmath>
using namespace std;
uint64_t count(double start, double end);
void testit(uint64_t expected, double start, double end) {
cout << hex << "Should be " << expected << ": " << count(start, end)
<< endl;
}
double increment(double data, int count) {
int i;
for (i = 0; i < count; i++) {
data = nextafter(data, INFINITY);
}
return data;
}
double decrement(double data, int count) {
int i;
for (i = 0; i < count; i++) {
data = nextafter(data, -INFINITY);
}
return data;
}
int main() {
testit((uint64_t) 1 << 52, 1.0, 2.0);
testit(5, 3.0, increment(3.0, 5));
testit(2, decrement(0, 1), increment(0, 1));
testit((uint64_t) 1 << 52, -2.0, -1.0);
testit(1, -0.0, increment(0, 1));
testit(10, decrement(0,10), -0.0);
return 0;
}
// Return the bit pattern representing a double as
// a 64-bit unsigned integer.
uint64_t toInteger(double data) {
return *reinterpret_cast<uint64_t *>(&data);
}
// Count the doubles in a range, assuming double
// is IEEE 754 64-bit binary.
// Counts [start,end), including start but excluding end
uint64_t count(double start, double end) {
if (!(isfinite(start) && isfinite(end) && start <= end)) {
// Insert real error handling here
cerr << "error" << endl;
return 0;
}
if (start < 0) {
if (end < 0) {
return count(fabs(end), fabs(start));
} else if (end == 0) {
return count(0, fabs(start));
} else {
return count(start, 0) + count(0, end);
}
}
if (start == -0.0) {
start = 0.0;
}
return toInteger(end) - toInteger(start);
}
