= Factoriales con Threads en Java
:author: Pepper Pots (A01166611), Anthony Stark (A01160611)
:lang: es
:email: A01166611@itesm.mx, A01160611@itesm.mx 
:encoding: utf-8

Este reporte fue elaborado para el curso de _Programación multinúcleo_ del Tecnológico de Monterrey, Campus Estado de México.  

:numbered:

== Introducción

Según <<Wolfram>>, el factorial de un número _N_ se define de manera iterativa como:

*****************************
_N_! = 1 &#215; 2  &#215; 3 &#215; ...  &#215; _N_ 
*****************************

En esta práctica se calculó el factorial de un número muy grande en Java  utilizando la clase +java.math.BigInteger+ (ver el API de Java en <<Oracle>>). El objetivo consistía en resolver este problema de manera secuencial y usando _threads_ de Java para obtener una solución paralela. 

[NOTE]
.Hardware y software utilizado
=============================
Los programas se probaron en una computadora de escritorio con un procesador de dos núcleos Intel Pentium D de 3.00GHz y 2.4 GiB de memoria RAM. El sistema operativo utilizado fue Ubuntu 12.04 con un kernel de Linux 3.2.0-58. Los programas se compilaron usando el compilador de Java 1.7.0_04 de Oracle.
=============================

== Solución secuencial

El siguiente listado muestra un programa completo en Java que calcula de forma secuencial el factorial de 100,000:

[source,java]
----------------------------
/*--------------------------------------------------------------------
 * Práctica 0: Factoriales en Java versión secuencial 
 * Fecha: 21-Ene-2014
 * Autores:
 *          1166611 Pepper Pots  
 *          1160611 Anthony Stark
 *--------------------------------------------------------------------*/

package mx.itesm.cem.pmultinucleo;

import java.math.BigInteger;

public class SequentialFactorial {

    public static void main(String[] args) throws InterruptedException {

        final int n = 100000;

        long timeStart = System.currentTimeMillis();
        BigInteger result = BigInteger.ONE;

        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }

        long timeEnd = System.currentTimeMillis();

        System.out.printf("Resultado = %d, Tiempo = %.4f%n", result.bitCount(),
                (timeEnd - timeStart) / 1000.0);
    }
}
----------------------------

Dado que el factorial de 100,000 es extremadamente grande para imprimirlo (más de cuatrocientos mil dígitos), se utilizó el método +bitCount+ para solo contar el número de bits igual a uno que tiene el valor binario del resultado.

Esta es la salida del programa:

[source,text]
----------------------------
Resultado = 708218, Tiempo = 34.0650
----------------------------

== Solución paralela

La solución paralela en Java involucra usar dos _threads_. El primer _thread_ se encarga de calcular la primera mitad de la multiplicaciones: 1 &#215; 2 &#215; 3 &#215; ... &#215; 50,000. El segundo _thread_ se encarga de calcular la otra mitad de las multiplicaciones: 50,001 &#215; 50,002 &#215; 50,003 &#215; ... &#215; 100,000. Una vez que terminan ambos _threads_, se multiplican los resultados de ambos para obtener el resultado final. El siguiente listado contiene el programa completo:

[source,java]
----------------------------
/*--------------------------------------------------------------------
 * Práctica 0: Factoriales en Java versión paralela con threads
 * Fecha: 21-Ene-2014
 * Autores:
 *          1166611 Pepper Pots  
 *          1160611 Anthony Stark
 *--------------------------------------------------------------------*/

package mx.itesm.cem.pmultinucleo;

import java.math.BigInteger;

public class ParallelFactorial implements Runnable {

    private int start, end;
    private BigInteger result = BigInteger.ONE;

    public ParallelFactorial(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {
        for (int i = start; i <= end; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
    }

    public static void main(String[] args) throws InterruptedException {
        final int n = 100000;
        
        long timeStart = System.currentTimeMillis();
        
        ParallelFactorial p1 = new ParallelFactorial(2, n / 2);
        ParallelFactorial p2 = new ParallelFactorial(n / 2 + 1, n);
        Thread t1 = new Thread(p1);
        Thread t2 = new Thread(p2);     
        t1.start();
        t2.start();
        t1.join();
        t2.join();      
        BigInteger total = p1.result.multiply(p2.result);
        
        long timeEnd = System.currentTimeMillis();
        
        System.out.printf("Resultado = %d, Tiempo = %.4f%n", total.bitCount(),
		        (timeEnd - timeStart) / 1000.0);        
    }
}
----------------------------

El programa produce esta salida:

[source,text]
----------------------------
Resultado = 708218, Tiempo = 12.9380
----------------------------

El _bit count_ es el mismo que en la versión secuencial, por lo que podemos suponer que nuestra versión paralela produce el resultado correcto. 

== Resultados

A continuación se muestran los tiempos de ejecución de varias corridas de los dos programas:

.Tiempos de ejecución del factorial secuencial 
[options="header,footer", cols="^,^", width="70%"]
|=======================
| # de corrida     | Tiempo T~1~ (segundos)
| 1                | 33.9440
| 2                | 34.2370
| 3                | 33.4740
| 4                | 33.4550
| 5                | 34.0650
| Media aritmética | 33.8350   
|=======================

.Tiempos de ejecución del factorial paralelo 
[options="header,footer", cols="^,^", width="70%"]
|=======================
| # de corrida     | Tiempo T~2~ (segundos)
| 1                | 13.1770 
| 2                | 12.8350
| 3                | 12.6560
| 4                | 13.3280
| 5                | 12.9380
| Media aritmética | 12.9868  
|=======================

A partir de las medias aritméticas calculadas, el _speedup_ obtenido con un CPU de dos núcleos es:

*****************************
S~2~ = T~1~ / T~2~ = 33.8350 / 12.9868 = 2.6053
*****************************

El _speedup_ obtenido es muy bueno, incluso superando al _speedup_ ideal. Sin embargo, no queda claro por qué ocurre esto.
       
== Agradecimientos

Se agradece a Steve Rogeres por sugerir usar LibreOffice Calc para calcular los promedios de los tiempos de ejecución.

== Referencias

[bibliography]

- [[[Oracle]]] Oracle Corporation. _Java Platform, Standard Edition 7 API Specification_ http://docs.oracle.com/javase/7/docs/api/ (Consultada el 21 de enero, 2014).

- [[[Wolfram]]] Wolfram MathWorld. _Factorial_ 
http://mathworld.wolfram.com/Factorial.html (Consultada el 21 de enero, 2014).