Revista INTEGRACIÓN Universidad Industrial de Santander Escuela de Matemáticas Vol. la, No 2, p. 55-62, julio--diciembre de 1995

CARLOS

E.

BRUCE

FERNÁNDEZ

H.

OSSA f

EDWARDSt

Si una persona entiende perfectamente lo que significa que un número sea la raíz cuadrada de otro número positivo, ¿qué método utilizaría para calcular a mano, digarnas, la raíz cuadrada de 53 con cuatro dígitos exactos? Indudablemente ninguno de los métodos numéricos tradicionales, como el de Newton, sería la escogencia más natural, entre otras cosas porque a lo mejor ni siquiera ha oído hablar de esos métodos. Lo más lógico es que esa per,sona recurra al "ensayo y error". eliga sucesivamente dígitos dJ, d2, da, d4 tales que:

Es decir, que

(1) dI sea el mayor dígito que satisface d~ ~ 53. (2) d2 sea el mayor dígito que satisface (d1,d2)2

~ 53.

(3) da sea el mayor dígito que satisface (dI, d2da)2 (4) d4 sea el mayor dígito que satisface (dI, d2dad4)2

:::; 53. :::; 53.

"El primer autor contó con la colaboración financiera de COLCIENCIAS, mediante pasantía en la Universidad de Florida (autorización no. 047-95). tDepartamento de Matemáticas, Universidad de Antioquia, Medellín, COLOMBIA. ~Departament of Mathematics, University of Florida, Gainesville, Florida 32611, USA.

Como la aproximación parece quedarse corta, entonces ensaya con d2 =

2: 7,22

= (7,1 + O,1)2 = 50,41 + 1,42 + 0,01 = 51,84

< 53,

52,9984 < 53, 53, 1441 > 53,

y elige d4 = O. Ya se tiene la solución del problema: la raíz de 53, con cuatro dígitos exactos, es 7,280. Y si lo desea, puede continuar hasta hallar cualquier número de cifras exactas.

1. Es recursivo: tados.

utiliza los resultados previos para obtener nuevos resul-

3. Tiene baja complejidad algorítmica: evita al máximo operaciones diferentes a sumas, productos por potencias de 10 (desplazamientos de la coma deeim~ y comparaciones. Estas son características de un algoritmo para calcular raíces de funcioneS' elementales, conocido con el nombre de CORDIC, el cual se ha implementado en calculadoras y coprocesadores matemáticos, por ser más eficiente que otros métodos tradicionales, como los de Newton, aproximación polinómica, etc. En este artículo haremos un breve recuento histórico de CORDIC, desarrollaremos el método para el caso de raíces cuadradas y mostraremos un ejemplo. En artículos posteriores extenderemos el uso del método a otras funciones elementales.

CORDIC es un método basado en rotación de coordenadas para el cálculo de productos, divisiones, funciones trigonométricas y sus inversas, funciones hiperbólicas, funciones exponenciales y togarítmicas y raíces cuadradas [6]. El método goza de muy baja complejidad algorítmica, pues las únicas operaciones usadas son multiplicaciones por potencias de 10 (desplazamientos de la coma decimal), sumas, restas, comparaciones y el uso de constantes pregrabadas. Debido a esto es especialmente adecuado para ser implementado dentro de las calculadoras y coprocesadores matemáticos. Esto sugiere que CORDIC es en sí mismo un computador, en el sentido técnico de la palabra. En el año de 1959 Volder [5] describió este computador, al cual llamó COordinate Rotational DIgital Computer, de donde derivó el nombre de CORDIC. Según Schelin [3], la técnica algorítmica del método tiene raíces en el trabajo de Henry Briggs en Arithmetica LtJgaritmica, en el año de 1624. Walther [6] presentó en 1971 un algoritmo CORDIC unificado para todas las funciones elementales. Los artículos que hemos mencionado anteriormente son de difícil lectura, puesto que están orientados hacia la ciencia de la computación, y con terminología un poco confusa. Aunque nunca es necesaria una apología de las matemáticas, queremos hacer notar que CORDIC es un buen ejemplo de aplicación práctica de las mismas. En comunicación personal [4] el equipo técnico de la compañía Texas Instruments indica que la mayoría de las calculadoras TI usan el método CORDIC, al igual que el coprocesador matemático 8087 de Intel. Hewlett-Packard, Texas Instruments y muchas otras compañías usan CORDIC para la evaluación de to-

das las funciones [3J. Es de anotar que ninguno de los mátodos clásicos que se enseñan en los cursos de cálculo y análisis numérico -·-como aproximaciones polinómicas basadas en series de Taylor-· - es utilizado en las calculadoras de hoy en día. De ahí la importancia de conocer .cOR,DIC, pues el uso de las calcqladoras se ha generalizado en la enseñanza de las ciencias e ingeniería.

3. El método CORDIC para la raíz cuadrada Sea X un número positivo cualquiera cuya raíz cuadrada deseamos calcular. Claramente siempre podemos escribir X en la forma

x = x ·10k, donde 1 ~ x < 100 y k es un número par. Entonces para hallar hallar ,¡x, pues .JX = lOk/2.

..¡x

basta

..;x .

Observe además que 1 ~ Ejemplo

1. X

.¡x = J49,

Ejemplo

=

3377 .

,¡x

< 10.

4933,77 puede escribirse X 10.

=

49,3377 . 102,

y

entonces

2. X = 0,0001726 puede escribirse X 10-2.

.¡x = JI;726.

Podemos por lo tanto, sin perder generalidad, restringir nuestra discusión al caso de raíces cuadradas en el intervalo [1,100) . Sea pues x E [1,100). Deseamos hallar r = ,¡x con n dígitos exactos, n ~ 1. Es decir, queremos encontrar dígitos dI, d2, ... ,dn, tales que

Como en la mayoría de los métodos numéricos, la idea es "minimizar el error". Usando matemáticas elementales es fácil demostrar que minimizar En es equivalente a minimizar

y esta es la vía que utilizaremos. Sea Aj la aproximación de r Entonces, Al A2 A3

Aj

= .¡x con j

dígitos exactos, para j

= = =

dI,

= =

d¡, d2d3 ... dj

=

1,2, ... , n.

dl,d2, dI, d2d3,

Aj-l

+

dj .10-3

'+1

j ~ 2,

,

donde los dj son dígitos y dI es el dígito de las unidades, pues 1 ~

.¡x <

10.

Como el método es recursivo, primero debemos obtener dI, minimizando f2, ... ,f~. Utilizaremos las conocidas fórmulas n

n

nA=¿A i=l

y

n2=¿(2i-1). i=l

Así pues tendremos: Para j = 1: E¡

=

x - d~ dl

= x-¿(2i-1), i=l y se elije el dígito dI de modo que E¡ obtenga el menor valor no negativo posible. Para

j ~ 2: fj

=

X -

=

x - (Aj-l'+

=

(x-

=

Ej-l -

5Ej

A~

A~-l)

dj .1O-j+l)2 - (2Aj-Idj

( 2Aj_Idj'

=

5Ej-1 - (lOAj-Idj

~

5Ej-l - (Aj_ldj

·lO-j+1

10-3+1

+ d]

.1O-2i+2)

+ dj2 . 10- 2'+2) 3

. lO-j+1

. 1O-j+2

+ 5d~

+ 5d;

;

. 1O-2i+2)

. 1O-2j+2)

;

lOj-2 . 5Ej = loi-2 . 5fj-1 -

di

L [Aj-1

+ 5 (2i

- 1) . lO-j] ,

(2)

i=l

en donde se elije el dígito dj de modo que 1()i-2. 5fj sea mínimo (no negativo). Si ocurre que este número es cero, el proceso ha terminado. Aunque a primera vista la fórmula (2) parece un poco complicada, las operaciones que aparecen en ella son muy sencillas. Solo requiere sumas, multiplicaciones por diez (que son simples desplazamientos de la coma decimal) y comparaciones. La teoría de la complejidad nos dice que estas operaciones se efectúan con mayor eficiencia en los chips de las calculadoras. Los sumandos en (2) correspondientes al término 5 (2i - 1) son 5, 15, ... ,85, que están pregrabados en la calculadora. Observe entonces que CORDIC elimina multiplicaciones que no sean desplazamientos de la coma. (Las calculadoras modernas operan en base diez, no en base dos.) El siguiente ejemplo ilustra dos cosas: primero, el uso de las reglas de decisión (1) y (2) del método CORDIC para raíces cuadradas; segundo, que el método mismo no está hecho para trabajarlo a mano, sino para implementarlo dentro de las calculadoras.

Ejemplo 3. Vamos a aproximar y'4933, 77 con 6 dígitos exactos. .102,

Ejemplo 1, hacemos 4933,77= 49,3377 Ímemos la raíz cuadrada de x = 49,3377.

Según el Y por 10 tanto, basta que aprox-

Para j = 1: d1

1'1

=x -

L (2i

- 1).

i=l

Debemos escoger dI de modo que 1'1 sea el menor número positivo posible. Entonces, tomamos tantos términos en la sumatoria como sean necesarios para que esto se cumpla: d1

q

=

X -

L (2i

- 1)

i=l

=

49,3377 - [1 + 3 + 5 + 7 + 9 + 11 + 13]

=

0,3377. [1 + 3 + 5 + 7 + 9 + 11 + 13J

Fueron necesarios 7 términos de la sumatoria, por 10 tanto dI = 7. Nuestra

=7Y

aproximación es, por ahora, Al

tenemos 1'1

= 0,3377.

Para j ~ 2 debemos utilizar la regla de decisión (2).

Para j = 2: d,

L [7 + 5 (2i -

51'2 = 5fl -

1) .10-2]

i=l d,

=

L [7 + 5 (2i -

1,6885 -

1) . 10-2] .

i=l

Puesto que con d2 = 1 ya se obtiene un valor negativo para 51'2, entonces deducimos que d2 = O.Nuestra aproximación por ahora es A2 = 7, O, y tenemos 51'2 5E'¡ = 1,6885.

=

Para j = 3:

I: d:t

501'3 =

501'2 -

[7, 0+ 5 (2i - 1) . 10-3]

i=l

=

16,885 - [(7, O + 0,005)

=

2,865.

+ (7, O + O,015)]

Con dos términos de la sumatoria se obtuvo el menor valor positivo de 501'.3, Así que d3 = 2, A3 = 7,02 y 50"3 = 2,865. Para j = 4:

I: d4

5001'4 =

500€3 -

[7,02

+ 5 (2i

- 1) . 10-4]

i=l

= 28,65 - [(7,02

+ 0,0005) + (7,02 + 0,0015) + (7,02 + O,0025)

+ (7,02 + 0,0035)] =

0,562.

Con cuatro términos de la sumatoria Re obtuvo el menor valor positivo de 5001'4. Así que d4 = 4, A4 = 7,024, Y 5001'4 = 0,562. Para j = 5: dr.

50001'5 = 50001'4 ~

L [7,024

+ 5 (2i

- 1) . 10-5]

i=l

ds

=

ó,62 -

L [7,024 + i=1

Ó

(2i - 1) . 10-5]

.

Puesto que con ds = 1 ya se obtiene un valor negativo para 5000fS, entonces deducimos que ds = O. Nuestra aproximación por ahora es As = 7,0240 Y 5000fS = 5,62. Para j = 6: c4;

50000f6

50000f5 -

I: [7,0240

+ 5 (2i

- 1) . 10-6]

i=l

= 56,2=

[(7,0240

+ 0,000005) + ... + (7,0240 + O,000075)J

0,00768.

Con ocho términos de la sumatoria se obtuvo el menor valor positivo. Así que = 8 y A6 = 7,02408 es la aproximación deseada para J49, 3377. Fina1,mente,

d6

/4933,77

=

/49,3377·

:::::!

7,02408·

=

70,2408.

10 10

El método CORDIC es apropiado para el cálculo de funciones elementales debido a su simplicidad, precisión y eficiencia algorítmica. Sus aplicaciones incluyan las calculadoras HP, TI y coprocesador 8087 de Inte1.

[1] ROYCE A. PAULEY AND BRIAN C. ALVERS, AppToximating Elementar'y Functions Ufling the CORDIC Method, Senior Thesis with Bruce Edwards, 1994. [2] RICARD J. PULSKAMP AND J AMES A. DELANEY, Computer and Calculator Computation of Elementary Funtions, UMAP Module 708, 1991. [3] CHARLES W. SHELIN, Calculator function approximation, American Mathematics Monthly, 1983, pp. 317--325. [4] Tmnscendental Function Al,qoT'ithms, Post from Texas Instruments to Graph TI mailing list, March 8, 1993. . [5] JACK E. VOLDER, The CORDIC Computing Technique, IRE Transactions on Electronic Computers, September 1959, pp.330-334. [6] J. S. WALTHER, A Unified Algorithm for Elementary Functions, Joint Computer Conference Proceedings, Spring 1971, pp. 379-385.