Flutuações Estranhas em C++
Recentemente eu iniciei a resolução do problema 43 da parte Core no Codesignal, chamado de Is Power. E apesar de estar listado como um problema fácil, eu encontrei uma parte bastante interessante sobre as funções padrões do C++ e como elas lidam com pontos flutuantes.
O Problema
Dado um número n, sua função deve retornar true caso o mesmo seja potência de outro número inteiro, ou false caso contrário. Usando as propriedades de logaritmos, bastava determinar um limite e criar um loop que tentasse encontrar um resultado inteiro. Minha resolução pode ser vista aqui.
O grande problema aqui é determinar se um número double não contém parte decimal partindo do resultado da função std::log. Meu primeiro instinto foi tentar usar o operador % (resto) com o número 1, dado que todo número inteiro não tem resto ao ser dividido por 1, porém esse operador não tem suporte a valores de ponto flutuante, então tive que buscar criatividade.
As Soluções
Buscando no Google a primeira solução que encontrei foi usar a função std::modf, que armazena a parte inteira de um número em dado endereço e retorna sua parte flutuante. Então, definir se um número n é inteiro poderia ser feito como:
bool isInt = (std::modf(n, &intPart) == 0);
Usando este método, eu obtive um resultado 9/10 nos testes, porém com o número 125 (5³), que teria como resultado verdadeiro na quinta interação, a comparação não funciona.
Dado que a std::modf não havia funcionado em todos os casos, eu busquei outra função que pudesse retornar apenas a parte inteira de um número, e encontrei uma thread no StackOverflow dizendo que a função std::trunc, usada para arredondar números, poderia ser usada como a seguir:
bool isInt = (std::trunc(n) == n);
Porém, novamente a comparação falhava para os resultados quando usada para o retorno do Log ₃ (125).
Olhando para os resultados
Sem entender o motivo da comparação falhar em apenas um resultado específico, eu decidi olhar para as diferenças entre a saída das funções e o número original, obtendo os seguintes valores:
n — std::trunc(n) = 4.44089e-16;
n — std::modf(n, &intPart) = 4.44089e-16;
Ambas iguais, e embora estejam bem próximas, não são o mesmo que zero, tornando a comparação falsa.
Olhando para esses números infimamente pequenos, me ocorreu que talvez existisse algum problema para essas funções em lidar com números pequenos. Porém, ao analizar a implementação descrita, ficou claro para mim que isso estaria além de quem ainda está aprendendo pequenos problemas em C++.
Um zero maior
Sendo que isso acontecia em apenas em um problema, eu decidi pensar se existia algum modo satisfatório de definir um número próximo a essa diferença como zero e que fosse o bastante para todos os problemas.
Lendo a mesma thread no StackOverflow, uma das respostas citava a função std::numeric_limits<double>::epsilon() como um modo de descobrir a menor fração dentro da máquina que pode ser considerada maior que zero, no caso da minha execução dentro do CodeSignal, 2.22045e-16.
Sendo assim, a minha comparação retornava o dobro da menor fração considerada como zero. O que eu precisava era definir meu novo limite com base nesse número. Decidi que a comparação final poderia ser:
if (diff) < (100 * std::numeric_limits<double>::epsilon())…
Efetivamente tornando minha comparação igual a zero maior que a comparação da máquina.
Executando o programa, finalmente eu consigo um resultado 10!
P.S.: Se você quer entender melhor porque zero em ponto flutuante não é exatamente zero e a nomenclatura epsilon, a wikipédia é um ótimo lugar para começar.
