Testando os quadrados por somas de ímpares de Pitágoras e otimização

Eu vi a seguinte publicação no Facebook e pensei em testar computacionalmente até um limite grande. Para quem não quer, ou não tem como, acessar o Facebook, reproduzo a imagem abaixo:

Quando escrevia o programa notei que estava fazendo errado, que o código iria gastar tempo demais inutilmente, então reescrevi o código resolvendo isto.

A primeira versão do programa foi:

#include        <stdio.h>

int     main()
{
        register unsigned long long numero, impar, soma ;

        for( numero = 1 ; numero <= 1000000000 ; numero++ )
        {
                register int    i ;

                for( i = numero, impar = 1, soma = 0 ; i ; i--, impar +=2 )
                        soma += impar ;

                if( soma != numero*numero )
                        printf( "Falhou para o numero %llu\n",numero );
        }
}

Esta é a descrição literal do problema, mas nem sempre a descrição literal é a melhor a ser implementada. O que está errado neste programa?

O problema é que estava pensando em números individualmente quando quero testar toda uma faixa. E se eu aproveitar o cálculo anterior para calcular o atual? Ou seja, eu só preciso somar um número ímpar, e não todos desde o início a cada iteração.

#include        <stdio.h>

int     main()
{
        register unsigned long long     numero, soma, impar     ;

        for( numero = 1, impar = 1, soma = 0 ; numero <= 1000000000 ; numero++, impar +=2 )
        {
                soma += impar ;

                if( soma != numero*numero )
                        printf( "Falhou para o numero %llu\n",numero );
        }
}

Qual é a diferença do tempo de processamento?

O primeiro programa tem um corportamento quadrático. Cada iteração da variável numero gastará mais tempo que a iteração anterior e menos do que a seguinte, pois a quantidade de iterações do loop interno aumenta a cada iteração da variável numero. E o segundo programa é linear, cada iteração gastará o mesmo tempo da iteração anterior e da posterior. Não tem um loop interno dependente da variável numero.

E qual é o efeito prático disto? Para números pequenos não foi tão perceptível, mas para 1000000000, um bilhão, não tem como negar. O gasto de tempo do primeiro esta abaixo:

goffredo:notebook2[949] time ./quadrados_por_impares
4.394u 0.000s 0:04.48 97.9%     5+167k 0+0io 0pf+0w

E do segundo programa:

goffredo:notebook2[950] time ./quadrados_por_impares_V2.0
0.029u 0.000s 0:00.03 66.6%     6+198k 0+0io 0pf+0w

São 4394 milisegundos contra 29 milisegundos. Mais de 150 vezes o tempo de processamento.

Valeu a pena pensar um pouco mais.

Outras notas

Perceba que usei as variáveis como register unsigned long long. Eu pedi pelo máximo de otimização delas, que fossem sem sinal e que fossem inteiros de 64 bits para caber o número que eu queria calcular, e seu quadrado.

Para imprimir o valor da variável  numero, caso o teste falhasse, usei %llu. Isto quer dizer um unsigned long long deve ser esperado como parâmetro e escrito na saída, que é o tipo da variável em questão.

Pode notar as múltiplas inicializações e os múltiplos incrementos nos for nos dois programas. Isto é algo plenamente válido no C.

Note o loop interno na primeira versão. Ele tem uma otimização. Ao invés de fazer a variável de controle crescente e testar com o número de iterações desejado, eu a iniciei com o número de iterações desejado e a fiz decrescente. Tem dois motivos para isto. O primeiro é que só vai acessar a variável numero uma única vez, ao invés de a cada iteração do loop, e comparar com zero é simples.

E qual é a solução geral?

O Thiago Fanelli Ferraiol apresentou a sua resposta, que reproduzo abaixo:

Bem simples, não?