2的平方根的X个十进制数需要多少个二进制数

Question

我一直在玩计算 2 的平方根之类的东西。很容易想出一个算法来产生 n 个正确的二进制数字。我需要帮助的是确定我需要多少二进制数字才能得到正确的十进制数字？ m个二进制数会得到我m个十进制数，但m个十进制数可能还不是全部正确。

编辑： 我已经确定二进制 precision = ceil(log2(10^m)).

的下限

考虑一下可能没有严格的上限，因为从 2 的任何较低幂（转换为基数 10 时）进位可能会影响任何更高的基数 10。

因此这可能是一个动态问题，需要评估 m 个二进制数字的小数展开并确定哪些额外的二进制数字可能导致以 10 为基数的进位。

编辑 2： 我可能想多了。在初始计算之后，我可以继续添加 (1x10^(-precision)) 并对结果进行平方，直到我超过 2 - 然后减去 (1x10^(-precision))，我就会得到答案。尽管如此，我仍然对finding/developing这样的算法感兴趣:)

Answer 1

你用的是什么方法？

我假设在 y = x^2

中对 x 进行二进制搜索

整数部分受限于结果sqrt(y)，不能截断，否则结果不对。但是 x 被 y 的一半限制，所以：

ni2 = log2(|y|)

小数部分 很棘手见：

the relation between binary and decimal digits

但是在第一个数字的非线性开始之后，相关性在这里稳定下来，从链接的答案中反转公式：

nf2 = (((nf10-7.810)/9.6366363636363636363636)+1.0)<<5;

ni2 是整数部分二进制 bits/digits
nf2是小数部分二进制bits/digits
nf10 是小数部分的十进制数字

顺便说一句，我使用了 32 位对齐的值，因为这是我用于算术的值所以：

9.6366363636363636363636 = 32/0.30102999566398119521373889472449
0.30102999566398119521373889472449 = log10(2)

Answer 2

令 x 为实数，y 为其近似值。

令 RE 为 y 相对于 x 的相对误差：

RE(x, y) = abs(x - y) / abs(x)

令b为非负整数。基数 b 中的对数相对误差定义为：

LREb(x, y) = -logb(RE(x, y))

其中 logb 是以 b 为底的对数：

logb(z) = log(z) / log(b)

对于任何非负 z。

以b为基数的LRE表示x和y之间的公共数字个数。这里，"number of correct digits" 不是一个整数，而是一个实数：这将简化接下来的计算，避免对 ceil 和 floor 函数的需要，前提是我们接受如下语句："y has 2.3 correct digits with respect to x"。更准确地说，如果 x 和 y 有 q 个公共基数 b，则：

LREb(x, y) >= q - 1

对于这些等式，如果相对误差有上限，则 LREb 有下限。更准确地说，如果：

RE(x, y) <= epsilon

然后：

LREb(x, y) >= -logb(epsilon)

另外，如果以10为底的正确位数为LRE10 = p，则RE = 10^-p，这意味着以2为底的正确位数为：

LRE2 = -log2(10^-p)

2的平方根的X个十进制数需要多少个二进制数

How many Binary Digits needed for X Decimal Digits of Square Root of 2

math

square-root