在C中将连续的二进制分数转换为十进制分数
Convert continues binary fraction to decimal fraction in C
我实现了对二的平方根的逐位计算。每一轮它都会输出一位小数部分，例如
1 0 1 1 0 1 0 1等
我想将此输出转换为十进制数：
4 1 4 2 1 3 6等
我面临的问题是，这通常会像这样工作：
1 * 2^-1 + 0 * 2^-2 + 1 * 2^-3等
我想完全避免分数，因为我想使用整数将二进制转换为十进制。我也想在计算后立即打印每个小数位。
转换为十六进制很简单，因为我只需要等待 4 位。是否有一种智能方法可以转换为 base10，它只允许观察整个输出的一部分，并理想地从等式中删除数字，一旦我们确定它不会再改变，即
1 0
2 0,25
3 0,375
4 0,375
5 0,40625
6 0,40625
7 0,4140625
8 0,4140625
处理完第 8 位后，我很确定 4 是第一个小数位。因此，我想从等式中删除 0.4 complety 以减少我需要处理的位。
您可以使用乘法和除法方法来减少浮点运算。
1 0 1 1
相当于 1*2^0+0*2^1+2^(-2)+2^(-3) 可以简化为 (1*2^3+0*2^2+1*2^1+1*2^0)/(2^3) 只有除法仍然是浮点数运算其余都是整数运算。乘以2可以通过左移实现。
Is there a smart approach to convert to base10 which allows to observe only a part of the whole output and ideally remove digits from the equation, once we are certain that it wont change anymore (?)
是的，最终在实践中，但理论上，在 select 个案例中没有。
这类似于 Table-maker's dilemma。
考虑以下对接近 0.05 的值的处理。只要二进制序列是 .0001 1001 1001 1001 1001 ... ，我们就无法知道它的十进制等效值是 0.04999999... 或 0.05000000... 非零。
int main(void) {
double a;
a = nextafter(0.05, 0);
printf("%20a %.20f\n", a, a);
a = 0.05;
printf("%20a %.20f\n", a, a);
a = nextafter(0.05, 1);
printf("%20a %.20f\n", a, a);
return 0;
}
0x1.9999999999999p-5 0.04999999999999999584
0x1.999999999999ap-5 0.05000000000000000278
0x1.999999999999bp-5 0.05000000000000000971
代码可以分析传入的二进制小数位序列，然后在每个位之后提出两个问题："if the remaining bits are all 0"十进制是什么？”和"if the remaining bits are all 1"十进制是什么？” .在许多情况下，答案将共享共同的前导有效数字。然而如上所示，只要收到1001，就没有共同的有效小数位。
一个通常的"out" 是有一个关于将永远 显示的小数位数的上限。在那种情况下，代码仅呈现 rounded 结果，即使二进制输入序列保持为 1001，也可以在有限时间内推导出该结果
ad nauseam.
The issue I´m facing is, that this would generally work like this:
1 * 2^-1 + 0 * 2^-2 + 1 * 2^-3 etc.
嗯，1/2 = 5/10 和 1/4 = 25/100 等等，这意味着您需要 5 的幂并将值移动 10 的幂
所以给出 0 1 1 0 1
[1] 0 * 5 = 0
[2] 0 * 10 + 1 * 25 = 25
[3] 25 * 10 + 1 * 125 = 375
[4] 375 * 10 + 0 * 625 = 3750
[5] 3750 * 10 + 1 * 3125 = 40625
编辑：
Is there a smart aproach to convert to base10 which allows to observe only a part of the whole output and idealy remove digits from the equation, once we are certain, that it wont change anymore
在这种情况下，实际上可能会弹出最高有效数字 (MSD)。这会有点长，但请耐心等待
考虑值 X 和 Y：
- 如果 X 的位数与 Y 的位数相同，则 MSD 将发生变化。
10000 + 10000 = 20000
- 如果 Y 比 X 少 1 个或多个数字，则 MSD 可以 更改。
19000 + 1000 = 20000
19900 + 100 = 20000
所以第一点是不言自明的，但第二点是什么能让我们弹出 MSD。我们需要知道的第一件事是，我们添加的值在每次迭代中不断地被分成两半。这意味着如果我们只考虑 MSD，base10 中的最大值是 9，这将产生序列
9 > 4 > 2 > 1 > 0
如果我们将这些值相加，它将等于 16，但如果我们尝试考虑下一位的值（例如 9.9 或 9.999），该值实际上接近 20，但不会超过 20。这意味着如果 X 有 n 个数字并且 Y 有 n-1 个数字，X 的 MSD 仍然可以改变。但是如果X有n位，Y有n-2位，只要X的n-1位小于8，那么MSD就不会改变（否则就是8+2=10或者9+2= 11 这意味着 MSD 将发生变化）。这里有一些例子
假设 X 是 sqrt(2) 的 运行 总和，Y 是 5^n:
1. If X = 10000 and Y = 9000 then the MSD of X can change.
2. If X = 10000 and Y = 900 then the MSD of X will not change.
3. If X = 19000 and Y = 900 then the MSD of X can change.
4. If X = 18000 and Y = 999 then the MSD of X can change.
5. If X = 17999 and Y = 999 then the MSD of X will not change.
6. If X = 19990 and Y = 9 then the MSD of X can change.
在上面的例子中，在点#2 和#5 上，1 已经可以弹出了。然而对于第 6 点，可能有 19990 + 9 + 4 = 20003，但这也意味着 2 和 0 都可以在发生之后弹出。
这是 sqrt(2) 的模拟
i Out X Y flag
-------------------------------------------------------------------
1 0 5 0
2 25 25 1
3 375 125 1
4 3,750 625 0
5 40,625 3,125 1
6 406,250 15,625 0
7 4 140,625 78,125 1
8 4 1,406,250 390,625 0
9 4 14,062,500 1,953,125 0
10 41 40,625,000 9,765,625 0
11 41 406,250,000 48,828,125 0
12 41 4,062,500,000 244,140,625 0
13 41 41,845,703,125 1,220,703,125 1
14 414 18,457,031,250 6,103,515,625 0
15 414 184,570,312,500 30,517,578,125 0
16 414 1,998,291,015,625 152,587,890,625 1
17 4142 0,745,849,609,375 762,939,453,125 1
我实现了对二的平方根的逐位计算。每一轮它都会输出一位小数部分，例如
1 0 1 1 0 1 0 1等
我想将此输出转换为十进制数：
4 1 4 2 1 3 6等
我面临的问题是，这通常会像这样工作：
1 * 2^-1 + 0 * 2^-2 + 1 * 2^-3等
我想完全避免分数，因为我想使用整数将二进制转换为十进制。我也想在计算后立即打印每个小数位。
转换为十六进制很简单，因为我只需要等待 4 位。是否有一种智能方法可以转换为 base10，它只允许观察整个输出的一部分，并理想地从等式中删除数字，一旦我们确定它不会再改变，即
1 0
2 0,25
3 0,375
4 0,375
5 0,40625
6 0,40625
7 0,4140625
8 0,4140625
处理完第 8 位后，我很确定 4 是第一个小数位。因此，我想从等式中删除 0.4 complety 以减少我需要处理的位。
您可以使用乘法和除法方法来减少浮点运算。
1 0 1 1
相当于 1*2^0+0*2^1+2^(-2)+2^(-3) 可以简化为 (1*2^3+0*2^2+1*2^1+1*2^0)/(2^3) 只有除法仍然是浮点数运算其余都是整数运算。乘以2可以通过左移实现。
Is there a smart approach to convert to base10 which allows to observe only a part of the whole output and ideally remove digits from the equation, once we are certain that it wont change anymore (?)
是的，最终在实践中，但理论上，在 select 个案例中没有。
这类似于 Table-maker's dilemma。
考虑以下对接近 0.05 的值的处理。只要二进制序列是 .0001 1001 1001 1001 1001 ... ，我们就无法知道它的十进制等效值是 0.04999999... 或 0.05000000... 非零。
int main(void) {
double a;
a = nextafter(0.05, 0);
printf("%20a %.20f\n", a, a);
a = 0.05;
printf("%20a %.20f\n", a, a);
a = nextafter(0.05, 1);
printf("%20a %.20f\n", a, a);
return 0;
}
0x1.9999999999999p-5 0.04999999999999999584
0x1.999999999999ap-5 0.05000000000000000278
0x1.999999999999bp-5 0.05000000000000000971
代码可以分析传入的二进制小数位序列，然后在每个位之后提出两个问题："if the remaining bits are all 0"十进制是什么？”和"if the remaining bits are all 1"十进制是什么？” .在许多情况下，答案将共享共同的前导有效数字。然而如上所示，只要收到1001，就没有共同的有效小数位。
一个通常的"out" 是有一个关于将永远 显示的小数位数的上限。在那种情况下，代码仅呈现 rounded 结果，即使二进制输入序列保持为 1001，也可以在有限时间内推导出该结果 ad nauseam.
The issue I´m facing is, that this would generally work like this:
1 * 2^-1 + 0 * 2^-2 + 1 * 2^-3 etc.
嗯，1/2 = 5/10 和 1/4 = 25/100 等等，这意味着您需要 5 的幂并将值移动 10 的幂
所以给出 0 1 1 0 1
[1] 0 * 5 = 0
[2] 0 * 10 + 1 * 25 = 25
[3] 25 * 10 + 1 * 125 = 375
[4] 375 * 10 + 0 * 625 = 3750
[5] 3750 * 10 + 1 * 3125 = 40625
编辑：
Is there a smart aproach to convert to base10 which allows to observe only a part of the whole output and idealy remove digits from the equation, once we are certain, that it wont change anymore
在这种情况下，实际上可能会弹出最高有效数字 (MSD)。这会有点长，但请耐心等待
考虑值 X 和 Y：
- 如果 X 的位数与 Y 的位数相同，则 MSD 将发生变化。
10000 + 10000 = 20000
- 如果 Y 比 X 少 1 个或多个数字，则 MSD 可以 更改。
19000 + 1000 = 20000
19900 + 100 = 20000
所以第一点是不言自明的，但第二点是什么能让我们弹出 MSD。我们需要知道的第一件事是，我们添加的值在每次迭代中不断地被分成两半。这意味着如果我们只考虑 MSD，base10 中的最大值是 9，这将产生序列
9 > 4 > 2 > 1 > 0
如果我们将这些值相加，它将等于 16，但如果我们尝试考虑下一位的值（例如 9.9 或 9.999），该值实际上接近 20，但不会超过 20。这意味着如果 X 有 n 个数字并且 Y 有 n-1 个数字，X 的 MSD 仍然可以改变。但是如果X有n位，Y有n-2位，只要X的n-1位小于8，那么MSD就不会改变（否则就是8+2=10或者9+2= 11 这意味着 MSD 将发生变化）。这里有一些例子
假设 X 是 sqrt(2) 的 运行 总和，Y 是 5^n:
1. If X = 10000 and Y = 9000 then the MSD of X can change.
2. If X = 10000 and Y = 900 then the MSD of X will not change.
3. If X = 19000 and Y = 900 then the MSD of X can change.
4. If X = 18000 and Y = 999 then the MSD of X can change.
5. If X = 17999 and Y = 999 then the MSD of X will not change.
6. If X = 19990 and Y = 9 then the MSD of X can change.
在上面的例子中，在点#2 和#5 上，1 已经可以弹出了。然而对于第 6 点，可能有 19990 + 9 + 4 = 20003，但这也意味着 2 和 0 都可以在发生之后弹出。
这是 sqrt(2) 的模拟
i Out X Y flag
-------------------------------------------------------------------
1 0 5 0
2 25 25 1
3 375 125 1
4 3,750 625 0
5 40,625 3,125 1
6 406,250 15,625 0
7 4 140,625 78,125 1
8 4 1,406,250 390,625 0
9 4 14,062,500 1,953,125 0
10 41 40,625,000 9,765,625 0
11 41 406,250,000 48,828,125 0
12 41 4,062,500,000 244,140,625 0
13 41 41,845,703,125 1,220,703,125 1
14 414 18,457,031,250 6,103,515,625 0
15 414 184,570,312,500 30,517,578,125 0
16 414 1,998,291,015,625 152,587,890,625 1
17 4142 0,745,849,609,375 762,939,453,125 1