Doubling density between two given numbers

Question

Important Editing: The original question was getting the density of both doublings and fractions. Since I get the answer for the paired, not for the fractions, I am changing the subject to close this question. The other half of the original question is here

New question

I want to find the doubling density between two given numbers, but I can't think of a good way. Therefore, I am looking for expressions with the closed form doublesIn (a, b). Or some code that does the work in a reasonable amount of time.

In doubles, I have to use some formula with mantissa and exponent, which I do not know about. I already have code using nextafter and it is terribly slowly approaching [-1,1] (below 1e6 it is very slow)

.

Any ideas? Thank you in advance!:)

PS: If you want to know, I encode some mathematical data for myself, and I want to find how useful it would be to replace double with a fraction (long, long or similar) with certain algorithms (for example, removing Gauss, Newton's method for finding roots and etc.), and for this I want to take some measures.

Answer 1

In the future, including the program, I assume that double is represented by the IEEE 754 64-bit binary floating point. This is the most likely case, but is not guaranteed by the C ++ standard.

You can count doubles in a range at constant time because you can count unsigned integers in a range at constant time by subtracting the beginning from the end and adjusting whether the range is open or closed.

Doubles in a finite non-negative range have bit patterns that form a sequential 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].

End non-positive doubling ranges behave the same, except that unsigned bits increase as doubles become more negative.

If your range includes both positive and negative numbers, divide it by zero to deal with one non-negative range and another non-positive range.

Most complications arise when you want to get an accuracy score. In this case, you need to configure whether the range is open or closed, and count zero exactly once.

For your purpose, being from one or two to several hundred million may not really matter.

Here is a simple program demonstrating an idea. He received a small error check, 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); }