来点有意思的问题，2的方幂的开始数字问题

mathe · 发表于 2008-4-29 12:06:09

我觉得medie的方法比较好，但是需要加代码判断一下计算误差引起的问题。

medie2005 · 发表于 2008-4-29 12:09:42

是啊,确实出了问题:
已经发现了一个错误:m==63 6.

无心人 · 发表于 2008-4-29 13:44:29

我书里有部分我自己算的结果
等我回家去对照

无心人 · 发表于 2008-4-29 13:47:23

错误太多

无心人 · 发表于 2008-4-29 13:48:54

我觉得
完全可以计算2^n到n=20000
然后针对部分n使用你的方法

计算2^n到20000，应该不会超过100ms吧

mathe · 发表于 2008-4-29 13:55:56

原帖由 无心人 于 2008-4-29 13:48 发表

我觉得
完全可以计算2^n到n=20000
然后针对部分n使用你的方法

计算2^n到20000，应该不会超过100ms吧

我觉得不会快，一直使用累加的方法实O(n^2)的算法。medie的方法是O(n)的。

无心人 · 发表于 2008-4-29 14:11:19

可累加一次是能得到最多4个结果的啊

无心人 · 发表于 2008-4-29 14:22:13

考虑取前32位十进制数字，则使用5个双字，每个保存8个十进制
一旦第五个产生进位，则抛弃首双字，顺序移动，以产生新的5个双字

这么做加法

请问，还是O(n)的么？
误差积累在100000次加法后，大概多大？

无心人 · 发表于 2008-4-29 14:33:47

我觉得
总误差应该不会在一个双字之外

即会至少有两个双字的结果是正确的

mathe · 发表于 2008-4-29 15:00:55

我倒是觉得还是采用medie的算法比较快，毕竟是O(n)的算法。
不过计算需要采用GMP之类的工具。
开始只需要采取普通精度进行计算，当然计算过程中需要判断是否精度不过，如果发现精度不够
那么我们需要提高精度计算对应参数m下的c1,c2，还有log10_2就可以了。
从理论上，应该对于大部分情况，低精度的计算足够了，只需要对于少数情况，需要用到高精度。
还有m正好是10的幂的情况需要特殊处理。
当然仅仅对于这个题目而言，我觉得没有必要，4位数的m不是很高的要求

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 来点有意思的问题，2的方幂的开始数字问题