algorithm - 获得 e 值的最快方法是什么？

Question

以中等精度找到 e 值的最优化算法是什么？

我正在寻找对速度比高精度更重要的优化方法之间的比较。

编辑:我所说的中等准确度是指最多 6-7 位小数。但如果速度上存在巨大差异，那么我可以在 4-5 个位置上解决。

Answer 1

1. 基本数据类型

   如评论中所述，6-7 小数位的精度太低，无法通过算法执行此操作。而是使用一个常数，这是最快的方法。

   const double e=2.7182818284590452353602874713527;
   

   如果涉及到 FPU，常量通常也存储在那里......而且与计算它的函数相比，单个常量占用的空间要少得多......

2. 有限精度

   只有当涉及到 bignum 时，才可以使用算法来计算 e。该算法取决于目标精度。同样，对于较小的精度，使用预定义常量:

   e=2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193200305992181741359662904357290033429526059563073813232862794349076323382988075319525101901157383418793070215408914993488416750924476146066808226480016847741185374234544243710753907774499206955170189
   

   但通常以十六进制格式进行更快更精确的操作:

   e=2.B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF324E7738926CFBE5F4BF8D8D8C31D763DA06C80ABB1185EB4F7C7B5757F5958490CFD47D7C19BB42158D9554F7B46BCED55C4D79FD5F24D6613C31C3839A2DDF8A9A276BCFBFA1C877C56284DAB79CD4C2B3293D20E9E5EAF02AC60ACC93ECEBh
   

   对于有限/有限精度和最佳速度是 PSLQ算法最好。我的理解是，它是寻找实数和整数迭代之间关系的算法。

   • here is my favourite PSLQ up to 800 digits of Pi PSLQ example

3. 任意精度

   对于任意或“固定”精度，您需要具有可变精度的算法。这是我在我的 arbnum 类中使用的:

   e=(1+1/x)^x where x -> +infinity
   

   如果您选择 x 作为 2 的幂，请意识到 x 只是数字的单个设置位并且 1/x 具有可预测的位-宽度。所以 e 将通过单除法和 pow 获得。这里有一个例子:

   arbnum arithmetics_e()          // e computation min(_arbnum_max_a,arbnum_max_b)*5 decimals
       {                           // e=(1+1/x)^x  ... x -> +inf
       int i; arbnum c,x;
       i=_arbnum_bits_a; if (i>_arbnum_bits_b) i=_arbnum_bits_b; i>>=1;
       c.zero(); c.bitset(_arbnum_bits_b-i); x.one(); x/=c; c++;
       for (;!x.bitget(_arbnum_bits_b);x>>=1) c*=c;    //=pow(c,x);
       return c;
       }
   

   其中_arbnum_bits_a,_arbnum_bits_b是二进制小数点前后的位数。所以它分解为一些位运算，一个 bignum 除法和平方的单一幂。请注意，乘法和除法对于 bignums 并不那么简单，通常涉及 Karatsuba 或更糟的......

   还有多项式方法不需要 bignum 算法，类似于计算 Pi。这个想法是在不影响先前计算的位(太多)的情况下每次迭代计算二进制位 block 。它们应该更快，但与往常一样，对于任何取决于实现及其运行的硬件的优化。