Ir para o conteúdo

Factoriais

Programa para calcular factoriais com múltiplas threads (usa programação dinâmica).

Compilar com gcc -lpthread -lgmp -o fac fac.c

fac.c:

/*
 *  GPL
 *
 *  fac - Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <gmp.h>
#include <assert.h> 
#include <stdbool.h>
#include <string.h>

#define N_THREADS 10
#define N_FAC 50000

struct thread_arg
{
    int start;
    int end;
};

mpz_t *result;
pthread_mutex_t *mutex_result;

bool is_computed(int n)
{
    bool r;

    pthread_mutex_lock(&mutex_result[n-1]);
    r=mpz_cmp_ui(result[n-1],0);
    pthread_mutex_unlock(&mutex_result[n-1]);

    return r;
}

/* Return the nearest smaller *index* of computed factorial
 */
int get_nearest_computed(int n)
{
    int i;

    for (i=n-1; i >= 0; i--)
        if (is_computed(i))
            return i-1;

    return -1;
}

void compute_fac(int n)
{
    mpz_t r;
    int nearest_computed;
    int i;

    if (n == 1)
        return;

    mpz_init(r);

    nearest_computed=get_nearest_computed(n);

    assert(nearest_computed >= 0);

    pthread_mutex_lock(&mutex_result[nearest_computed]);
    mpz_set(r,result[nearest_computed]);
    pthread_mutex_unlock(&mutex_result[nearest_computed]);

    for (i=nearest_computed+2; i <= n; i++)
    {
        mpz_mul_ui(r,r,i);

        if (!is_computed(i))
        {
            pthread_mutex_lock(&mutex_result[n-1]);
            mpz_set(result[n-1],r);
            pthread_mutex_unlock(&mutex_result[n-1]);
        }
    }

    mpz_clear(r);
}

void *thread_init(void *data)
{
    struct thread_arg *arg=data;    
    int i;

    for (i=arg->start; i <= arg->end; i++)
        compute_fac(i);

    return NULL;
}

int main(void)
{
    int i;
    pthread_t *threads;
    struct thread_arg *th_arg;

    assert(!(N_FAC%N_THREADS));

    threads=malloc(sizeof(*threads)*N_THREADS);
    if (threads == NULL)
        return -1;

    th_arg=malloc(sizeof(*th_arg)*N_THREADS);
    if (th_arg == NULL)
        return -1;

    result=malloc(sizeof(*result)*N_FAC);
    if (result == NULL)
        return -1;

    mutex_result=malloc(sizeof(*mutex_result)*N_FAC);
    if (mutex_result == NULL)
        return -1;

    for (i=0; i < N_FAC; i++)
    {
        pthread_mutex_t mutex_tmp=PTHREAD_MUTEX_INITIALIZER;

        mpz_init(result[i]);
        mpz_set_ui(result[i],(!i) ? 1 : 0); /* 1! is set here */

        memcpy(&mutex_result[i],&mutex_tmp,sizeof(mutex_tmp));
    }

    for (i=0; i < N_THREADS; i++)
    {
        th_arg[i].start=i*(N_FAC/N_THREADS)+1;
        th_arg[i].end=i*(N_FAC/N_THREADS)+(N_FAC/N_THREADS);

        pthread_create(&threads[i],NULL,thread_init,&th_arg[i]);
    }

    for (i=0; i < N_THREADS; i++)
        pthread_join(threads[i],NULL);

    for (i=0; i < N_FAC; i++)
    {
        gmp_printf("%d! = %Zdn",i+1,result[i]);
        mpz_clear(result[i]);
    }

    free(threads);
    free(th_arg);
    free(result);
    free(mutex_result);

    return 0;
}