Tタイプの浮動小数点数の配列Tがあります。 float または double のいずれかです。
T x[n];
これらの数値は厳密に正であり、並べ替えられています。つまり、
0 < x[0] < x[1] < x[2] < ... < x[n-1]
次の不等式が厳密に満たされるようなH型の最小の浮動小数点数を見つけたい:T
int(x[i+1]*H) > int(x[i]*H) // for i=0..n-2
x心配するアンダーフローやオーバーフローの問題がないような数値であると仮定しましょう。
以下で説明するように問題に取り組んでいますが、それが堅牢であるかどうかはわかりませんが、うまくいくと次善の結果が生じると思います。
これを解決する堅牢で正確な方法はありますか? 最適ではないソリューションを受け入れることもできますが、少なくとも堅牢である必要があります。
私の現在の方法
この表記法を使用して、丸め誤差の影響を受ける可能性m(x)のある概数の浮動小数点数を示します。x次の節では、適切な上限と下限を考慮して、以下の不等式を修正します。以下は、ソース コードとして解釈されるのではなく、最終的な方程式に到達するための数学的手順と推論として解釈されることに注意してください。
Let a(x) be the closest floating point number toward -inf
Let b(x) be the closest floating point number toward +inf
// Original inequality, where the operation affected by rounding error
// are marked with m()
int(m(x[i+1]*H)) > int(m(x[i]*H)) // for i=0..n-2
// I remove `atoi` subtracting and adding 0.5
// this is a conceptual operation, not actually executed on the machine,
// hence I do not mark it with an m()
m(x[i+1]*H) - 0.5 > m(x[i]*H) + 0.5 // for i=0..n-2
// I reorganize terms
m(x[i+1]*H) - m(x[i]*H) > 1.0 // for i=0..n-2
// I would like to resolve the m() operator with strict LHS minorant and RHS majorant
// Note I cannot use `a(x)` and `b(x)` because I do not know `H`
// I use multiplication by `(1+2*eps)` or `(1-2*eps)` as I hope this
// will result in a number strictly greater (or lower) than the original one.
// I already know this does not work for example if x is very small.
// So this seems like a pitfall of this approach.
x[i+1]*H(1-2*eps) - x[i]*H*(1+2*eps) > b(1) // for i=0..n-2
// solve the inequality for H, marking the operations affected by rounding
// with m()
H > m( b(1) / m( x[i+1](1-2*eps) - x[i]*(1+2*eps) ) ) // for i=0..n-2
// take majorant or minorant as appropriate for rounded terms
H > b( b(1) / a( x[i+1](1-2*eps) - x[i]*(1+2*eps) ) ) // for i=0..n-2
// and eventually take a majorant which gives me the final formula for H
H = b( b( b(1) / min{ a( x[i+1](1-2*eps) - x[i]*(1+2*eps) ) } ) )