Algorithms | Soma 1 até a um natural x

Não sei se o titulo será o mais acertado, mas esse é o nome de um algoritmo que vi num site a uns dias. O algoritmos faz o seguinte, dando um numero natural, por exemplo 5, é feita a seguinte operação 5+4+3+2+1 = 15, mas esse algoritmo recorria a recursão logo em termos de performance não é grande coisa(como vamos ver mais a frente, somente quando se trata de números grandes).

Então resolvi pegar o algoritmo e tenta-lo optimiza-lo ao máximo em linguagem c/c++, alem disso adicionei suporte a 64bit aumentando assim a gama de valores que este suporta.

Código antigo:

int SomatRec(int n)
{
int soma;
if(n==1){
soma=1;}
else{
soma=n+SomatRec(n-1);}
return soma;
}

Novo código:

/**
* Add 1 to a natural x.
*
* Function without recursion, very optimized.
* By Gil Mendes (gil0mendes)
*
* @param int64_t number - Natural number (x)
* @return int64_t - Result
*/
int64_t add1ToX(register int64_t number) {
register int64_t total = 0;

do {
total += number--;
} while(number != 0);

return total;
}

Fazendo alguns testes podemos ver que a recursão até é boa quando se trata de números pequenos, aqui fina uma tabela com os valores(tempos em microsegundos):

Valor Resultado sem recursão Tempo sem recursão Resultado com recursão Tempo com recursão
5 15 5 15 2
100 5050 6 50500 5
1000 500500 13 500500 61
100000 5000050000 541 705082704 4143
1000000 500000500000 5866 Não suportado Não suportado
1000000000 500000000500000000 2807508 Não suportado Não suportado

Pode-de concluir que o algoritmo que fiz é muito melhor, em primeiro comporta-se muito bem em termos de tempo, utiliza muito menos memoria e ainda suporta uma maior gama de números, aqui fica o link com o source code do programa de testes.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s