#LyX 1.6.7 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\use_default_options true
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author ""
\author ""
\end_header
\begin_body
\begin_layout Section
Desarrollo
\end_layout
\begin_layout Subsection
Artimética de precisión arbitraria
\end_layout
\begin_layout Standard
Para realizar los experimentos se observó que es necesario contar con una
aritmética de precisión arbitraria con las operaciones de suma, resta multiplic
ación y división.
\end_layout
\begin_layout Standard
Primero se pensó en hacer una clase que represente números de punto flotante,
a la cual se le pueda fijar la presicion de manera dinámica.
Para realizar las operaciones de la misma, se evaluó la posibilidad de
implementar
\begin_inset Quotes eld
\end_inset
manualmente
\begin_inset Quotes erd
\end_inset
dichas operaciones.
\end_layout
\begin_layout Standard
Luego se optó por un enfoque más simple: representar internamente el número
con un double (
\emph on
IEEE 754 binary64
\emph default
).
De esta forma, ya que el objetivo es lograr que la precisión sea t < 52,
y sabiendo que un double tiene 52 bits en la mantisa (lo que define la
presicion), el mismo alcanza para representar cualquier numero con presicion
t.
Lo que nos permite realizar las operaciones de suma, resta, multiplicación
y división utilizando como base las provistas por el procesador.
\end_layout
\begin_layout Standard
Otro aspecto relevante es la cantidad de bits del exponente, es decir, cuántos
bits asignarle.
Luego de discutir el tema y considerar que el exponente sólo define el
alcance de la representación (cuál será el mayor y el menor numero representabl
e), se optó por utilizar la misma cantidad de bits para el exponente que
la que se utiliza para representar un double.
De esta forma solo tendremos que ocuparnos de la mantisa de dicha representació
n.
Cabe mencionar que para esta decisión se tomo en consideración que las
operaciónes aritméticas a realizar son todas con el fín de calcular
\begin_inset Formula $\sqrt{2}$
\end_inset
.
\end_layout
\begin_layout Standard
La aritmética finalmente funciona de la siguiente manera:
\end_layout
\begin_layout Standard
Cuando se genera un numero con presicion t, lo que se hacer es guardar intername
nte el mismo como un double, pero se le quita presicion hasta llegar a la
presicion t buscada.
\end_layout
\begin_layout Standard
Luego, para realizar alguna operacion, se toman los dos operandos (ya con
la presicion correcta) y se opera utilizano los doubles de la representacion
interna.
Una vez obtenido este resultado se genera nuevamente un numero con presicion
t a partir de este.
\end_layout
\begin_layout Subsubsection
Métodos de aproximación de la mantisa
\end_layout
\begin_layout Standard
Para adecuar la precisión de un número a la presición t buscada, se implementaro
n dos métodos: truncamiento y redondeo.
\end_layout
\begin_layout Standard
El primero consiste en poner en cero todos los bits de la mantisa que estén
en posiciones mayores a t.
Para esto se utilizó una máscara de bits y se realizó un and lógico (de
bits) sobre los bits de la mantisa y la máscara.
\end_layout
\begin_layout Standard
Para implementar el método de redondeo es necesario considerar el bit de
la posición t+1 de la mantisa.
Lo que se traduce en sumarle al numero original el valor que representa
ese bit para luego truncar el resulado a precisión t.
Para realizar esto se realiza un truncamiento del numero a presicion
\begin_inset Formula $t+1$
\end_inset
y otro con presicion
\begin_inset Formula $t$
\end_inset
, al restar estos dos numeros se obtiene el numero que representa el bit
\begin_inset Formula $t+1$
\end_inset
.
Por ultimo se suma al numero original este valor y se lo trunca a presicion
\begin_inset Formula $t$
\end_inset
, como se explicó anteriormente.
\end_layout
\begin_layout Subsection
Método binomial
\end_layout
\begin_layout Standard
Para este método se realizaron distintas implementaciones teniendo en cuenta
ciertas particularidades que se notaron de la fórmula:
\end_layout
\begin_layout Itemize
que el numerador y denominador de cada término es un producto
\end_layout
\begin_layout Itemize
que cada término es igual al anterior multiplicado por una constante que
depende de la iteración actual
\end_layout
\begin_layout Itemize
que la fórmula se puede expresar como una sumatoria
\end_layout
\begin_layout Standard
La primera implementación,
\emph on
binomial simple
\emph default
, calcula para cada término el numerador y el denominador y, luego, el resultado
de la division.
Mediante este proceso se calculan todos los terminos (hasta cierto n variable).
Y a medida que se genera cada término, se lo suma en una variable que finalment
e tendrá el resultado buscado.
\end_layout
\begin_layout Standard
La segunda implementación,
\emph on
binomial incremental
\emph default
, consta en dividir cada termino en productos de fracciones, esto es posible
gracias a que:
\end_layout
\begin_layout Standard
\begin_inset Formula \[
(1+x)^{n}=1+n\, x+\frac{n\,(n-1)}{2!}x^{2}+\frac{n\,(n-1)\,(n-2)}{3!}x^{3}+\dots\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \[
{\displaystyle (1+x)^{n}=1+{\displaystyle \sum_{i=0}^{\infty}a_{i}}}\]
\end_inset
Con,
\begin_inset Formula $a_{i}={\displaystyle \prod_{j=0}^{i}b_{j}}$
\end_inset
y
\begin_inset Formula $b_{j}=\frac{n-j}{j+1}$
\end_inset
.
\end_layout
\begin_layout Standard
Se puede ver tambien que
\begin_inset Formula $a_{i+1}=a_{i}.b_{i+1}$
\end_inset
.
Sabiendo esto, lo que se hizo en cada paso fue, en vez de recalcular todo
el termino se utiliza el termino anterior y a partir de este (multiplicando
por el valor de
\begin_inset Formula $b_{j}$
\end_inset
) se obtiene el termino siguiente.
\end_layout
\begin_layout Standard
La tercera y ultima implementacion,
\emph on
binomial decremetal
\emph default
, usa la propiedad conmutativa de la suma, ya que suma los terminos en el
orden inverso.
Con este fin se calcularon los terminos de manera similar a la implementacion
anterior, pero en vez de sumarlos, se los guarda en una lista.
Finalmente se recorre la lista de atras haca adelante realizando, ahora
sí, la sumatoria de los terminos.
\end_layout
\begin_layout Subsection
Método de las fracciones continuas
\end_layout
\begin_layout Standard
La primera implementacion planteada para este metodo consiste en realizar
el calculo de la fraccion partiendo desde la más interior hasta llegar
a la exterior.
La implementacion, de este modo, no tiene mayores complicaciones.
\end_layout
\begin_layout Standard
Otro enfoque que se usó fué el de no realizar las divisiones de las fracciones
hasta la última iteración, esto es más sencillo de ver de la siguiente
manera:
\begin_inset Formula \[
\sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\dots}}}\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \[
\sqrt{2}=1+\underset{n\rightarrow\infty}{lim}a_{n}\]
\end_inset
\end_layout
\begin_layout Standard
Siendo:
\end_layout
\begin_layout Standard
\begin_inset Formula \[
\begin{cases}
a_{1}=\frac{1}{2}\\
a_{i+1}=\frac{1}{2+a_{i}}\end{cases}\]
\end_inset
\end_layout
\begin_layout Standard
A partir de esto, si se considera:
\begin_inset Formula $a_{i}=\frac{b_{i}}{c_{i}}$
\end_inset
, se obtiene:
\end_layout
\begin_layout Standard
\begin_inset Formula \[
a_{i+1}=\frac{1}{2+a_{i}}=\frac{1}{2+\frac{b_{i}}{c_{i}}}=\frac{1}{\frac{2c_{i}+b_{i}}{c_{i}}}=\frac{c_{i}}{2c_{i}+b_{i}}=\frac{b_{i+1}}{c_{i+1}}\]
\end_inset
\end_layout
\begin_layout Standard
Finalmente se obtiene:
\end_layout
\begin_layout Standard
\begin_inset Formula \[
\sqrt{2}=1+{\displaystyle \underset{n\rightarrow\infty}{lim}}\frac{b_{n}}{c_{n}}\]
\end_inset
\end_layout
\begin_layout Standard
Con:
\end_layout
\begin_layout Standard
\begin_inset Formula \[
\begin{cases}
b_{1}=1\\
b_{i+1}=c_{i}\end{cases}\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula \[
\begin{cases}
c_{1}=2\\
c_{i+1}=2c_{i}+b_{i}\end{cases}\]
\end_inset
\end_layout
\begin_layout Standard
Utilizando esto es posible no realizar ninguna division hasta la ultima
iteración.
\end_layout
\begin_layout Subsection
Metodo Babilonio
\end_layout
\begin_layout Standard
Para este método sólo se realizó una implementación, la misma es una traduccion
bastante literal de la formula que el método presenta.
La aproximacion inicial
\emph on
A
\emph default
se fijó como
\begin_inset Formula $2$
\end_inset
, pero se estableció también como parámetro opcional de entrada.
De esta forma es posible ver cómo el mismo varía según el
\emph on
A
\emph default
elegido.
\end_layout
\end_body
\end_document