%% Modelo criado por R\'egis (c) 2011
%% http://latexbr.blogspot.com
%% twitter: @rg3915
%% Todos os caracteres foram convertidos para codigos TeX
%% para que possa ser lido em qualquer plataforma.
\documentclass[a4paper]{report} %padrao letterpaper, 10pt
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{amsfonts,amssymb,graphicx,enumerate}
\usepackage[centertags]{amsmath}
\usepackage{hyperref}
\usepackage{setspace}
\usepackage{fancyhdr}
\usepackage{indentfirst}
\usepackage{alltt}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{amsfonts}
\usepackage{color}
\usepackage{listings}
\usepackage{tipa}
% Configuracoes de pagina
\usepackage[lmargin=3cm,rmargin=3cm,tmargin=3cm,bmargin=3cm]{geometry}
% Layout da pagina
\usepackage{hyperref}
\hypersetup{pdfpagelayout=SinglePage, % ou TwoPageLeft
    colorlinks=true,
    pdftitle={Relat\'orio ep2 de MAC0438},
    pdfauthor={Andr\'e Spanguero Kanayama \& Renato Scaroni}}



% Ambiente para demonstracao que coloca quadrado no final, usando \rule
% Nota: \rule{largura}{altura} produz um retagulo preto.
\newenvironment{dem}[1][Demonstra\c c\~ao]{\textbf{#1:}\

}  {\hfill\rule{1ex}{1ex}}
%*******************************************************
% Definindo novos comandos
\providecommand{\sin}{} \renewcommand{\sin}{\hspace{2pt}\textrm{sen}}
\newcommand{\R}{\mathbb{R}} %simbolos de numeros reais
%*******************************************************
\title{Relat\'orio ep2 de MAC0438}
\author{Andr\'e Spanguero Kanayama \& Renato Scaroni}
\date{Maio de 2013}    %para ocultar a data digite: \date{ }
%**********1*********************************************
\begin{document}    %Inicio do documento
\maketitle  %cria o titulo na capa

\tableofcontents %Sumario
%-------------------------------------------------------
\chapter{O c\'alculo do pi}
\label{chap_primeiro} %rotulo que pode ser usado em referencia cruzada

\section{M\'etodo utilizado}
\label{sec_primeiro}

\indent O primeiro desafio deste exerc\'icio-programa \'e a escolha do m\'etodo adequado
para o c\'alculo do pi. O m\'etodo escolhido para o nosso trabalho foi o algoritmo de Chudnovsky.
Este algoritmo devolve o numero de pi como resultado de uma somat\'oria infinita dada pela f\'ormula
abaixo:
\\\\
%FORMULA FEIA E GIGANTE DO CHUDNOVSKY!!!! SKAVURSKA!!!
%\begin{math}
\begin{align*}
\frac{1}{\pi} = 12 \sum_{k=0}^{\infty} \frac{(-1)^k (6k)!(13591409+545140134k)}{(3k)!(k!)�640320^{3k+\frac{3}{2}}} 
\end{align*}
%\end{math}
\\\\
\indent Este m\'etodo foi o escolhido dentre os tantos existentes pelo fato de expressar pi como uma soma de
infinitos termos, o que facilita a paraleliza\c c\~ao do algoritmo. Outro motivo que nos levou a escolher este m\'etodo foi o fato
de se mostrar bem eficiente e razo\'avelmente preciso.

\chapter{Detalhes da implementa\c c\~ao}
\label{chap_segundo} %rotulo que pode ser usado em referencia cruzada
\section{Concep\c c\~ao do algoritmo}
\label{sec_segundo}
\indent A implementa\c c\~ao do c\'alculo do pi foi feito variando o valor de k na f\'ormula
apresentada no cap\'itulo anterior e somando o inverso desse fator numa vari\'avel que ao fim de cada 
iter\c c\~ao guardar\'a o valor de pi obtido at\'e o momento.
\\
\indent Ou seja, a cada itera\c c\~ao do algoritmo calcula-se uma parte do valor do pi que ser\'a acrescentada
ao valor obtido at\'e este ponto. O algoritmo executa esse loop at\'e que o valor a ser acrescentado ao \begin{math} \pi \end{math} nesse
passo seja menor que um \begin{math} \epsilon \end{math} dado como entrada pelo usu\'ario. Quando isso acontecer
o programa retornar\'a o valor total do \begin{math} \pi \end{math}.
\section{Paraleliza\c c\~ao do algoritmo}
\label{sec_terceiro}
\indent Uma vez tendo a id\'eia do algoritmo pronta, tivemos que pensar na paraleliza\c c\~ao do mesmo.
Para isso, tendo em mente as exig\^encias contidas no enunciado deste exerc\'icio-programa, implementamos da seguinte forma:
\\
\indent Primeiro declaramos um vetor com 16 posi\c c\~oes, dos quais ser\~ao usadas as N primeiras, onde N \'e o n\'umero
de n\'ucleos de processamento dispon\'iveis no processador. Em seguida, a cada itera\c c\~ao cada um dos N n\'ucleos calcula 
um fator da f\'ormula de chudnovsky com valores diferentes para k, de forma que a cada itera\c c\~ao s\~ao calculados N 
fatores, de k a k+N-1. No fim da itera\c c\~ao valor de k \'e incrementado em N.
\\
\indent Cada n\'ucleo deve calcular o fator de k m\'odulo N, ou seja, o n\'ucleo i deve calcular todos os fatores com 
\begin{math}
 k \equiv i (mod N)
\end{math} que devem ser calculados a cada itera\c c\~ao. Depois de calculado o fator correspondente, cada n\'ucleo, 
que executar\'a uma thread do programa, guardar\'a esse resultado em uma posi\c c\~ao do vetor acima citado. Isto \'e,
a thread de n\'umero j, com j entre 0 e N-1, dever\'a calcular o fator correspondente, de acordo com o crit\'erio acima e guardar
o resultado na posi\c c\~ao j do vetor.
\\
\indent Assim que cada thread calcula exatamente 1 fator da f\'ormula de chudnovsy, elas s\~ao travadas at\'e que todas tenham calculado.
Nesse momento o programa soma todas as N primairas posi\c c\~oes do vetor para descobrir o incremento dessa itera\c c\~ao. se este for menor
que o \begin{math}
       \epsilon
      \end{math}
passado pelo usu\'ario o programa termina, sen\~ao inicia uma nova itera\c c\~ao, liberando as threads para que calculem mais um fator cada.

\begin{thebibliography}{99}
\bibitem{Chudnovsky} Chudnovsky, David V.; Chudnovsky, Gregory V, "The Computation of Classical Constants", Proceedings of the National Academy of Sciences of the United States of America, 1989

\end{thebibliography}

\addcontentsline{toc}{chapter}{Refer\^encias Bibliogr\'aficas}

\end{document}  %Fim do documento