Algoritmo para encontrar um multiplicador comum para converter números decimais em números inteiros

https://stackoverflow.com/questions/58493

09-06-2019
|

Pergunta

Eu tenho uma matriz de números que potencialmente têm até 8 casas decimais e preciso encontrar o menor número comum pelo qual posso multiplicá-los para que sejam todos números inteiros.Eu preciso disso para que todos os números originais possam ser multiplicados na mesma escala e processados por um sistema selado que lide apenas com números inteiros, então eu posso recuperar os resultados e dividi-los pelo multiplicador comum para obter meus resultados relativos .

Atualmente fazemos algumas verificações nos números e multiplicamos por 100 ou 1.000.000, mas o processamento feito pelo sistema *selado pode ficar bastante caro ao lidar com números grandes, então multiplicar tudo por um milhão só por fazer não é realmente uma ótima opção.Como aproximação, digamos que o algoritmo selado fique 10 vezes mais caro cada vez que você multiplica por um fator de 10.

Qual é o algoritmo mais eficiente, que também dará o melhor resultado possível, para realizar o que preciso e existe um nome matemático e/ou fórmula para o que preciso?

*O sistema selado não é realmente selado.Eu possuo/mantenho o código-fonte dele, mas suas 100.000 linhas estranhas de magia proprietária e ele foi exaustivamente testado contra bugs e desempenho, alterá-lo para lidar com carros alegóricos não é uma opção por vários motivos.É um sistema que cria uma grade de células X por Y, depois os retângulos que são X por Y são colocados na grade, ocorre uma “mágica proprietária” e os resultados são cuspidos – obviamente, esta é uma versão extremamente simplificada da realidade, mas é uma aproximação suficientemente boa.

Até agora, existem algumas boas respostas e me perguntei como deveria escolher a resposta “correta”.No início, imaginei que a única maneira justa seria criar cada solução e testá-la em termos de desempenho, mas depois percebi que a velocidade pura não era o único fator relevante – uma solução mais precisa também é muito relevante.Eu escrevi os testes de desempenho de qualquer maneira, mas atualmente estou escolhendo a resposta correta com base na velocidade e também na precisão usando uma fórmula de “intuição”.

Meus testes de desempenho processam 1.000 conjuntos diferentes de 100 números gerados aleatoriamente.Cada algoritmo é testado usando o mesmo conjunto de números aleatórios.Os algoritmos são escritos no .NET 3.5 (embora até agora seja 2,0 compatível), tentei muito fazer os testes o mais justo possível.

Greg - Multiplique por grande número e depois divida por GCD - 63 milissegundos
Andy - String Parsing - 199 milissegundos
Eric – Decimal.GetBits – 160 milissegundos
Eric - Pesquisa binária - 32 milissegundos
IMA - desculpe, não consegui descobrir como implementar sua solução facilmente no .net (eu não queria gastar muito tempo com isso)
Bill - acho que sua resposta estava bem perto da de Greg, então não a implementou.Tenho certeza de que seria um pouco mais rápido, mas potencialmente menos preciso.

Portanto, a solução Multiplicar por grande número e depois dividir por GCD ”de Greg foi o segundo algoritmo mais rápido e forneceu os resultados mais precisos, então, por enquanto, estou considerando-o correto.

Eu realmente queria que a solução Decimal.GetBits fosse a mais rápida, mas era muito lenta, não tenho certeza se isso é devido à conversão de um Double em Decimal ou ao mascaramento e deslocamento de bits.Deve haver uma solução utilizável semelhante para um duplo direto usando o bitconverter.getbytes e algum conhecimento contido aqui: http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point-types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew- greig.aspx mas meus olhos ficavam vidrados toda vez que lia aquele artigo e acabei ficando sem tempo para tentar implementar uma solução.

Estou sempre aberto a outras soluções se alguém puder pensar em algo melhor.

Solução

Eu multiplicaria por algo suficientemente grande (100.000.000 para 8 casas decimais) e depois dividiria pelo GCD dos números resultantes.Você acabará com uma pilha de menores números inteiros que poderá alimentar o outro algoritmo.Depois de obter o resultado, inverta o processo para recuperar o intervalo original.

Outras dicas

Vários números por 10 até que você tenha números inteiros.
Divida por 2,3,5,7 enquanto você ainda tem todos os números inteiros.

Acho que isso abrange todos os casos.

2.1 * 10/7 -> 3
0.008 * 10^3/2^3 -> 1

Isso pressupõe que seu multiplicador possa ser uma fração racional.

Se você quiser encontrar algum número inteiro N de modo que N*x também seja um número inteiro exato para um conjunto de pontos flutuantes x em um determinado conjunto são todos números inteiros, então você tem um problema basicamente insolúvel.Suponha que x = o menor ponto flutuante positivo que seu tipo pode representar, digamos que seja 10 ^ -30.Se você multiplicar todos os seus números por 10 ^ 30 e, em seguida, tentar representá-los em binário (caso contrário, por que você está se esforçando tanto para transformá-los em inteiros?), você perderá basicamente todas as informações dos outros números devido transbordar.

Então aqui vão duas sugestões:

Se você tiver controle sobre todo o código relacionado, encontre outra abordagem.Por exemplo, se você tem alguma função que leva apenas os int, mas você tem carros alegóricos e deseja encher seus carros alegóricos na função, basta reescrever ou sobrecarregar essa função para aceitar carros alegóricos também.
Se você não tiver controle sobre a parte do seu sistema que requer INTs, escolha uma precisão com a qual você se preocupa, aceite que você simplesmente terá que perder algumas informações às vezes (mas sempre será "pequeno" em certo sentido ) e, em seguida, apenas multiplique todo o seu flutuador por essa constante e em volta para o número inteiro mais próximo.

A propósito, se você está lidando com frações, em vez de números flutuantes, então é um jogo diferente.Se você tiver um monte de frações a/b, c/d, e/f;e você deseja um multiplicador menos comum N tal que N*(cada fração) = um número inteiro, então N = abc / mdc(a,b,c);e mdc(a,b,c) = mdc(a, mdc(b, c)).Você pode usar Algoritmo de Euclides para encontrar o mdc de quaisquer dois números.

Greg:Boa solução, mas calcular um GCD comum em uma matriz de mais de 100 números não ficará um pouco caro?E como você faria isso?É fácil fazer o GCD para dois números, mas para 100 fica mais complexo (eu acho).

Andy malvado:Estou programando em .Net e a solução que você apresenta é praticamente compatível com o que fazemos agora.Eu não queria incluí-lo na minha pergunta original porque esperava algum pensamento fora da caixa (ou da minha caixa, pelo menos) e não queria contaminar as respostas das pessoas com uma solução potencial.Embora eu não tenha nenhuma estatística de desempenho sólida (porque não tive nenhum outro método para compará-la), sei que a análise de string seria relativamente cara e imaginei que uma solução puramente matemática poderia ser potencialmente mais eficiente.Para ser justo, a solução atual de análise de strings está em produção e ainda não houve reclamações sobre seu desempenho (está até mesmo em produção em um sistema separado no formato VB6 e também não há reclamações).Só que não parece certo, acho que ofende minha sensibilidade de programação - mas pode muito bem ser a melhor solução.

Dito isto, ainda estou aberto a quaisquer outras soluções, puramente matemáticas ou não.

Em qual linguagem você está programando?Algo como

myNumber.ToString().Substring(myNumber.ToString().IndexOf(".")+1).Length

lhe daria o número de casas decimais para um duplo em C#.Você poderia analisar cada número e encontrar o maior número de casas decimais (x) e, em seguida, multiplicar cada número por 10 elevado à potência de x.

Editar:Por curiosidade, o que é esse sistema selado para o qual você só pode passar números inteiros?

Em um loop, obtenha a mantissa e o expoente de cada número como inteiros.Você pode usar frexp como expoente, mas acho que a máscara de bits será necessária para a mantissa.Encontre o expoente mínimo.Encontre os dígitos mais significativos na mantissa (percorra os bits procurando o último "1") - ou simplesmente use um número predefinido de dígitos significativos.Seu múltiplo é algo como 2^(numberOfDigits-minMantissa)."Algo como" porque não me lembro de preconceitos/compensações/intervalos, mas acho que a ideia é bastante clara.

Basicamente, você deseja determinar o número de dígitos após a vírgula decimal para cada número.

Isso seria bem mais fácil se você tivesse a representação binária do número.Os números estão sendo convertidos de notação racional ou científica anteriormente em seu programa?Nesse caso, você pode pular a conversão anterior e ter muito mais facilidade.Caso contrário, você pode querer passar cada número para uma função em uma DLL externa escrita em C, onde você poderia trabalhar diretamente com a representação de ponto flutuante.Ou você pode transformar os números em decimais e trabalhar com Decimal.GetBits.

A abordagem mais rápida que consigo pensar no local e seguindo suas condições seria encontrar a menor potência de dez necessária (ou 2, ou qualquer outra coisa), conforme sugerido anteriormente.Mas em vez de fazer isso em loop, economize alguns cálculos fazendo uma pesquisa binária nas potências possíveis.Supondo um máximo de 8, algo como:

int NumDecimals( double d )
{
   // make d positive for clarity; it won't change the result
   if( d<0 ) d=-d;

   // now do binary search on the possible numbers of post-decimal digits to 
   // determine the actual number as quickly as possible:

   if( NeedsMore( d, 10e4 ) )
   {
      // more than 4 decimals
      if( NeedsMore( d, 10e6 ) )
      {
          // > 6 decimal places
          if( NeedsMore( d, 10e7 ) ) return 10e8;
          return 10e7;
      }
      else
      {
         // <= 6 decimal places
         if( NeedsMore( d, 10e5 ) ) return 10e6;
         return 10e5;
      }
   }
   else
   {
      // <= 4 decimal places
      // etc...
   }

}

bool NeedsMore( double d, double e )
{
   // check whether the representation of D has more decimal points than the 
   // power of 10 represented in e.
   return (d*e - Math.Floor( d*e )) > 0;
}

PS:você não estaria repassando os preços dos títulos para um mecanismo de precificação de opções, estaria?Tem exatamente o sabor...

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow