tps/1/informe/informe.tex (18826B)
1 \documentclass[12pt]{article} 2 \usepackage[spanish]{babel} 3 \usepackage{natbib} 4 \usepackage{url} 5 \usepackage[utf8]{inputenc} 6 \usepackage{amsmath} 7 \usepackage{graphicx} 8 \usepackage{parskip} 9 \usepackage{fancyhdr} 10 \usepackage{vmargin} 11 \usepackage[ddmmyy]{datetime} 12 \usepackage{anyfontsize} 13 \usepackage{helvet} 14 \renewcommand{\familydefault}{phv} 15 \usepackage{xcolor} 16 \usepackage[T1]{fontenc} 17 18 % \setmarginsrb{leftmargin}{topmargin}{rightmargin}{bottommargin}% 19 % {headheight}{headsep}{footheight}{footskip} 20 \setmarginsrb{2.5 cm}{2.25 cm}{2.5 cm}{1.50 cm} 21 {1 cm}{1.25 cm}{1 cm}{1.50 cm} 22 23 \usepackage{color} 24 \usepackage{hyperref} 25 \hypersetup{ 26 colorlinks=true, % set true if you want colored links 27 linktoc=all, % set to all if you want sections and subsections linked 28 linkcolor=blue, % choose some color if you want links to stand out 29 urlcolor=blue, 30 } 31 32 \usepackage{subfig} 33 \usepackage[labelformat=empty]{caption} 34 35 \usepackage{fancyvrb} 36 \fvset{xleftmargin=\mathindent} 37 38 % code blocks 39 \usepackage{verbatimbox} 40 \newenvironment{fullgrayverb} 41 {\verbbox} 42 {\endverbbox\par\colorbox{gray!25}{\parbox{\textwidth}{\theverbbox}}\par} 43 44 % inline code blocks 45 \usepackage{tcolorbox} 46 \newcommand\mystrut{\rule[-3pt]{0pt}{12pt}} 47 \newtcbox{\code}{on line, boxrule=0pt, boxsep=0pt, top=0pt, 48 left=0pt, bottom=0pt, right=0pt, colback=gray!25, colframe=white, 49 fontupper={\ttfamily\mystrut}} 50 51 \title{Números Primos} % Titulo del trabajo. 52 \author{Martin J. Klöckner} % Nombre y apellido 53 \newcommand{\padron}{123456} % Padrón 54 \newcommand{\tpnumber}{1} % Número de trabajo práctico 55 \date{\today} % Fecha (automática) 56 57 \makeatletter 58 \let\thetitle\@title 59 \let\theauthor\@author 60 \let\thedate\@date 61 \makeatother 62 63 \pagestyle{fancy} 64 \fancyhf{} 65 \rhead{\theauthor} 66 \lhead{\thetitle} 67 \cfoot{\thepage} 68 69 \begin{document} 70 \begin{titlepage} 71 \vspace*{-2.5cm} 72 {\centering 73 \includegraphics[width=1.00\textwidth]{img/logofiuba.png}\\[2.25 cm]} 74 \centering 75 \textsc{\Large CB100}\\[0.2 cm] 76 \textsc{\large Algoritmos y Estructuras de Datos}\\[4 cm] 77 \textcolor{cyan}{{\fontsize{40}{60}\selectfont \bfseries \thetitle}}\\[0.5cm] 78 {\Large \bfseries Trabajo Práctico N$^\circ$\tpnumber}\\[5cm] 79 80 81 \vfill 82 \noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}\\[0.5cm] 83 \begin{minipage}{.46\textwidth} 84 \textbf{Autor}\\ 85 \theauthor 86 \end{minipage}% 87 \begin{minipage}{.34\textwidth} 88 \textbf{Legajo}\\ 89 \padron 90 \end{minipage}% 91 \begin{minipage}{.2\textwidth} 92 \begin{flushright} 93 \textbf{Fecha}\\ 94 \thedate 95 \end{flushright} 96 \end{minipage} 97 \end{titlepage} 98 99 { 100 \hypersetup{linkcolor=black} % colorlinks=true option is used 101 \tableofcontents 102 \pagebreak 103 } 104 105 \section{Introducción} 106 107 En este trabajo práctico se desarrolla una aplicación de consola que busca 108 números primos hasta un valor máximo determinado por el usuario, cuando 109 finaliza, los imprime en un archivo de texto plano en el directorio de ejecución 110 de la aplicación. 111 112 El lenguaje de programación utilizado para el desarrollo de la aplicación es C++ 113 y el algoritmo utilizado para hallar los números primos es la Criba de 114 Eratóstenes. 115 116 \subsection{Números Primos} 117 118 Los números primos por definición son aquellos números positivos que solo son 119 divisibles por \code{1} y por si mismos, divisibles en términos de que el resto 120 de la división es nulo. El \code{0} y el \code{1} son dos casos particulares en 121 los cuales ambos son considerados no primos, el \code{0} por razones obvias, no 122 está definida la división por \code{0}, y el \code{1} por que solo es divisible 123 por si mismo, lo cual hace que solo sea divisible por un número. 124 125 El número \code{7}, por ejemplo, es un número primo, ya que solo es divisible 126 por \code{1} y por \code{7}. El número \code{8} no es un número primo, ya que 127 ademas de ser divisible por si mismo y por \code{1}, es divisible por \code{2} y 128 por \code{4}. 129 130 \subsection{Criba de Eratóstenes} 131 132 La criba de Eratóstenes es un algoritmo sofisticado y eficiente para descartar 133 números no primos de una lista de números. En la Criba de Eratóstenes se itera 134 número a número sobre una lista ordenada y finita de números naturales, 135 comenzando por el primero, si se trata de un número primo, se buscan todos los 136 múltiplos en la lista de números y se descartan, luego se avanza al siguiente 137 número que no haya sido descartado, el cual siempre resulta un número primo, y 138 se descartan sus múltiplos, así sucesivamente hasta el final de la lista. 139 140 La criba de Eratóstenes se puede optimizar basándose en la propiedad de que los 141 números no primos (números compuestos), se pueden expresar como el producto de 142 números primos, por ejemplo \code{4 = 2*2} o \code{21 = 3*7}, por lo tanto, si 143 un número no es primo, debe tener al menos un factor primo que sea menor o igual 144 que su raíz cuadrada, ya que de lo contrario, el producto de los factores 145 resultaría en un numero mayor. 146 147 De la propiedad anterior se deduce que se puede detener la iteración en la lista 148 de números cuando se llega a la raíz cuadrado del numero máximo en la lista, ya 149 que los números no primos por encima de éste tendrán algún factor menor que la 150 raíz cuadrada del numero máximo, de este modo se reduce drásticamente el numero 151 de iteraciones necesarias para descartar los números no primos de la lista. 152 153 \section{Desarrollo} 154 155 Para la implementación de la aplicación, como bien se mencionó en la 156 introducción, se utilizó puramente el lenguaje C++, en particular en su versión 157 estándar C98. Para organizar el proceso de compilación se utilizó la herramienta 158 \code{make}. 159 160 \subsection{Implementación en C++} 161 162 El código fuente de la aplicación esta contenido en un solo archivo: 163 \code{primos.cpp}. 164 165 En la primera parte del archivo se definen dos constantes globales 166 \code{OUTPUT\_FILE\_PATH}, que representa el nombre del archivo de salida, y 167 \code{MAXIMO} que representa el largo de la lista de números a analizar. 168 169 \begin{fullgrayverb}[\mbox{}] 170 #define OUTPUT_FILE_PATH "primos.txt" 171 const unsigned int MAXIMO = 100000000; 172 \end{fullgrayverb} 173 174 Luego se declara la función \code{vectorDiscardNonPrimes}, esta función asigna 175 el valor \code{false} a los casilleros del vector, que recibe como argumento, en 176 los cuales el índice es un numero no primo. 177 178 \begin{fullgrayverb}[\mbox{}] 179 // Se declara la función `vectorDiscardNonPrimes` 180 void vectorDiscardNonPrimes(std::vector<bool> &v); 181 \end{fullgrayverb} 182 183 Se declara la función \code{vectorPrintToOpenFile} la cual recibe como 184 argumento un vector, un archivo abierto y una referencia a una variable. Esta 185 función imprime sobre el archivo las posiciones del vector en donde el 186 contenido es \code{true}, la cantidad de números impresos los asigna a la 187 variable \code{primesWritten}. 188 189 \begin{fullgrayverb}[\mbox{}] 190 // Se declara la función `vectorPrintToOpenFile` 191 void vectorPrintToOpenFile( 192 const std::vector<bool> v, 193 std::ofstream &outputFile, 194 unsigned int &primesWritten); 195 \end{fullgrayverb} 196 197 \subsubsection{Función \code{main}} 198 199 La Criba de Eratóstenes opera sobre una lista de números naturales ordenada, 200 para representarla se utiliza la librería estándar \code{vector}, de la cual 201 se define un vector de tipo \code{bool} inicialmente con valores \code{true} 202 indicando que son todos números primos. 203 204 \begin{fullgrayverb}[\mbox{}] 205 // Se define un vector de tipo `bool` de largo `MAXIMO` 206 // con valores iniciales `true` 207 std::vector<bool> numeros(MAXIMO, true); 208 \end{fullgrayverb} 209 210 \pagebreak 211 Para la manipulación del archivo de salida, se utiliza la clase \code{ofstream} 212 de la librería estándar \code{fstream}. 213 214 \begin{fullgrayverb}[\mbox{}] 215 // Se define el objeto `outputFile` para representar el archivo de salida 216 std::ofstream outputFile; 217 \end{fullgrayverb} 218 219 Además se define la variable \code{primesFound} la cual luego contendrá la 220 cantidad de números primos hallados. 221 222 \begin{fullgrayverb}[\mbox{}] 223 unsigned int primesFound; 224 \end{fullgrayverb} 225 226 Para descartar los números no primos del vector \code{numeros} se invoca a la 227 función \linebreak\code{vectorDiscardNonPrimes}. 228 229 \begin{fullgrayverb}[\mbox{}] 230 vectorDiscardNonPrimes(numeros); 231 \end{fullgrayverb} 232 233 Luego de finalizada la función, se imprime en el archivo de salida los índices 234 del vector correspondientes a los casilleros que permanecen con un valor 235 \code{true}, ya que éstos representan los números primos. 236 237 Utilizando los métodos \code{open} e \code{is\_open} del objeto 238 \code{outputFile} se abre el archivo \code{primos.txt} y se comprueba si hubo 239 algún error, en caso afirmativo, se informa al usuario haciendo uso de métodos 240 de la librería estándar \code{iostream} y se termina la ejecución inmediatamente 241 con un código de error \code{-1}. 242 243 \begin{fullgrayverb}[\mbox{}] 244 outputFile.open(OUTPUT_FILE_PATH); 245 if (outputFile.is_open() == false) { 246 std::cerr << "ERROR: No se pudo abrir `" OUTPUT_FILE_PATH "`\n"; 247 return -1; 248 } 249 \end{fullgrayverb} 250 251 Para exportar los números primos del vector se invoca a la función 252 \linebreak\code{vectorPrintToOpenFile} 253 254 \begin{fullgrayverb}[\mbox{}] 255 vectorPrintToOpenFile(numeros, outputFile, primesFound); 256 \end{fullgrayverb} 257 258 Luego de finalizada la impresión en el archivo, se cierra utilizando el método 259 \code{close}. 260 261 \begin{fullgrayverb}[\mbox{}] 262 outputFile.close(); 263 \end{fullgrayverb} 264 265 Finalmente se imprime un mensaje al usuario indicando que terminó la impresión, 266 y se informa la cantidad de números primos hallados, esto se hace utilizando 267 métodos de la librería estándar \code{iostream}. 268 269 \begin{fullgrayverb}[\mbox{}] 270 std::cout << "Se encontraron `" << primesFound << "` números primos\n"; 271 \end{fullgrayverb} 272 273 Por ultimo se termina la ejecución con un código \code{0} indicando que el 274 programa se ejecutó exitosamente. 275 276 \begin{fullgrayverb}[\mbox{}] 277 return 0; 278 \end{fullgrayverb} 279 280 \subsubsection{Función \code{vectorDiscardNonPrimes}} 281 282 La función \code{vectorDiscardNonPrimes} recibe una referencia a un vector de 283 tipo \code{bool} como argumento y asigna \code{false} a los casilleros en los 284 cuales el índice del mismo es un número no primo. 285 286 La función comienza descartando los casos particulares, \code{0} y \code{1}, por 287 lo que asigna \code{false} a los índices respectivos directamente. 288 289 \begin{fullgrayverb}[\mbox{}] 290 // 0 y 1 no son primos 291 vector[0] = vector[1] = false; 292 \end{fullgrayverb} 293 294 Luego itera sobre el vector asignando \code{false} a todos los múltiplos de los 295 números primos, hasta llegar a la raíz cuadrada del numero máximo de la lista, o 296 lo que es equivalente, hasta que el indice al cuadrado sea menor al numero 297 máximo. 298 299 \begin{fullgrayverb}[\mbox{}] 300 for (size_t i = 2; i*i < MAXIMO; ++i) { 301 if(vector[i] == true) { 302 for (size_t j = i; j <= (MAXIMO/i); ++j) { 303 vector[i*j] = false; 304 } 305 } 306 } 307 \end{fullgrayverb} 308 309 \subsubsection{Función \code{vectorPrintToOpenFile}} 310 311 La función \code{vectorPrintToOpenFile} recibe como argumento un vector, una 312 archivo abierto y una referencia a una variable. Luego de invocada la función 313 imprime sobre el archivo los índices del vector en los cuales el contenido es 314 \code{true}, a la variable que recibe le asigna la cantidad de índices impresos. 315 316 Al comienzo de la función se asigna a la variable \code{primesWritten} cero. 317 318 \begin{fullgrayverb}[\mbox{}] 319 primesWritten = 0; 320 \end{fullgrayverb} 321 322 Para la impresión en el archivo, la función recorre el vector en búsqueda de 323 aquellos casilleros que contengan \code{true}, en los casos afirmativos imprime 324 el índice del vector al archivo e incrementa el contenido de la variable 325 \code{primesWritten}, los casilleros que contienen \code{false} son ignorados. 326 327 \begin{fullgrayverb}[\mbox{}] 328 for (size_t i = 2; i < vector.size(); ++i) { 329 if(vector[i] == true) { 330 outputFile << i << std::endl; 331 primesWritten++; 332 } 333 } 334 \end{fullgrayverb} 335 336 \subsection{Makefile} 337 338 Para organizar el proceso de compilación de la aplicación se utiliza la 339 herramienta \code{GNU make}, la cual lee un archivo de nombre exclusivo 340 \code{Makefile} que posee su propia sintaxis. 341 342 El archivo \code{Makefile} utilizado intenta ser reutilizable y de fácil 343 modificación, es por esto que al comienzo del mismo se utilizan variables para 344 almacenar las principales opciones que el usuario podría querer modificar, por 345 ejemplo el nombre del compilador utilizado, el nombre final del archivo, entre 346 otras. 347 348 \begin{fullgrayverb}[\mbox{}] 349 CC := g++ 350 CFLAGS := -Wall -Wshadow -pedantic -ansi -std=c++98 -O3 351 SRCS := $(wildcard *.cpp) 352 OBJS := $(SRCS:.cpp=.o) 353 TARGET := primos 354 \end{fullgrayverb} 355 356 Para compilar el programa y enlazar cabeceras, en caso de que haya, se utilizan 357 las siguientes reglas: 358 359 \begin{fullgrayverb}[\mbox{}] 360 $(TARGET): $(OBJS) 361 $(CC) $(CFLAGS) -o $@ $^ 362 363 %.o: %.cpp 364 $(CC) $(CFLAGS) -c $< -o $@ 365 \end{fullgrayverb} 366 367 La regla que contiene \code{\$(TARGET)} se expande al nombre final de la 368 aplicación, luego de los dos puntos se indican las dependencias, las cuales se 369 expanden a los archivos objeto (los que terminan en \code{.o}) 370 371 Para compilar los archivos objetos se utiliza la segunda regla, la cual 372 corresponde a una \code{pattern rule}, una extensión exclusiva de \code{GNU}, 373 esta \code{pattern rule} compila todos los archivos terminados en \code{.cpp} a 374 archivos objeto terminados en \code{.o}. 375 376 \subsection{Optimizaciones del Compilador} 377 378 La mayoría de los compiladores de C++ modernos proporcionan una opción para 379 activar optimizaciones. Al utilizar estas optimizaciones el compilador 380 intenta eliminar código redundante y optimizar mediante técnicas avanzadas el 381 archivo binario final, de este modo se logra reducir el uso de memoria, el 382 tiempo de ejecución y por consiguiente el consumo de energía, entre otras cosas. 383 384 En el archivo \code{Makefile} de la aplicación por defecto se utiliza el máximo 385 de optimizaciones posibles \code{-O3}, de ésta manera se obtiene un archivo 386 binario superior en rendimiento que el que se obtendría con las optimizaciones 387 desactivadas. 388 389 \subsubsection{Tiempo de Ejecución} 390 391 En el siguiente bloque se muestra la salida del programa utilizando el máximo de 392 optimizaciones posible del compilador \code{-O3}, se puede apreciar en la salida 393 del programa el tiempo de ejecución del mismo. 394 395 \begin{fullgrayverb} 396 Se encontraron `5761455` números primos en `11.36` segundos 397 \end{fullgrayverb} 398 399 Desactivando las optimizaciones del compilador, compilando y ejecutando 400 nuevamente la aplicación, se obtiene el siguiente mensaje en la consola: 401 402 \begin{fullgrayverb} 403 Se encontraron `5761455` números primos en `46.21` segundos 404 \end{fullgrayverb} 405 406 Comparando los dos resultados, se puede observar que al utilizar las 407 optimizaciones de compilador el tiempo de ejecución se reduce en 408 aproximadamente \code{75\%}. 409 410 \section{Instalación} 411 412 Para instalar la aplicación usted debe de disponer de una copia del código 413 fuente, si no posee una, puede obtenerla ingresando al 414 \href{https://github.com/mjkloeckner/CB100}{Repositorio de Github}, de allí 415 podrá descargar una copia, o bien puede clonar el repositorio utilizando 416 \code{git} con el siguiente comando: 417 418 \begin{fullgrayverb} 419 $ git clone https://github.com/mjkloeckner/CB100.git 420 \end{fullgrayverb}$ 421 422 Tenga en cuenta que si clona el Repositorio, o lo descarga del repositorio de 423 Github, tendrá que navegar al directorio \code{tps/1} 424 425 \subsection{Sistemas basados en UNIX} 426 427 Compruebe que este en el mismo directorio que el archivo \code{primos.cpp}. Luego, 428 compile el código con el programa \code{make} 429 430 \begin{fullgrayverb} 431 $ make 432 \end{fullgrayverb}$ 433 434 Luego puede ejecutar la aplicación de la siguiente manera: 435 436 \begin{fullgrayverb} 437 $ ./primos 438 \end{fullgrayverb}$ 439 440 \pagebreak 441 \subsection{Windows} 442 443 En el caso de utilizar Windows como sistema operativo, usted puede configurar 444 \href{https://en.wikipedia.org/wiki/Windows_Subsystem_for_Linux}{WSL}, el cual 445 virtualiza un sistema basado en UNIX, para hacerlo puede seguir la 446 \href{https://learn.microsoft.com/en-us/windows/wsl/install}{guia oficial de 447 Microsoft}. Una vez configurado WSL siga los pasos para los sistemas basados en 448 UNIX 449 450 De manera análoga si usted dispone de un compilador de C++ puede compilar la 451 aplicación directamente desde la consola, sin la necesidad de utilizar la 452 herramienta \code{make}, para eso ejecute el siguiente comando: 453 454 \begin{fullgrayverb} 455 $ g++ -Wall -Wshadow -ansi -std=c++98 -O3 primos.cpp -o primos 456 \end{fullgrayverb}$ 457 458 Tenga en cuenta la sintaxis de su compilador ya que puede variar, el comando 459 anterior está previsto para \href{https://www.mingw-w64.org/}{MinGW-w64} 460 461 Luego de compilado la aplicación usted la puede ejecutar de la siguiente manera 462 463 \begin{fullgrayverb} 464 $ ./primos 465 \end{fullgrayverb}$ 466 467 \section{Conclusión} 468 469 Luego de finalizar el desarrollo de la aplicación, se puede concluir que la 470 combinación de C++ con \code{GNU Make}, resulta muy versátil, y en este caso en 471 un alto rendimiento. 472 473 El lenguaje C++ es uno de los lenguajes de mayor rendimiento en la lista de 474 lenguajes de programación de alto nivel actuales, junto con C, aunque a 475 diferencia de éste, C++ ofrece una amplia variedad de librerías estándar, lo que 476 mejora su robustez y permite al usuario abstraerse de ciertas implementaciones 477 que resultan irrelevantes en ciertos casos, por ejemplo, en el desarrollo de 478 esta aplicación, el objecto \code{vector} utilizado para representar la lista de 479 números naturales. De no existir la librería estándar \code{vector} uno tendría 480 que ensuciarse las manos e implementar un tipo de dato para representar los 481 números naturales, ya que no alcanza con los tipos de datos primitivos ofrecidos 482 por el lenguaje. 483 484 Ademas de ahorrar tiempo al programador, las librerías estándar ofrecen mayor 485 seguridad que si se tratase de un tipo de dato creado por el usuario, ya que las 486 principales están respaldadas por organizaciones y grupos de estándares como 487 ISO, IEC, entre otros. 488 489 \pagebreak 490 \section{Referencias} 491 492 \begin{itemize} 493 \item Deitel H., Deitel P. - C how to Program: With an Introduction to C++ 494 (2015) 495 \item 496 \href{https://github.com/mjkloeckner/CB100}{Repositorio de Github} 497 \item 498 \href{https://en.cppreference.com/w/}{C++ Reference} 499 \item 500 \href{https://cplusplus.com/reference/}{Standard C++ Library reference} 501 \item 502 \href{https://en.cppreference.com/w/cpp/container/vector_bool}{ 503 std::vector\textless bool\textgreater} 504 \item 505 \href{https://cplusplus.com/reference/fstream/ofstream/}{std::ofstream} 506 \item 507 \href{https://www.mingw-w64.org/}{MinGW-w64} 508 \item 509 \href{https://www.gnu.org/software/make/manual/html_node/index.html}{GNU 510 Make Manual} 511 \end{itemize} 512 513 \end{document} 514