与えられた2つの数値の間の倍数の密度

Question

重要編集：最初の質問は、倍率と分数の両方の密度を得ることでした。私は倍数ではなく倍数の答えを得るので、この質問を閉じるためにトピックを変更しています。元の質問の他の半分はhere

新しい問題

私は2つの与えられた数字の間ダブルスの密度を見つけたいですが、私は良い方法を考えることはできません。だから私は閉形式doublesIn（a、b）を探しています。または、妥当な時間内に作業を行うコード。

二重では、私は仮数と指数でいくつかの式を使用する必要があります私は認識していません。 nextafterを使用したコードが既にあります。[-1,1]に非常に遅いです（1e6以下は非常に遅いです）

アイデア？前もって感謝します！ :)

PS：あなたが知りたいのであれば、私は数学のものを自分でコーディングしていますが、あるアルゴリズムでdoubleを（長い、長くても似たような）ガウスの消去、ニュートンの根を見つける方法など）、そのためにいくつかの対策が必要です。

Answer 1

このプログラムを含めて、私はdoubleがIEEE 754 64ビット2進浮動小数点で表されると仮定しています。これが最も可能性の高いケースですが、C++標準では保証されていません。

終点から始点を引いて、範囲が開いているか閉じているかを調整することで、一定時間内に範囲内の符号なし整数を数えることができるため、一定時間内に2倍を数えることができます。

有限の負でない範囲の倍数は、整数の連続したシーケンスを形成するビットパターンを持ちます。たとえば、範囲[1.0,2.0]には、[0x3ff0_0000_0000_0000、0x4000_0000_0000_0000]の範囲の各整数に対して1つのdoubleが含まれます。

double型の有限の正の範囲は、double型の負の値が増えるにつれて、符号なしビットパターンの値が大きくなる点を除き、同じように動作します。

範囲に正の数と負の数の両方が含まれる場合は、ゼロで分割して、1つの非負の範囲と別の非正の範囲を扱うようにします。

多くの複雑さは、カウントを正確に取得したいときに発生します。その場合、範囲が開いているか閉じているかを調整し、正確に1回カウントする必要があります。

あなたの目的のために、数億のうち1つまたは2つがオフになることはあまり重要ではありません。

ここに、そのアイデアを示す簡単なプログラムがあります。エラーチェックはほとんど受けていませんので、自己責任で使用してください。

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