kleinsten Skalierungsfaktor zu finden, jede Zahl innerhalb eines Zehntels einer ganzen Zahl aus einem Satz von Doppel zu bekommen

Question

Angenommen, wir, so etwas wie dies haben eine Reihe von Doppel s:

1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89 

Wir wollen jetzt finden der kleinste, positive, ganzzahlige Skalenfaktor x, der ein beliebiges Element von s multipliziert mit x innerhalb eines Zehntel einer ganzen Zahl ist.

Es tut uns leid, wenn das nicht sehr klar ist - bitte fragen Sie nach Klärung, wenn nötig.

Bitte beschränken Sie die Antworten auf C-artige Sprachen oder algorithmischen Pseudocode.

Danke!

Answer 1

Sie suchen nach etwas namens simultane Diophantische Approximation. Die übliche Aussage ist, dass Sie echte Zahlen a_1, ..., a_n und eine positive echte epsilon gegeben werden und Sie wollen ganze Zahlen P_1, ..., P_n und Q so |Q*a_j - P_j| < epsilon finden, hoffentlich mit Q so klein wie möglich.

Dies ist ein sehr gut untersuchtes Problem mit bekannten Algorithmen. Sie sollten jedoch wissen, dass es NP-schwer ist, die beste Approximation mit Q < q zu finden, wobei q ein weiterer Teil der Spezifikation ist. Soweit ich weiß, ist dies für Ihr Problem nicht relevant, weil Sie eine feste epsilon haben und die kleinste Q wollen, nicht umgekehrt.

Ein Algorithmus für das Problem ist (Lenstra-Lenstra) -Lovász Gitterreduktionsalgorithmus. Ich frage mich, ob ich irgendwelche guten Referenzen für dich finden kann. These class notes erwähnen das Problem und Algorithmus, sind aber wahrscheinlich nicht von unmittelbarer Hilfe. Wikipedia hat eine fairly detailed page auf dem Algorithmus, einschließlich einer ziemlich großen Liste von Implementierungen.

Answer 2

Um Vlads modifizierte Frage zu beantworten (wenn Sie genaue ganze Zahlen nach der Multiplikation wollen), ist die Antwort bekannt. Wenn Ihre Zahlen rationale a1/b1, a2/b2, ..., aN/bN sind, mit Brüchen reduziert (ai und bi relativ prim), dann ist die Zahl, die Sie multiplizieren müssen, das kleinste gemeinsame Vielfache von b1, ..., bN.

Answer 3

Dies ist keine vollständige Antwort, aber einige Vorschläge:

Hinweis: Ich bin „s“ für den Skalierungsfaktor, und „x“ für die Doppelzimmer mit.

Fragen Sie sich zuerst, ob Brute-Force nicht funktioniert. Z.B. versuch s = 1, dann s = 2, dann s = 3 und so weiter.

Wir haben eine Liste von Zahlen x [i] und eine Toleranz t = 1/10. Wir wollen die kleinste positive ganze Zahl s finden, so dass es für jedes x [i] eine ganze Zahl q [i] gibt, so dass | s * x [i] - q [i] | < t.

Erstens, wenn wir für jedes x [i] eine geordnete Liste erstellen können, ist es einfach genug, diese zusammenzufassen, um die kleinsten s zu finden, die für alle funktionieren. Zweitens beachte, dass die Antwort nur vom Bruchteil von x [i] abhängt.

Um den obigen Test umzuordnen, haben wir | x - q/s | < t/s. Das heißt, wir wollen eine "gute" rationale Näherung für x finden, in dem Sinne, dass die Approximation besser sein sollte als t/s. Mathematiker haben eine Variante davon untersucht, bei der das Kriterium für "gut" ist, dass es besser sein muss als jedes andere mit einem kleineren "s" -Wert, und der beste Weg, diese zu finden, ist durch Verkürzungen der continued fraction expansion.

Leider ist dies nicht ganz das, was Sie brauchen, denn sobald Sie unter Ihrer Toleranz stehen, müssen Sie nicht immer besser werden - die gleiche Toleranz wird funktionieren. Die nächste offensichtliche Sache ist es, dies zu verwenden, um zu der ersten Nummer zu springen, die funktionieren würde, und von dort brutale Gewalt anzuwenden. Leider kann für jede Nummer die größte der ersten 5 sein, so dass Sie nicht alle so viel kaufen. Allerdings wird diese Methode Ihnen ein s finden, das funktioniert, nur nicht das kleinste. Können wir dieses s verwenden, um ein kleineres zu finden, wenn es existiert? Ich weiß es nicht, aber es wird eine Obergrenze für Brute Forcing setzen.

Wenn die Toleranz für jedes x < t ist, dann bedeutet dies, dass die Toleranz für das Produkt aller x < t^n sein muss. Dadurch könntest du viel weiterspringen und eine vernünftige Untergrenze für Brute-Forcing festlegen.