计算百万位e

liangbch

mathe的算法并不快，那个计算过程需要b次多重精度乘法运算，而我的算法则不用，只是做后阶段计算$e^a$复杂度较高。
  
下面我们用数学语言重新描述一下我的算法，这个算法使用于以$10^k$为基的多重精度运算。
   若 $e^x=10^d*e^a$ 这里, $d in ZZ, a<log(10)~~2.30$
   两边取自然对数得
    $x=d*log(10)+a$
     $=> d= |__x/log(10)__| $  |_  _| 表示向下取整
  $=> a=x - d*log(10)$
     故 $e^x=10^d*e^a$

类似的使用于2进制的算法
若 $e^x=2^b*e^a$ 这里, $b in ZZ, a<log(2)~~0.693$
   两边取自然对数得
    $ x=b*log(2)+a$
    $=> b= |__ x/log(10) __|$  |_  _| 表示向下取整
    $=> a=x - b*log(10)$
    故 $e^x=2^b*e^a$

gxqcn

哦，明白了。
你的算法在10进制下，乘以 10^d 是个简单“移位”运算而已。

但无论如何，似乎都要将常数 ln(10)（或 ln(2)） 保留足够的精度以应付尾数 $a$ 的计算。

gxqcn

假如 $e^x$ 指定精度的计算可以足够快，
那么对于其它底数，即便指数为正整数的，通过换底成 $e^x$ 形式去计算指定精度，是否更划算？

liangbch

是啊，但前提是必须事先对数运算log(x).
     

　　你能注意到，对于采用十进制，余项$e^a$, $a<log(10)~~2.30$, 仍然太大，使用泰勒公式求值时，收敛的依然很慢，为了提高收敛速度，需要将a降到足够小，为此不得使用对数表。

　　我们定义对数表t[], t[  i  ].n, 和 t[  i  ].v 表示对数表第i个表项的真数和对数，t[  i  ].v=log(t[  i  ].n).假如你我们想通过查表，使得这个余项a小于r, 那么在构建对数表时，如果采用1级对数表，必须使得相邻表项的对数值的差小于等于r, 即t[  i+1 ].v - t[  i  ].v <=r。如这个对数表的最大值是m,.则至少需要 m/r个表项。如此看来降低余项r的值和缩小对数表的表项是一对矛盾。为了解决这个矛盾。只能使用多级对数表。例如：1级对数表的各个表项的对数值的差是0.1左右，最大值是2.3,， 则有0.1, 0.2, ...2.3 共23个表项，二级对数表是0.01,0.02,0.99共10个表项，继续下去可能做一个3级，4级对数表。容易看出，如果使得余项r小于一个指定值， 若每级对数表的表项越少，则对数表的级数会较多。

　　我的一个设想是，采用多级对数表，每次通过第k级对数表处理后，r的值可缩小1/256,相应的每对数表的表项为256-400个。因为对数表各个点不是均匀分布的。”通过第k级对数表处理”是指，假如 $e^x = y* e^a$, 在第k级对数表中找一个合适的表项tk[  i  ].v ,使得tk[  i  ].v刚好小于a, 则
$e^x$ 可化为 $ e^x =y* tk[ i ].n * e^ {r}, r = a- tk [ i ].v$.
　　另一个问题是，使用较少的小质数，很难构建足够密集的对数表。 如可能很难在区间[T1,T2] 找到满足这样条件的分数p/q,使得 p/q的对数值基本位于[T1,T2]的中间，而p,q的质因数小于指定的值,且p和p小于指定值。
  
　　随着区间[T1,T2]越来越小，找到一个符合条件的p/q 也越来越难，为此不得不放宽p,q的范围，p/q的质因数可以更大，p和q也可以更大。

　　构建一个足够密集的对数表，且每个表项tk[ i ].n 的分子和分母的质因数尽可能小，tk[ i  ].n 的分子和分母也尽可能小，是一件很复杂的事情，需要大量计算。我一直在业余时间从事这方面的工作，目前仍没有最终完成这个多级对数表的构建，相信经过一段时间后最终完成的。


　　顺便说一些，求小质数的高精度对数值，目前已经找到比较满意的解决办法，虽然没有计算e快，但速度还是非常之快的。

无心人

计算一个12位小质数的对数到32位，速度有多快？
一秒钟计算1000000次能达到么？

liangbch

我所说的小质数指2，3，5，7这样前32个甚至前16个小质数。计算他们的对数对于计算普通的数的对数很有帮助。 你所说的那个达到12位数字的质数不是通常意义的小质数，计算他们的对数不具有特别的意义。

仙剑魔

我根据大家的思路也想了下
先假设x是个高精度的数,所以写成2进制就有点麻烦了
考虑科学记数法,把x写成a*10^b,其中a在[1,10),b为整数
这样
e^x
=e^(a*10^b)
=(e^a)^(10^b)
=(e^a)^(2^b*5^b)
=(e^a)^(2^(4b)*0.625^b)
=(e^(a*0.625^b))^(2^4b)
这样就计算
c=a*0.625^b
d=e^c
然后把d平方4b次

还有就是计算ln(x)有什么好的方法呀?
其实我在写大数计算,所以在寻找好的算法

无心人

呵呵

我也想知道如何最快速计算对数
media2005的圆周率和阶乘的问题
到目前懒得算了
高精度浮点太慢了

liangbch

以我目前的思路，求一个12位质数的对数和求一个12位任意数的对数没有什么区别，至于速度。我还没有完全是实现这个程序，无法给出数据。

仙剑魔

ln(x)也可以用x=a*10^b展开
ln(x)=ln(a*10^b)=ln(a)+b*ln(10)
所以如果有ln(x)在x比较小的时候的快速算法就OK啦