c++ - 2个给定数字之间的 double 密度

Question

重要编辑:最初的问题是关于获取 double 和分数的密度。当我得到 double 而不是分数的答案时，我正在改变主题以结束这个问题。原问题的另一半是here

新问题

我想找出 2 个给定数字之间的 double 密度，但我想不出一个好方法。所以我正在寻找一个封闭形式的表达式 doublesIn(a,b)。或者一些在合理时间内完成工作的代码。

对于 double ，我应该使用一些我不知道的尾数和指数的公式。我已经有一个使用 nextafter 的代码，它在 [-1,1] 附近非常慢(低于 1e6 非常慢)

.

有什么想法吗？提前致谢! :)

PS:如果你想知道，我正在为自己编写一些数学东西，我想知道在某些算法(如高斯消元法，牛顿求根法等)，为此我想采取一些措施。

Answer 1

在接下来的内容中，包括程序在内，我假设 double 由 IEEE 754 64 位二进制 float 表示。这是最有可能的情况，但 C++ 标准不保证。

您可以在常数时间内计算一个范围内的 double 值，因为您可以在常数时间内计算一个范围内的无符号整数，方法是从末尾减去起点并调整范围是开还是闭。

有限非负范围内的 double 具有形成连续整数序列的位模式。例如，范围 [1.0,2.0] 包含范围 [0x3ff0_0000_0000_0000, 0x4000_0000_0000_0000] 中每个整数的 double 值。

double 的有限非正范围的行为方式相同，除了无符号位模式的值随着 double 变得更负而增加。

如果您的范围既包括正数也包括负数，将其拆分为零，以便处理一个非负范围和另一个非正范围。

当您想要准确计数时，大多数复杂情况都会出现。在这种情况下，您需要调整范围是打开还是关闭，并恰好将零计数一次。

就您的目的而言，相差几亿分之一或二分之一可能无关紧要。

这是一个演示这个想法的简单程序。它几乎没有接受过错误检查，因此使用风险自负。

#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);
}