Algorithmus einen gemeinsamen Multiplikator zu finden Dezimalzahlen auf ganze Zahlen zu konvertieren

https://stackoverflow.com/questions/58493

09-06-2019
|

Frage

Ich habe eine Reihe von Zahlen, die möglicherweise bis zu 8 Dezimalstellen haben und ich brauche die kleinste gemeinsame Nummer finden ich sie so vermehren kann, dass sie alle ganzen Zahlen sind. Ich brauche dies so alle ursprünglichen Zahlen alle im gleichen Maßstab multipliziert werden kann und durch ein geschlossenes System verarbeitet werden, die nur mit ganzen Zahlen umgehen wird, dann kann ich die Ergebnisse abrufen und teilen sie durch den gemeinsamen Multiplikator meine relativen Ergebnisse zu erhalten .

Zur Zeit haben wir ein paar Kontrollen auf den Zahlen und multiplizieren Sie mit 100 oder einer Million, aber die Verarbeitung durch das * geschlossene System erfolgen kann sehr teuer werden, wenn sie mit großen Zahlen zu tun, um alles von einer Million multipliziert, nur um es isn ‚t wirklich eine gute Option. Als eine Annäherung sagen lässt, dass der abgedichtete Algorithmus 10 mal teurer Sie um den Faktor 10 multiplizieren jedes Mal bekommt.

Was ist der effizienteste Algorithmus, dass auch das bestmögliche Ergebnis geben zu erreichen, was ich brauche, und gibt es einen mathematischen Namen und / oder Formel für das, was ich braucht?

* Das geschlossene System ist nicht wirklich verschlossen. Ich besitze / pflegen den Quellcode für sie, aber seine 100.000 ungeraden Zeilen proprietärer Magie und es wurde gründlich Fehler und Leistung getestet, es zu verändern mit Schwimmern zu behandeln ist keine Option, aus vielen Gründen. Es ist ein System, das ein Gitter von X durch Y-Zellen erzeugt, dann Rects, die X von Y sind in das Netz fallen gelassen „proprietäre Magie“ auftritt und die Ergebnisse werden ausgespuckt - offensichtlich ist dies eine extrem vereinfachte Version der Realität, aber es ist gut genug Annäherung.

Bisher gibt es ruhig ein paar gute Antworten und ich fragte mich, wie ich über die Wahl der ‚richtigen‘ man gehen sollte. Zunächst einmal mir der einzige Messe Weg gefunden wurde jede Lösung und Performance-Test, es zu schaffen, aber ich später erkennen, dass reine Geschwindigkeit war nicht der einzige relevante Faktor - eine genauere Lösung ist auch sehr relevant. Ich schrieb trotzdem die Performance-Tests, aber derzeit die ich die Wahl die richtige Antwort basierend auf Geschwindigkeit und Genauigkeit eine ‚Bauchgefühl‘ Formel.

Meine Performance-Tests verarbeiten 1000 verschiedene Sätze von 100 zufällig erzeugten Zahlen. Jeder Algorithmus wird getestet, um den gleichen Satz von Zufallszahlen. Die Algorithmen werden in .NET 3.5 geschrieben (obwohl bisher 2.0 kompatibel sein würde) Ich habe versucht, ziemlich schwer, die Tests so fair wie möglich zu machen.

Greg - Multiplizieren von großer Zahl und dann von GCD Divide - 63 Millisekunden
Andy - String Parsing - 199 Millisekunden
Eric - Decimal.GetBits - 160 Millisekunden
Eric - Binäre Suche - 32 Millisekunden
Ima - sorry ich konnte nicht herauszufinden, ein, wie zu implementieren Ihre leicht Lösung in .net (ich habe nicht wollen zu lange verbringen, auf sie)
Bill - Ich schätze Ihre Antwort war ziemlich schließen so zu Gregs nicht implementieren es. Ich bin sicher, dass es eine smidge würde schneller aber möglicherweise weniger genau.

So Gregs Multipliziert mit großer Anzahl und teilen sich dann durch GCD“Lösung war der zweitschnellste Algorithmus und es gab die genauesten Ergebnisse so jetzt ich es bin Aufruf richtig.

Ich wollte wirklich die Decimal.GetBits Lösung die schnellsten sein, aber es war sehr langsam, ich bin nicht sicher, ob dies zu einem Dezimal oder der Bit Maskierung und Verschiebung auf die Umwandlung eines Doppel fällig ist. Es sollte ein ähnlich brauchbare Lösung für einen geraden Doppel die BitConverter.GetBytes mit und einige hier enthaltenen Wissen: http://blogs.msdn.com/bclteam/archive/2007/ 29.05 / bcl-Refresher-Floating-Point-Typen-the-good-the-bad-und-die-ugly-Inbar-Gazit-matthew-greig.aspx aber meine Augen nur gehalten Verglasung jedes Mal über ich habe gelesen, dass Artikel und ich lief schließlich aus der Zeit, um zu versuchen, eine Lösung zu implementieren.

Ich bin immer offen für andere Lösungen, wenn jemand etwas b denken kannEtter.

Lösung

ich von etwas ausreichend groß (100 Mio. für 8 Dezimalstellen) multipliziert würde, dann teilen durch das GCD der erhaltenen Zahlen. Sie werden sie mit einem Haufen von kleinsten ganzen Zahlen enden, die Sie den anderen Algorithmus einspeisen können. Nachdem das Ergebnis bekommen, Reverse den Prozess Ihren ursprünglichen Bereich.

Andere Tipps

Mehrere alle Zahlen von 10 bis Sie ganze Zahlen haben.
Teilen von 2,3,5,7, während Sie haben noch alle Zahlen.

Ich denke, dass alle Fälle abdeckt.

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

Das ist dein Multiplikator unter der Annahme, kann ein rationaler Bruch sein.

Wenn Sie eine ganze Zahl N finden wollen, so dass N * x ist auch eine exakte ganze Zahl für eine Reihe von Schwimmern x in einer gegebenen Menge sind alle ganzen Zahlen, dann haben Sie eine grundsätzlich unlösbares Problem. Angenommen, x = der kleinste positive Schwimmer Ihre Art darstellen kann, sagen, es ist 10 ^ -30. Wenn Sie mit 10 ^ 30, die alle Ihre Zahlen multiplizieren und dann versuchen, sie in binärer darzustellen (sonst, warum versuchen Sie auch so schwer zu ihnen Ints zu machen?), Dann werden Sie verlieren grundsätzlich alle Informationen der anderen Zahlen durch Überlauf zu.

hier So sind zwei Vorschläge:

Wenn Sie alle Kontrolle über den zugehörigen Code haben, finden eine andere Ansatz. Zum Beispiel, wenn Sie eine Funktion, die haben dauert nur int ist, aber Sie haben Schwimmern, und Sie möchten Ihre Schwimmer stopfen in die Funktion, nur neu zu schreiben oder diese Funktion Überlastung akzeptieren auch schwimmt.
Wenn Sie nicht die Kontrolle über den Teil des Systems, das erfordert int ist, wählen Sie dann eine Genauigkeit, zu der sich um dich kümmern, akzeptieren, dass Sie werden einfach mal einige Informationen verlieren müssen (aber es wird seine „klein“ immer in einem gewissen Sinne), und dann einfach multiplizieren all schweben die durch diese Konstante und runden auf die nächste ganze Zahl.

übrigens, wenn Sie mit Brüchen zu tun haben, eher als Float, dann ist es ein anderes Spiel. Wenn Sie eine Reihe von Fraktionen a / b, c / d, e / f; und Sie ein kleinster gemeinsamer Multiplikator N, so dass N * (jede Fraktion) = eine ganze Zahl, dann N = a b c / ggT (a, b, c); und ggT (a, b, c) = gcd (a, gcd (b, c)). Sie können verwenden Euklids Algorithmus die gcd von zwei Zahlen zu finden.

Greg: Nice Lösung, aber kein GCD berechnen, die in einer Reihe von mehr als 100 Zahlen üblich ist, bekommt ein bisschen teuer? Und wie würden Sie das gehen? Seine einfache GCD für zwei Zahlen zu tun, aber für 100 es wird komplexer (glaube ich).

Evil Andy: Ich bin Programmierung in .Net und die Lösung, die Sie stellen ist so ziemlich ein Spiel für das, was wir jetzt tun. Ich wollte es nicht in meiner ursprünglichen Frage schließen, weil ich für einige außerhalb der Box hatte gehofft (oder meine Box sowieso) denkt, und ich wollte nicht, Völker Antworten mit einer potentiellen Lösung besudeln. Ich habe zwar keine solide Performance-Statistiken (weil ich keine andere Methode gehabt haben, um es zu vergleichen, gegen) Ich weiß, würde der String-Parsing relativ teuer sein und ich dachte, möglicherweise eine rein mathematische Lösung effizienter sein könnte. Um die aktuelle String-Parsing-Lösung fair ist in der Produktion und es wurde noch keine Beschwerden über seine Leistung (seine selbst in der Produktion in einem separaten System in einem VB6-Format und keine Beschwerden dort entweder). Es ist nur so, dass es nicht richtig anfühlt, ich denke, es ist meine programing Empfindlichkeiten beleidigt - aber es kann auch die beste Lösung sein

Wie gesagt ich bin immer noch offen für andere Lösungen, rein mathematisch oder nicht.

Welche Sprache programmieren Sie? So etwas wie

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

würden Sie die Anzahl der Nachkommastellen für ein Doppel in C #. Sie könnten jede Nummer durch, dass laufen und die größte Anzahl von Dezimalstellen (x) finden, dann von 10 auf die Kraft der x jede Zahl multiplizieren.

Edit: Aus Neugier, was dieses geschlossene System ist, das können Sie nur ganze Zahlen passieren

In einer Schleife Mantisse und Exponenten jeder Zahl als ganze Zahlen bekommen. Sie können frexp für Exponenten verwenden, aber ich denke, wird Bitmaske für Mantisse erforderlich. Finden minimale Exponenten. Finden höchstwertigen Stellen in Mantisse (Schleife durch Bits der Suche nach letzten „1“) - oder verwenden Sie einfach vordefinierte Anzahl von signifikanten Stellen. Ihre mehrfach ist dann so etwas wie 2 ^ (numberOfDigits-minMantissa). „So etwas wie“ weil ich mich nicht erinnern, spannt / Offsets / Bereiche, aber ich denke Idee klar genug ist.

Also im Grunde wollen Sie die Anzahl der Stellen nach dem Komma für jede Nummer bestimmen.

Dies wäre eher einfacher, wenn Sie die binäre Darstellung der Zahl haben. Werden die Zahlen von rationals oder wissenschaftlicher Notation früher in Ihrem Programm konvertieren? Wenn ja, könnten Sie die frühere Umwandlung überspringen und eine viel einfachere Zeit haben. Andernfalls könnten Sie jede Zahl auf eine Funktion in einer externen DLL in C geschrieben passieren, wo Sie direkt mit der Floating-Point-Darstellung arbeiten können. Oder Sie könnten die Zahlen werfen in Dezimalzahlen und einige Arbeit mit Decimal.GetBits .

Der schnellste Ansatz, den ich von an Ort und Stelle denken und Ihre Bedingungen folgende wäre die kleinste notwendige Potenz von zehn (oder 2 oder was auch immer) zu finden wie zuvor vorgeschlagen. Aber anstatt es in einer Schleife zu tun, speichert einige Berechnung durch die möglichen Kräfte binäre Suche zu tun. Unter der Annahme, ein Maximum von 8, so etwas wie:

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: Sie wäre nicht die Preise der Wertpapiere zu einem Optionspreis Motor würden Sie vorbei? Es hat genau den Geschmack ...

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow