Ferramentas de Usuário

Ferramentas de Site


dev_geral:c:snippet:factoriais

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;
}
dev_geral/c/snippet/factoriais.txt · Última modificação em: 2018/05/14 21:37 (edição externa)