Tipo de aritmética informática
La representación de números con índice de nivel ( LI ) y sus algoritmos para operaciones aritméticas fueron introducidos por Charles Clenshaw y Frank Olver en 1984. [1]
Clenshaw y Peter Turner presentaron la forma simétrica del sistema LI y sus operaciones aritméticas en 1987. [2]
Michael Anuta, Daniel Lozier, Nicolas Schabanel y Turner desarrollaron el algoritmo para la aritmética de índice de nivel simétrico ( SLI ) y una implementación paralela del mismo. Se ha trabajado mucho en el desarrollo de algoritmos aritméticos SLI y su extensión a operaciones aritméticas complejas y vectoriales .
Definición
La idea del sistema de índice de niveles es representar un número real no negativo X como
![{\displaystyle X=e^{e^{e^{\cdots ^{e^{f}}}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde y el proceso de exponenciación se realiza ℓ veces, con . ℓ y f son el nivel y el índice de X respectivamente. x = ℓ + f es la imagen LI de X . Por ejemplo,![{\displaystyle 0\leqf<1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \ell \geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle X=1234567=e^{e^{e^{0.9711308}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
entonces su imagen LI es
![{\displaystyle x=\ell +f=3+0.9711308=3.9711308.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La forma simétrica se utiliza para permitir exponentes negativos, si la magnitud de X es menor que 1. Se toma sgn (log( X )) o sgn(| X | − | X | −1 ) y lo almacena (después de sustituir +1 para 0 para el signo recíproco ya que para X = 1 = e 0 la imagen LI es x = 1.0 y define de forma única X =1 y podemos prescindir de un tercer estado y usar solo un bit para los dos estados −1 y +1 [ se necesita aclaración ] ) como el signo recíproco r X. Matemáticamente, esto equivale a tomar el recíproco (inverso multiplicativo) de un número de magnitud pequeña y luego encontrar la imagen SLI para el recíproco. El uso de un bit como signo recíproco permite la representación de números extremadamente pequeños.
También se puede utilizar un bit de signo para permitir números negativos. Uno toma sgn (X) y lo almacena (después de sustituir +1 por 0 para el signo, ya que para X = 0 la imagen LI es x = 0.0 y define de forma única X = 0 y podemos prescindir de un tercer estado y usar solo uno bit para los dos estados −1 y +1 [ se necesita aclaración ] ) como el signo s X. Matemáticamente, esto equivale a tomar el inverso (inverso aditivo) de un número negativo y luego encontrar la imagen SLI para el inverso. El uso de un bit para el signo permite la representación de números negativos.
La función de mapeo se llama función logarítmica generalizada . Se define como
![{\displaystyle \psi (X)={\begin{casos}X&{\text{if }}0\leq X<1\\1+\psi (\ln X)&{\text{if }}X\ geq 1\end{casos}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y se asigna a sí mismo de forma monótona, por lo que es invertible en este intervalo. La inversa, la función exponencial generalizada , está definida por![{\displaystyle [0,\infty)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \varphi (x)={\begin{cases}x&{\text{if }}0\leq x<1\\e^{\varphi (x-1)}&{\text{if }} x\geq 1\end{casos}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La densidad de valores X representada por x no tiene discontinuidades a medida que pasamos del nivel ℓ al ℓ + 1 (propiedad muy deseable) ya que:
![{\displaystyle \left.{\frac {d\varphi (x)}{dx}}\right|_{x=1}=\left.{\frac {d\varphi (e^{x})}{ dx}}\right|_{x=0}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La función de logaritmo generalizado está estrechamente relacionada con el logaritmo iterado utilizado en el análisis de algoritmos en informática.
Formalmente, podemos definir la representación SLI para un X real arbitrario (no 0 o 1) como
![{\displaystyle X=s_{X}\varphi (x)^{r_{X}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
donde s X es el signo (inversión aditiva o no) de X y r X es el signo recíproco (inversión multiplicativa o no) como en las siguientes ecuaciones:
![{\displaystyle s_{X}=\operatorname {sgn}(X),\,r_{X}=\operatorname {sgn}(|X|-|X|^{-1}),\,x=\psi (\max(|X|,|X|^{-1}))=\psi (|X|^{r_{X}})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
mientras que para X = 0 o 1, tenemos:
![{\displaystyle s_{0}=+1,r_{0}=+1,x=0.0,\,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle s_{1}=+1,r_{1}=+1,x=1.0.\,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Por ejemplo,
![{\displaystyle X=-{\dfrac {1}{1234567}}=-e^{-e^{e^{0.9711308}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y su representación SLI es
![{\displaystyle x=-\varphi (3.9711308)^{-1}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ver también
Referencias
- ^ Clenshaw, Charles William; Olver, Frank William John (1984). "Más allá del punto flotante". Revista de la ACM . 31 (2): 319–328. doi : 10.1145/62.322429 .
- ^ Clenshaw, Charles William; Turner, Peter R. (1 de octubre de 1988) [16 de septiembre de 1986, 4 de junio de 1987]. "El sistema de índice de niveles simétrico". Revista IMA de Análisis Numérico . Oxford University Press , Instituto de Matemáticas y sus Aplicaciones. 8 (4): 517–526. doi :10.1093/imanum/8.4.517. ISSN 0272-4979. OCLC 42026743 . Consultado el 10 de julio de 2018 .
Otras lecturas
- Clenshaw, Charles William; Olver, Frank William John ; Turner, Peter R. (1989). "Aritmética de índices de niveles: una encuesta introductoria". Análisis numérico y procesamiento paralelo (actas de conferencias / Escuela de verano de análisis numérico de Lancaster 1987). Apuntes de conferencias de matemáticas (LNM). 1397 : 95-168. doi :10.1007/BFb0085718.
- Clenshaw, Charles William; Turner, Peter R. (23 de junio de 1989) [4 de octubre de 1988]. "Cuadratura de raíces mediante aritmética de índice de niveles". Informática . Springer-Verlag . 43 (2): 171–185. ISSN 0010-485X.
- Zehendner, Eberhard (verano de 2008). "Rechnerarithmetik: Logarithmische Zahlensysteme" (PDF) (guión de la conferencia) (en alemán). Universidad Friedrich Schiller de Jena . págs. 21-22. Archivado (PDF) desde el original el 9 de julio de 2018 . Consultado el 9 de julio de 2018 .[1]
- Hayes, Brian (septiembre-octubre de 2009). "La aritmética superior". Científico americano . 97 (5): 364–368. doi :10.1511/2009.80.364. Archivado desde el original el 9 de julio de 2018 . Consultado el 9 de julio de 2018 .[2]. También reimpreso en: Hayes, Brian (2017). "Capítulo 8: Aritmética superior". Infalibles y otras meditaciones matemáticas (1 ed.). La prensa del MIT . págs. 113-126. ISBN 978-0-26203686-3. ISBN 0-26203686-X .
enlaces externos
- sli-c-library (alojada por Google Code), "Implementación en C++ de aritmética de índice de nivel simétrico".