2个给定数字之间的双倍密度 [英] Density of doubles between 2 given numbers

问题描述

重要编辑：最初的问题是关于获取双精度和分数的密度。当我得到双打而不是分数的答案时，我正在更改主题以关闭该问题。原始问题的另一半是此处

新问题

我想找到两个给定数字之间的倍数密度，但我想不起来一个好方法。因此，我正在寻找封闭形式的表达式doublesIn（a，b）。或一些在合理的时间内能正常工作的代码。

对于双精度值，我应该使用一些我不知道的尾数和指数公式。我已经有一个使用 nextafter 的代码，它的速度非常接近[-1,1]（低于1e6的速度非常慢）

。 / p>

有什么想法吗？提前致谢！ ：）

PS：如果您想知道，我正在为自己编写一些数学知识，并且我想找到用小数代替double的有用性（ long，long或类似的算法）（例如高斯消去法，牛顿求根法等）上的某些算法，为此，我想采取一些措施。

解决方案

接下来，包括程序在内，我假设 double 由IEEE 754 64位二进制浮点表示。

您可以在恒定时间内计算范围内的双精度数，因为您可以计算范围内的无符号整数

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

如果您的范围同时包含正数和负数，则将其拆分为零，以便进行交易

大多数复杂情况是在您希望精确计数时产生的。在这种情况下，您需要调整范围是打开还是关闭，并精确地计数一次零。

出于您的目的，相差一或两个

这是一个简单的程序，可以演示这个想法。

  #include< iostream> 
 #include< cmath> 
使用命名空间std; 
 
 uint64_t count（双起始，双终止）; 
 
 void testit（预期为uint64_t，双开始，双结束）{
 cout<<十六进制<< 应该是<<预期<< ：<< count（开始，结束）
<<恩德尔
} 
 
双重递增（double data，int count）{
 int i; 
 for（i = 0; i  data = nextafter（data，INFINITY）; 
} 
返回数据； 
} 
 
双重减量（double data，int count）{
 int i; 
 for（i = 0; i< count; i ++）{
 data = nextafter（data，-INFINITY）; 
} 
返回数据； 
} 
 
 int main（）{
 testit（（uint64_t）1 << <52，1.0，2.0）; 
 testit（5，3.0，增量（3.0，5））; 
 testit（2，减量（0，1），增量（0，1））; 
 testit（（uint64_t）1<< 52，-2.0，-1.0）; 
 testit（1，-0.0，增量（0，1））; 
 testit（10，减量（0,10），-0.0）; 
返回0； 
} 
 
 //返回表示双精度的位模式为
 // 64位无符号整数。 
 uint64_t toInteger（double data）{
 return * reinterpret_cast< uint64_t *>（& data）; 
} 
 
 //计算一个范围内的double，假设double 
 //是IEEE 754 64位二进制。 
 //计数[start，end），包括开始但不包括结束
 uint64_t count（double start，double end）{
 if（！（isfinite（start）&& isfinite（结束）&&开始< =结束））{
 //在此处插入实际错误处理
 cerr<< 错误<<恩德尔
返回0； 
} 
 if（start< 0）{
 if（end< 0）{
 return count（fabs（end），fabs（start））; 
}否则if（end == 0）{
 return count（0，fabs（start））; 
}否则{
 return count（start，0）+ count（0，end）; 
} 
} 
 if（start == -0.0）{
 start = 0.0; 
} 
 return toInteger（end）-toInteger（start）; 
} 
  

Important Edit: The original question was about getting the density of both doubles and fractions. As i get the answer for doubles and not for fractions, I'm changing the topic to close this question. The other half of the original question is here

New question

I want to find the density of doubles between 2 given numbers but I can't think of a good way. So I'm looking for a closed-form expressions doublesIn(a,b). Or some code that does the work in a reasonable time.

With doubles i should use some formula with mantissa and exponent I'm not aware of. I already have a code using nextafter and it's awfully slow close to [-1,1] (below 1e6 is very slow)

.

Any ideas? Thanks in advance! :)

PS: If you want to know, I'm coding some math stuff for myself and I want to find how useful would be to replace double with a fraction (long,long or similar) on certain algorithms (like Gaussian elimination, newton's method for finding roots, etc), and for that I want to have some measures.

解决方案

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

这篇关于2个给定数字之间的双倍密度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！