SISTEMAS NUMERICOS Y OPERACIONES ARITMETICAS DE UN SISTEMACOMPUTACIONAL

Una computadora digital moderna puede estar equipada con varios procesadoresaritmticos (hardware), que manipulan datos de diferentes formatos o resuelvenfunciones aritmticas especiales para aplicaciones generales o dedicadas. Estosprocesadores aritmticos proveen mayor velocidad de cmputo que los mtodostradicionales de computacin. La eleccin de un dado sistema aritmtico condicionatanto al diseo del sistema como a las aplicaciones.

Sea R un conjunto de nmeros reales, la aritmtica real podra definirse como unmapeo algebraico f: R x R R.

Sea M el conjunto de nmeros representados en una mquina, cada nmero enM podra tener solo un numero finito de dgitos. M ser entonces un subconjunto finitode R, esto es, M est contenido en R. Una aritmtica en la mquina podra modelarsepor el mapeo g: M x MM.

La segunda difiere de la primera en el aspecto fundamental de la precisin. Solocmputos de precisin finita pueden ser realizados por los procesadores aritmticos,mientras que la aritmtica real puede producir resultados de precisin arbitraria. LaAritmtica Mquina ser entonces una aproximacin de la Aritmtica Real sujeta a loscontroles de redondeo apropiados.

En trminos de mapeo funcional, la funcin mquina g puede relacionarse a lareal f por la siguiente funcin compuesta g : h o p. Donde el mapeo h se define por h= f| M x MR (la funcin real f restringida al dominio mquina M x M) y el mapeodefinido por p: RM (el esquema de redondeo elegido).

Ntese que las computadoras digitales, en contraste con las unidades aritmticasconvencionales, pueden realizar cmputos de precisin arbitrarios, dada la suficientecapacidad de almacenamiento y tiempo de ejecucin. La precisin finita surge de lasrestricciones en ambos aspectos impuestos al sistema: tamao de palabra restringida,registros, sumadores, capacidad de memoria y los tiempos de ejecucin.

SISTEMAS NUMERICOSLa implementacin de los algoritmos aritmticos en una computadora digital

depende mucho de cmo el dato numrico es almacenado en memoria y en registros.Como las computadoras slo implementan artimticas de precisin finita, todas lasrepresentaciones numricas debern ser restringidas a una longitud finita. Una buenaeleccin del sistema aritmtico y de la representacin numrica interna afecta tanto ala eficiencia de la implementacin de las operaciones mquina como a la exactitud.Generalmente, los sistemas nmericos de las arimticas mquina pueden dividirse encinco categoras:

1- Sistemas Numricos con Base (Conventional Radix Number System) Las computadoras convencionales usan fixed radix, base fija, con r2 y un

conjunto de dgitos {0, 1, 2..., r-1}. Todos los dgitos del nmero son pesados(ponderados) positivamente y cada nmero es representado en forma nica. Algunossistemas especiales pueden usar Mixed Radix, en los cuales diferentes dgitos delnmero asumen valores distintos de la base.

Es el sistema adoptado por la mayora de los sistemas. Slo unos pocos utilizanel sistema reduntante de dgito signado y los restantes sistemas (reiduo, racional,logartmico) no han demostrado an ser eficientes por lo que no han sido aceptados.

Un nmero con base r, X, se representa en una computadora por un vectordigital de (n+k)-tuplas X=(Xn-1, , X0 . X-1 , , X-k)r donde cada componente Xi, para-k

Los primeros n dgitos forman la parte entera del nmero, y los restantes k,indexados negativamente forman la parte fraccionaria, un punto (o coma) separa aambas porciones. En una computadora ese punto es implcito, esto es, no ocupaninguna posicin fsica en el almacenamiento.

En un sistema radix pesado se asocia con cada vector digital X, un valor nicodenotado como la sumatoria de cada dgito multiplicado por el peso de su posicin (o elproducto escalar del vector por el vector peso). En particular, el vector peso ser (rn-1,, r0, r-1, ..., r-k), donde r es la base.

En la prctica hay cuatro sistemas usados frecuentemente correspondiendo a lasbases 2 (binario), 8 (octal), 10 (decimal) y 16 (hexadecimal).

2- Sistemas Numricos de Dgito SignadoEste sistema puede ser considerado como una extensin del caso de Fixed-Radix

en el cual se advierten que los dgitos sean pesados tanto positiva como negativamenteen el conjunto {-, ..., -1, 0, 1,..., } donde es un entero positivo limitado. Un dadovalor numrico en este sistema podr tener ms de una representacin; por ello estesistema es considerado redundante.

3- Sistema Numrico ResiduoA cada dgito no se le asigna un factor de peso, por lo que el orden de los dgitos

es irrelevante en la determinacin del valor del nmero. Adems, mltiples bases sonasignadas a diferentes dgitos.

Un nmero es representado por una n-tupla X={r1, ..., rn}m con respecto a otran-tupla M={m1, ..., mn}, cada ri se denomina residuo de X mdulo m i, donde todos losmi son primos.

4- Sistemas Numricos RacionalesEstos sistemas representan las cantidades numricas como fracciones en

trminos de pares de enteros numerador/denominador. Las operaciones bsicas +,-,*,/de estos nmeros siempre dan nmeros racionales, luego estas operaciones soncerradas, sin recurrir a precisin infinita. Una situacin que torna esto difcil es el casode que numerador/denominador pueden hacerse muy grandes rpidamente.

5- Sistemas Numricos LogartmicosEstos sistemas emplean un nmero real N>1 como base. El conjunto de nmeros is definido por el espacio logartmico LN={x: | |x|=N i, i

es entero} {0}.La idea de aplicar expresiones exponenciales surge para habilitar redondeo

geomtrico mas que aritmtico para aumentar la exactitud.

CLASIFICACION DE LAS OPERACIONES ARITMETICASA- Operaciones Aritmticas Estndar. Esta incluye las 4 funciones aritmticas primitivas: suma, resta, multiplicacin y

divisin tanto en punto fijo como en punto flotante. Toda otra funcin matemticapodr ser expresada en trminos de estas cuatro. Respecto a los dos modos deoperacin podemos decir:

1. Punto fijo (FXP) es usado normalmente en problemas con datos con Fixed-Radix-Point, como los encontrados en aplicaciones comerciales o clculos estadsticos.FXP se puede subdividir en dos subclases, de acuerdo a la posicin aparente del punto.En aritmtica entera todos los resultados se alinean en el extremo derecho de losregistros, como si el punto estuviese en la derecha. En la aritmtica fraccionaria todoslos resultados, independientemente de su longitud, se alinean a la izquierda de losregistros.

2. Punto Flotante (FLP) es usado principalmente en cmputos de tipocientfico e ingenieril, en los cuales se requiere frecuentemente escalamiento. FLPpuede a su vez subdividirse en dos subclases de acuerdo al formato de datos. Cuando

2

se fuerza la normalizacin se tiene la llamada FLP normalizada; cuando no se requierelos operandos normalizados tanto durante etapas intermedias y finales del resultado,se tiene FLP no normalizadas.

B- Funciones Aritmticas Elementales.Se refiere a aquellas operaciones especiales usadas frecuentemente en cmputos

matemticos. No todas las computadoras incluyen estas funciones como hardwareestndar. En el presente la mayora implementa estas funciones elementarias porsoftware o firmware. 'Special Purpose Hardware' est siendo utilizado cada vez ms apartir de los costos decrecientes del hardware.

C- Operaciones Pseudo-Aritmticas. Estas requieren cierto grado de clculo aritmtico, pero principalmente para

propsitos dedicados en la ejecucin de un programa. Dos subclases de operacionespseudo-aritmticas seran:

1. Address Arithmetic: tiene que ver con el cmputo de la direccin efectivade memoria, como indexing, indirect, relative u offset.

2. Data Editing Arithmetic: incluye operaciones lgicas y de transformacinde datos como compare, complement, load, store, shift, normalize, etc. Estas sonusadas en la transformacin de datos de un formato a otro, chequeo de consistenciacon un formato fuente o testeo para controlar la secuencia de ejecucin.

Las instrucciones aritmticas a su vez son subdivididas de acuerdo a la precisinque manejan, ya sean FXP or FLP.

1. Single-Precision Arithmetic: operaciones definidas sobre operandosestndar con longitud de palabra igual a una palabra de memoria.

2. Double-Precision Arithmetic: cada operando usa el doble de la longitud depalabra.

FXP {Integer o Fractional}Operacin SP o DP

FLP {Normalized o Unnormalized}A su vez, una operacin, podr ser binaria o decimal.

USO DE RADIX-2Los humanos estamos acostumbrados al sistema decimal, mientras que una

computadora digital codifica los datos en binario. Esta forma popular de codificacinbinaria est basada en la eficiencia de la representacin, facilidad para el diseoaritmtico, y seguridad de la operacin. Adems, como se demostrar, no se encuentramuy lejos de la base ideal. Ideal se refiere en el sentido de optimizar elalmacenamiento de la informacin.

Para un sistema posicional de base b y n dgitos, podemos establecer que laprecisin, o la cantidad de nmeros bn. Para cada posicin habr un requerimiento de bsmbolos, luego podemos definir una medida de eficiencia de almacenamiento E comoE=n*b. Queremos minimizar E bajo las restricciones de la precisin N=bn, por lo quetenemos que:

N = bn

ln N = n*ln bE = b*n = b*ln N/ln b

Derivando con respecto a b tenemos que dE/db = (ln N)*(ln b 1)/ (ln b)2

Lo cual ser 0 si ln(b)=1, es decir, para b=e. Evidentemente la base derepresentacin debe ser entera, y desde el punto de vista de eficiencia 3 es algo

3

superior a 2, dado que 3/ln3

Obsrvese que cada peso coincide con los cuatro primeros pesos del sistema binarionatural. La ventaja del EXCESO 3 y 5211, ambos no posicionales, es su simetra segnel eje que podemos trazar entre 4 y 5, se observa que la codificacin de dos nmerossimtricos al eje es obtenida complementando cada uno de los bits de uno para pasaral otro. Esto se conoce como autocomplementacin.

El acarreo binario en exceso 3 coincide con el decimal. En exceso 3, esto indicaque el carry generado en sumas con cdigos BCD con estas caractersticas coincide conel carry binario, esto es, el que se obtiene sumando en forma binaria los 1 y 0, quecodifican el dgito decimal, lo cual facilita la implementacin de los mismos.

Los algoritmos aritmtcos pueden ser implementados en la computacin digitalmoderna mediante software, hardware o firmware, o una combinacin de estas tressoluciones. Hacerlo en software resulta lento, y ocupa un gran espacio en memoriapara las rutinas, aunque era ms barato en los comienzos de la industria de lacomputacin. Con el rpidamente decreciente costo del hardware, muy pocascomputadoras usan software para evaluar funciones que se usan frecuentemente.Implementar un algoritmo aritmtico por hardware provee una velocidad de ejecucinmayor y ocupacin mnima de espacio en memoria.

Representacin de NmerosUn nmero signado podr ser positivo o negativo, pero no ambos. Usualmente el

dgito ms a la izquierda de un nmero en sistema posicional es reservado para elsigno. Considrese el siguiente nmero en base r A=(an-1 an-2 .... a0)r. Donde el signo,es decir el dgito an-1 ser 0 o r-1, dependiendo de si A0 o A

-(2n-1-1) A 2n-1-1 Representacin del cero: 000...0 y 111...1 (dirty zero)3. Complemento a la Base (Radix Complement) =(((r-1) n-2 n-3 ... 0)+1)r donde =rn-A y lo tratamos como un pseudo-

positivo.Rango: (10...00)2 A (01....11)2

-2n-1 A 2n-1-1 Representacin del cero: 000...0La suma y la resta resultar ms sencilla que en DRC, pero como se ve,

complementar resulta un poco ms difcil, pues implica una suma que podr afectar atodos los n bits. Esta facilidad en la suma y resta se ver amplificada a la hora deconsiderar la multiplicacin y la divisin. Esta es una de las razones, adems de larepresentacin nica del 0 (clean zero), por la cual RC parece ser el sistema derepresentation preferido actualmente.

Las tres notaciones harn trivial la distincin entre positivos y negativos, ademsde tener rangos iguales (o casi iguales) para representar tanto positivos comonegativos. Se puede ver, adems, que para llenar una palabra si el nmero no es delongitud n-1, se completar con 0's para signo-magnitud el intervalo entre la magnitudy el signo, sea el ya el nmero negativo o positivo. En cambio, para DRC y RC, seextender el signo hacia la derecha hasta alcanzar la magnitud en s, es decir, secompletar con 0's si es positivo o con 1's si es negativo.

Algoritmos de Suma y RestaSigno-Magnitud

Sean X=(xn-1 ... x0) e Y=(yn-1 ... y0) de forma tal que X+Y=S=(sn-1 ... s0). Si xn-1=yn-1, es decir, si tienen el mismo signo entonces:

se suman las magnitudes y sn-1=xn-1=yn-1.si Carryn-1=1 entonces se produjo un Overflow.

Si xn-1yn-1, es decir, si son de distinto signo entonces: si |X|>|Y|, realizo |X|-|Y|sn-1 ser el signo del de mayor magnitud, es decir, sn-1=xn-1.

Disminished Radix ComplementEn DRC para sumar se suman como si fuera todo el nmero incluyendo el signo, unamagnitud.Si X e Y son positivos entonces el Carryn=0. Se produce overflow si sn-1=1.Si X e Y son de distinto signo:

si Carryn=0 el resultado es correcto.si Carryn=1, se descarta el carry y se suma 1 a la posicin menos significativa.

Si X e Y son negativos entonces el Carryn=1, lo descartamos y se suma 1 en la posicinmenos significativa. Se produce overflow si sn-1=0.En general se produce overflow si Carryn Carry n-1=1.

Radix ComplementEn RC para sumar se suman como si fuera todo el nmero incluyendo el signo, unamagnitud Si X e Y son positivos entonces el Carryn=0. Se produce overflow si sn-1=1.Si X e Y son de distinto signo:

si Carryn=0 el resultado es correcto.si Carryn=1, se descarta el carry y el resultado es correcto.

Si X e Y son negativos entonces el Carryn=1, lo descartamos y el resultado es correcto.

6

En general se produce overflow si Carryn Carry n-1=1.

Las primeras computadoras usaban en su mayora aritmtica de punto fijo. Parapoder utilizar FXP en aplicaciones cientficas, cuando los nmeros se iban de rango (pormuy grandes o muy chicos), se los escalaba con software, firmware o hardware. En lamayora de los casos, los nmeros deban ser escalados hacia arriba o hacia abajo paraentrar en el intervalo de representacin, y al final del cmputo el resultado estransformado al dominio del usuario. Sin estas transformaciones, el hardware de puntofijo producira resultados sin sentido. Sin embargo, la introduccin de escalamientopuede crear eventuales prdidas de significancia.

La aritmtica de punto flotante se propuso para superar las dificultadesasociadas con la aritmtica de punto fijo. Para representar un nmero f en puntoflotante, se har por partes f=(m,e)=m*re, donde m y e son ambos nmerossignados en punto fijo, en una dada base r. Los dos componentes m y e se llamanmantisa y exponente respectivamente.

En general, la mantisa m puede asumir uno de los tres sistemas vistos para FXP,podr ser fraccionaria con punto a la izquierda o entera con punto a la derecha, la baser no aparece en la representacin ya que es implcita y el exponente e es un entero enRC que puede ser biased o unbiased. El exponente puede ser positivo o negativo, a lahora de operar, se debern comparar los exponentes, esto se facilita convirtiendolostodos a positivos al sumarles una constante positiva y creando un biased-exponent.

Muchos factores deben ser pesados en la eleccin de m, e y r, en particular, elrango de valores a acomodar y la precisin que se desea obtener. Dado que ambos, e ym, comparten una o ms palabras en la representacin, el dar ms espacio a unaacorta a la otra. Es decir, incrementar el rango dando ms dgitos al exponentedecrementara la longitud de la mantisa, disminuyendo luego la precisin. Decrementarlos bit del exponente conduce a lo opuesto.

El tercer parmetro, la base de representacin, impacta tanto en el rango comoen la precisin. Se puede ver a medida que la base aumenta (la base siempre serpotencia de dos), menos corrimientos por alineacin y normalizacin se requieren (noolvidar que bases muy grandes funcionaban mal, dado que no tienen mximasignificancia). La base deber ser potencia de dos, dado que la mantisa estar enbinario, as se podr flotar y variar la posicion del punto en funcin del exponente.

Las operaciones de punto flotante pueden dar lugar a situaciones singulares ancuando estas sean legtimas sobre datos legtimos. Se usaran los smbolos + y -para referirse a los positivos y negativos casi-infinitos correspondientes a nmeros FLPcuyo exponente excede el mximo valor positivo, es decir, valores demasiado grandes.Se usan tambin + y - para representar nmeros cuyo exponente excede el mximonegativo, es decir, valores demasiado pequeos. El bit menos significativo se losconoce como LSB. Se dar un Overflow del Exponente cuando el exponente resultanteexceda el lmite superior, tanto para mantisas positivas como negativas, dando lugar a+/-. Se dar un Underflow del Exponente cuando el exponente resultante exceda elmnimo valor permitido y caiga en el intervalo (-,0-) y (0+,+). Es de notar que elverdadero cero al origen de coordenadas es una excepcin.

Hay dos tipos de FLP no normalizados y normalizados. Un nmero FLP sedice normalizado si su dgito ms significativo en la mantisa no es cero. El valor de unamantisa normalizada variar en el rango 1/r|m|

Teora de redondeoEn muchos casos el resultado de una operacin entre nmeros mquina no ser

representable, es decir, no ser un nmero mquina, y deber ser sometido a unredondeo.

Al truncar, simplemente eliminamos los bits sobrantes, as el error mximo alque me enfrento es 1 LSB. Al redondear, eliminamos los bits sobrantes, pero ajustamosla parte ms significativa sumandole 1 LSB si el dgito ms significativo de la partesobrante es 1; de esta forma el error mximo al que me expongo es LSB.

El intervalo entre dos nmeros mquina, normalizados, adyacentes es be.2-m

donde e es el exponente y m es la cantidad de dgitos en la mantisa. Esto representa elerror absoluto. El error relativo de un nmero mquina m y un X ser (x-m)/x

Una descripcin algebraica ms rigurosa debe distinguir nmeros positivos ynegativos, a los efectos de normalizar los mtodos existentes. Habamos visto lafuncin de redondeo como :R->M definida para todo a,b R tal que se verifica(a)(b) toda vez que ab.

Se denomina redondeo optimal si para todo a M, (a)=a. En la prctica estoser as para cualquier representacin razonable. Un redondeo optimal implica que sia R y m1, m2 son dos nmeros consecutivos de M con m1