来点有意思的问题，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的方幂的开始数字问题