:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Быстрые вычисления » Число е - школьный метод
  Вычисление числа е - школьный метод



По статье
Xavier Gordon


  Классический метод



По биномиальной теореме Ньютона, получаем

(1+x)n = 1+nx+ n(n-1)
2
x2+...+xn,
для x = 1/n, что, после некоторых преобразований, дает известное соотношение
e
=
1+ 1
1
+ 1
1×2
+ 1
1×2×3
+ 1
1×2×3×4
+ј
(1)
=

lim
n® Ґ 
sn =
lim
n® Ґ 
ж
з
и
n
е
k = 0 
1
k!
ц
ч
ш
,
(2)
полученное Эйлером в 1748 году. Это соотношение весьма эффективно для вычисления числа e, так как факториал числа растет очень быстро. Легко доказать, что
sn < e < sn+ 1
n.n!
.
Эйлер использовал это соотношение для нахождения 23 знаков числа е.

Формула (1) является довольно хорошей для вычисления e. Для получения d десятичных цифр е, достаточно первых K @ d log(10)/log(d) членов.

Cложность вычислений - O(n2/log(n)). Следующая программа вычисляет NbDigits=10000 первых цифр числа е.

/*
** Pascal Sebah : July 1999
** 
** Subject:
**
**    A very easy program to compute e with many digits.
**    No optimisations, no tricks, just a basic program to learn how
**    to compute in multiprecision.  
**
** Formula:
**
**    e = 1+1/1!+1/2!+...+1/k!+...
**
** Data:
**
**    A big real (or multiprecision real) is defined in base B as:
**      X = x(0) + x(1)/B^1 + ... + x(n-1)/B^(n-1)
**      where 0<=x(i)<B
**
** Results: (PentiumII, 450Mhz)
**    
**    1000   decimals :   0.02seconds
**    10000  decimals :   1.2s
**    100000 decimals :  97.0s
**    200000 decimals : 375.0s
**
** With a little work it's possible to reduce those computation
** times by a factor of 3 and more.
*/
#include <stdio.h>
#include <stdlib.h>
long B=10000; /* Working base */
long LB=4;    /* Log10(base)  */
/*
** Set the big real x to the small integer Integer 
*/
void SetToInteger (long n, long *x, long Integer) {
  long i;
  for (i=1; i<n; i++) x[i] = 0;
  x[0] = Integer;
}
/*
** Is the big real x equal to zero \?
*/
long IsZero (long n, long *x) {
  long i;
  for (i=0; i<n; i++)  
    if (x[i])	return 0;
	return 1;
}
/*
** Addition of big reals : x += y
**  Like school addition with carry management
*/
void Add (long n, long *x, long *y) {
  long carry=0, i;
  for (i=n-1; i>=0; i--) {
    x[i] += y[i]+carry;
    if (x[i]<B) carry = 0;
    else {
      carry = 1;
      x[i] -= B;
    }
  }  
}
/*
** Division of the big real x by the integer d 
**  Like school division with carry management
*/
void Div (long n, long *x, long d) {
  long carry=0, xi, q, i;
  for (i=0; i<n; i++) {
    xi    = x[i]+carry*B;
    q     = xi/d;
    carry = xi-q*d;   
    x[i]  = q;        
  }  
}
/*
** Print the big real x
*/
void Print (long n, long *x) {
  long i;
  printf ("%d.", x[0]);
  for (i=1; i<n; i++) {
    printf ("%.4d", x[i]);
    if (i%25==0) printf ("%8d\n", i*4);
  }
  printf ("\n");
}
/*
** Computation of the constant e
*/
void main () {
  long NbDigits=10000, size=1+NbDigits/LB;
  long *e  = (long *)malloc(size*sizeof(long));
  long *uk = (long *)malloc(size*sizeof(long));
  long k=1;
  
  // Formula used : e = 1+1/1!+1/2!+...+1/k!+...
  SetToInteger (size, e,  1); /* e  = 1 */
  SetToInteger (size, uk, 1);	/* uk = 1 */
   while (!IsZero(size, uk)) {
    Div (size, uk, k);  /* uk = u(k-1)/k */
    Add (size, e,  uk); /* e  = e + uk */
    k++;
  }  
  Print (size, e); /* Print out of e */
  free (e);
  free (uk);
}
Возведение в степень. Для любого х можно вычислить ex как выражение
ex =
е
n і 0 
xn
n!
.

Формула (1) отвечает частному случаю x = 1.

Если Вы хотите получить больше информации о различных способах вычисления числа e, то на сайте есть более серьезная статья на английском языке. Более быстрое вычисление числа е также приведено как пример использования Binary splitting method. Дан исходник, довольно сильно превосходящий по быстродействию классический метод.