Algorithme pour trouver un multiplicateur commun pour convertir les nombres décimaux en nombres entiers

https://stackoverflow.com/questions/58493

09-06-2019
|

Question

J'ai un tableau de nombres pouvant contenir jusqu'à 8 décimales et je dois trouver le plus petit nombre commun par lequel je peux les multiplier afin qu'ils soient tous des nombres entiers.J'en ai besoin pour que tous les nombres originaux puissent tous être multipliés à la même échelle et traités par un système scellé qui ne traitera que des nombres entiers, puis je peux récupérer les résultats et les diviser par le multiplicateur commun pour obtenir mes résultats relatifs. .

Actuellement, nous effectuons quelques vérifications sur les nombres et multiplions par 100 ou 1 000 000, mais le traitement effectué par le système *scellé peut devenir assez coûteux lorsqu'il s'agit de grands nombres, donc multiplier tout par un million juste pour le plaisir n'est pas vraiment une excellente option.À titre approximatif, disons que l'algorithme scellé devient 10 fois plus cher chaque fois que vous multipliez par 10.

Quel est l’algorithme le plus efficace, qui donnera également le meilleur résultat possible, pour accomplir ce dont j’ai besoin et existe-t-il un nom mathématique et/ou une formule pour ce dont j’ai besoin ?

*Le système scellé n’est pas vraiment scellé.Je possède/maintiens le code source, mais ses 100 000 lignes de magie propriétaire et il a été minutieusement testé en termes de bogues et de performances, le modifier pour gérer les flotteurs n'est pas une option pour de nombreuses raisons.C'est un système qui crée une grille de cellules X par Y, puis les rectangles X par Y sont déposés dans la grille, la « magie propriétaire » se produit et les résultats sont crachés – il s'agit évidemment d'une version extrêmement simplifiée de la réalité, mais c'est une assez bonne approximation.

Jusqu’à présent, il y a quelques bonnes réponses et je me demandais comment je devrais procéder pour choisir la « bonne ».Au début, je pensais que le seul moyen équitable était de créer chaque solution et de tester ses performances, mais j'ai réalisé plus tard que la vitesse pure n'était pas le seul facteur pertinent : une solution plus précise est également très pertinente.J'ai quand même écrit les tests de performance, mais actuellement, je choisis la bonne réponse en fonction de la vitesse et de la précision en utilisant une formule « instinctive ».

Mes tests de performances traitent 1 000 ensembles différents de 100 nombres générés aléatoirement.Chaque algorithme est testé en utilisant le même ensemble de nombres aléatoires.Les algorithmes sont écrits dans .NET 3.5 (bien que jusqu'à présent serait de 2,0 compatible), j'ai essayé assez fort pour rendre les tests aussi équitables que possible.

Greg - Multipliez par grand nombre, puis divisez par GCD - 63 millisecondes
Andy - Analyse des cordes - 199 millisecondes
Eric – Decimal.GetBits – 160 millisecondes
Eric - Recherche binaire - 32 millisecondes
IMA - Désolé, je ne pouvais pas comprendre un comment implémenter votre solution facilement dans .net (je ne voulais pas y passer trop longtemps)
Bill - Je pense que votre réponse était assez proche de Greg et ne l'a pas mise en œuvre.Je suis sûr que ce serait un peu plus rapide mais potentiellement moins précis.

Donc, la solution de Greg « Multiplier par un grand nombre puis diviser par GCD » était le deuxième algorithme le plus rapide et il a donné les résultats les plus précis, donc pour l'instant je l'appelle correct.

Je voulais vraiment que la solution Decimal.GetBits soit la plus rapide, mais elle était très lente, je ne sais pas si cela est dû à la conversion d'un Double en Decimal ou au masquage et décalage de bits.Il devrait y avoir une solution utilisable similaire pour un double droit en utilisant le BitConverter.getBytes et certaines connaissances contenues ici: 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 mais mes yeux restaient vitreux à chaque fois que je lisais cet article et j'ai finalement manqué de temps pour essayer de mettre en œuvre une solution.

Je suis toujours ouvert à d'autres solutions si quelqu'un peut penser à quelque chose de mieux.

La solution

Je multiplierais par quelque chose de suffisamment grand (100 000 000 pour 8 décimales), puis je diviserais par le PGCD des nombres résultants.Vous vous retrouverez avec une pile de plus petits entiers que vous pourrez transmettre à l'autre algorithme.Après avoir obtenu le résultat, inversez le processus pour récupérer votre plage d'origine.

Autres conseils

Multiples tous les nombres par 10 jusqu'à ce que vous ayez des entiers.
Divisez par 2,3,5,7 alors que vous avez encore tous les entiers.

Je pense que cela couvre tous les cas.

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

Cela suppose que votre multiplicateur puisse être une fraction rationnelle.

Si vous voulez trouver un entier N de sorte que N*x soit également un entier exact pour un ensemble de flottants x dans un ensemble donné sont tous des entiers, alors vous avez un problème fondamentalement insoluble.Supposons que x = le plus petit flottant positif que votre type puisse représenter, disons qu'il vaut 10^-30.Si vous multipliez tous vos nombres par 10^30, puis essayez de les représenter en binaire (sinon, pourquoi essayez-vous si fort de les transformer en entiers ?), alors vous perdrez pratiquement toutes les informations des autres nombres dues. déborder.

Voici donc deux suggestions :

Si vous avez un contrôle sur tout le code connexe, trouvez une autre approche.Par exemple, si vous avez une fonction qui ne prend que des INT, mais que vous avez des flotteurs et que vous souhaitez fourrer vos flotteurs dans la fonction, réécriture ou surchargez simplement cette fonction pour accepter également des flotteurs.
Si vous n'avez pas de contrôle sur la partie de votre système qui nécessite des INT ), puis multiplier tout votre flotteur par cette constante, et autour de l'entier le plus proche.

À propos, si vous avez affaire à des fractions plutôt qu'à des flottants, alors c'est un jeu différent.Si vous avez un tas de fractions a/b, c/d, e/f ;et vous voulez un multiplicateur le plus commun N tel que N*(chaque fraction) = un entier, alors N = abc / pgcd(a,b,c);et pgcd(a,b,c) = pgcd(a, pgcd(b, c)).Vous pouvez utiliser L'algorithme d'Euclide pour trouver le pgcd de deux nombres quelconques.

Grégory :Bonne solution, mais le calcul d'un GCD commun dans un tableau de plus de 100 nombres ne deviendra-t-il pas un peu cher ?Et comment procéderiez-vous ?C'est facile de faire GCD pour deux nombres mais pour 100 cela devient plus complexe (je pense).

Le méchant Andy :Je programme en .Net et la solution que vous proposez correspond à peu près à ce que nous faisons actuellement.Je ne voulais pas l'inclure dans ma question initiale parce que j'espérais une réflexion hors des sentiers battus (ou de ma boîte en tout cas) et je ne voulais pas entacher les réponses des gens avec une solution potentielle.Bien que je n'aie pas de statistiques de performances solides (car je n'ai eu aucune autre méthode pour la comparer), je sais que l'analyse des chaînes serait relativement coûteuse et j'ai pensé qu'une solution purement mathématique pourrait potentiellement être plus efficace.Pour être honnête, la solution actuelle d'analyse de chaînes est en production et il n'y a pas encore eu de plaintes concernant ses performances (elle est même en production dans un système séparé au format VB6 et aucune plainte là non plus).C'est juste que cela ne me semble pas bien, je suppose que cela offense mes sensibilités en matière de programmation - mais cela pourrait bien être la meilleure solution.

Cela dit, je suis toujours ouvert à toute autre solution, purement mathématique ou autre.

Dans quel langage programmez-vous ?Quelque chose comme

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

vous donnerait le nombre de décimales pour un double en C#.Vous pouvez parcourir chaque nombre et trouver le plus grand nombre de décimales (x), puis multiplier chaque nombre par 10 à la puissance x.

Modifier:Par curiosité, quel est ce système scellé auquel vous ne pouvez transmettre que des entiers ?

Dans une boucle, obtenez la mantisse et l'exposant de chaque nombre sous forme d'entiers.Vous pouvez utiliser frexp pour l'exposant, mais je pense qu'un masque de bits sera requis pour la mantisse.Trouvez l'exposant minimal.Recherchez les chiffres les plus significatifs dans la mantisse (parcourez les bits à la recherche du dernier "1") - ou utilisez simplement un nombre prédéfini de chiffres significatifs.Votre multiple est alors quelque chose comme 2^(numberOfDigits-minMantissa)."Quelque chose comme" parce que je ne me souviens pas des biais/compensations/gammes, mais je pense que l'idée est assez claire.

Donc, fondamentalement, vous voulez déterminer le nombre de chiffres après la virgule pour chaque nombre.

Ce serait plutôt plus facile si vous aviez la représentation binaire du nombre.Les nombres sont-ils convertis à partir de notations rationnelles ou scientifiques plus tôt dans votre programme ?Si tel est le cas, vous pouvez ignorer la conversion précédente et passer un moment beaucoup plus facile.Sinon, vous souhaiterez peut-être transmettre chaque nombre à une fonction dans une DLL externe écrite en C, où vous pourrez travailler directement avec la représentation à virgule flottante.Ou vous pouvez convertir les nombres en décimaux et travailler avec Décimal.GetBits.

L'approche la plus rapide à laquelle je puisse penser sur place et suivant vos conditions serait de trouver la plus petite puissance de dix nécessaire (ou 2, ou autre) comme suggéré précédemment.Mais au lieu de le faire en boucle, économisez quelques calculs en effectuant une recherche binaire sur les puissances possibles.En supposant un maximum de 8, quelque chose comme :

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 :vous ne transmettriez pas les prix des titres à un moteur de tarification d'options, n'est-ce pas ?Il a exactement la saveur...

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow