Calculadoras y algoritmos de cálculo

Cuando usamos una calculadora, queremos obtener un resultado relativamente exacto dentro de un tiempo razonable. Para una exactitud dada, los diseñadores de los circuitos electrónicos de la calculadora implementan aquéllos algoritmos que sean más fáciles de construir y que sean más rápidos.

Tomemos como ejemplo el cálculo del número e, la base de los logaritmos naturales. La definición de e por Jacob Bernoulli (1) en el s. XVII es el límite, cuando n se hace infinitamente grande, de la expresión:

( 1 + 1/n ) ^ n.

En el siglo XVIII, se probó que e es el límite cuando n se hace infinitamente grande de la sumatoria:

sumatoria desde k = 0 hasta n de 1/k!

Para un n dado, la definición de Bernoulli es aparentemente más simple, pues bastan sólo tres operaciones para calcular e: una división (1/n), una suma y una elevación a potencia. En cambio, el método de la sumatoria parece tremendaente engorroso: hay que calcular n+1 términos (desde 0 hasta n), empleando para cada uno una división y el cálculo de un factorial. Tenemos por lo tanto 2(n+1) operaciones, a las que hay que agregar n sumas, para un total de 3n+2 operaciones.

Pero si miramos un poco más de cerca las cosas, veremos que hay un poco más de trabajo en el cálculo de la potencia y del factorial, respectivamente. Un buen algoritmo de potenciación requiere del orden de raiz(n) multiplicaciones para elevar un número dado a n. En el caso del cálculo de n!, se requieren n-1 multiplicaciones; pero como n! se calcula dentro de una sumatoria, se puede usar para cada término k el resultado de (k-1)! obtenido en el término anterior para calcular k! simplemente usando una multiplicación adicional.

En resumen, para calcular e se requieren aproximadamente 2 + raiz(n) operaciones usando la definición de Bernoulli y 4n+3 operaciones usando la sumatoria. Pareciera que todavía el uso de la definición de Bernoulli lleva la delantera.

Pero ahora entra a tallar la precisión del método: por el método de Bernoulli (2), el primer decimal exacto de e se obtiene para n=74 (o sea, aprox. 11 operaciones); el método de la sumatoria llega a su primer decimal exacto para n=4 (19 operaciones).

Para llegar a su segundo decimal exacto, por Bernoulli necesitamos n=164 (15 operaciones), mientras la sumatoria requiere n=5 (23 operaciones).

A partir del tercer decimal exacto, el método de la sumatoria toma ventaja sobre Bernoulli: Bernoulli requiere n=4822 (72 operaciones), mientras que la sumatoria requiere n=6 (27 operaciones). Para el cuarto decimal, Bernoulli requiere n=16.600 (131 operaciones), mientras que la sumatoria requiere n=7 (31 operaciones). Para el quinto decimal, Bernoulli requiere n=744000 (864 operaciones), mientras la sumatoria necesita sólo n=9 (37 operaciones).

Con n=15, el método de la sumatoria permite obtener 12 decimales exactos. El de Bernoulli, para todos los efectos prácticos, está limitado a una precisión de seis decimales, a causa de los inevitables errores de redondeo y truncamiento y su propagación, que se producen al representar decimales no exactos (como 1/3.000.000) en el espacio limitado de un circuito electrónico.

Notas:

(1) Bernoulli descubrió que la expresión (1+1/n)^n convergía a una cantidad, aunque el no usó la letra e para denotar dicha cantidad; el uso de "e" fue obra de Euler, a principios del s. XVIII.

(2) En este artículo usamos la expresión "el método de Bernoulli" para denotar el cálculo de e usando la expresión (1+1/n)^n descubierta por Bernoulli. No hay un método formal llamado "Método de Bernoulli".