Ermittlung des nächstgelegenen ganzzahligen Bruchs zu einem gegebenen zufälligen reellen Wert zwischen 0..1 bei gegebenen Bereichen von Zähler und Nenner

Question

Gegeben sind zwei Bereiche positiver ganzer Zahlen x: [1 ... n] y y: [1 ... m] und einem zufälligen reellen Wert R von 0 bis 1 muss ich das Paar von Elementen (i,j) aus x und y finden, so dass x_i / y_j am nächsten an R liegt.

Wie kann ich dieses Paar am effizientesten finden?

Answer 1

Verwendung von Farey-Sequenz

Dies ist ein einfacher und mathematisch schöner Algorithmus, um dieses Problem zu lösen: Führen Sie eine binäre Suche durch, wobei bei jeder Iteration die nächste Zahl durch die Mediant-Formel (unten) gegeben ist. Aufgrund der Eigenschaften der Farey-Folge ist diese Zahl diejenige mit dem kleinsten Nenner innerhalb dieses Intervalls. Folglich wird diese Folge immer konvergieren und niemals eine gültige Lösung "verfehlen".

In Pseudocode:

input: m, n, R

a_num = 0, a_denom = 1
b_num = 1, b_denom = 1

repeat:
    -- interestingly c_num/c_denom is already in reduced form
    c_num = a_num + b_num
    c_denom = a_denom + b_denom

    -- if the numbers are too big, return the closest of a and b
    if c_num > n or c_denom > m then
        if R - a_num/a_denom < b_num/b_denom - R then
            return a_num, a_denom
        else
            return b_num, b_denom

    -- adjust the interval:
    if c_num/c_denom < R then
        a_num = c_num, a_denom = c_denom
    else
        b_num = c_num, b_denom = c_denom

goto repeat

Auch wenn es im Durchschnitt schnell ist (ich schätze, dass es O(log max(m,n)) ), kann sie dennoch langsam sein, wenn R nahe an einem Bruch mit kleinem Nenner liegt. Zum Beispiel findet man eine Annäherung an 1/1000000 con m = n = 1000000 wird eine Million Iterationen benötigen.

Answer 2

Der Standardansatz zur Annäherung der reellen Zahlen an die rationalen Zahlen ist die Berechnung der fortgesetzte Bruchrechnung (siehe [1]). Legen Sie bei der Berechnung von Teilen der Reihe eine Grenze für den Zähler und den Nenner fest, und der letzte Wert vor dem Bruch der Grenzen ist ein Bruch, der sehr nahe an Ihrer realen Zahl liegt.

Auf diese Weise wird sehr schnell eine sehr gute Annäherung gefunden, aber ich bin mir nicht sicher, ob damit immer eine möglichst gute Annäherung gefunden wird. Es ist bekannt, dass

jeder konvergente [Teilwert der Erweiterung des Kettenbruchs] ist näher am Kettenbruch als jeder andere Bruch, dessen Nenner kleiner ist als der des konvergenten

aber es kann Näherungen mit größerem Nenner (immer noch unter Ihrem Grenzwert) geben, die bessere Näherungen sind, aber keine Konvergenzen darstellen.

[1] http://en.wikipedia.org/wiki/Continued_fraction

Answer 3

Unter der Voraussetzung, dass R eine reelle Zahl ist, so dass 0 <= R <= 1 ganze Zahlen x: [1 ... n] und ganze Zahlen y: [1 ... m] . Es wird angenommen, dass n <= m , denn wenn n > m entonces x[n]/y[m] wird größer sein als 1 , die nicht die beste Annäherung an R .

Daher ist die beste Annäherung von R mit dem Nenner d entweder floor(R*d) / d o ceil(R*d) / d .

Das Problem kann gelöst werden durch O(m) Zeit und O(1) Raum (in Python):

from __future__ import division
from random import random
from math import floor

def fractionize(R, n, d):
    error = abs(n/d - R)
    return (n, d, error)  # (numerator, denominator, absolute difference to R)

def better(a, b):
    return a if a[2] < b[2] else b

def approximate(R, n, m):
    best = (0, 1, R)
    for d in xrange(1, m+1):
        n1 = min(n, int(floor(R * d)))
        n2 = min(n, n1 + 1) # ceil(R*d)
        best = better(best, fractionize(R, n1, d))
        best = better(best, fractionize(R, n2, d))
    return best

if __name__ == '__main__': 
    def main():
        R = random()
        n = 30
        m = 100
        print R, approximate(R, n, m)
    main()

Answer 4

Prolly bekommen flamed, aber ein Lookup könnte am besten sein, wo wir alle der gebrochenen Werte für jeden der möglichen Werte zu berechnen. Also ein einfaches Indizieren eines 2D-Arrays, das über die Bruchteile mit dem Arrayelement indiziert wird, das die reale Entsprechung enthält. Ich schätze, wir haben diskrete X- und Y-Teile, so dass dies endlich ist, es wäre nicht andersherum .... Ahh ja, der eigentliche Suchteil....erm reet....

Answer 5

Die Lösung: Das können Sie tun O(1) Raum und O(m log(n)) Zeit:

Es ist nicht notwendig, eine Liste für die Suche zu erstellen,

Der Pseudocode kann fehlerhaft sein, aber die Idee ist folgende:

r: input number to search.
n,m: the ranges.

for (int i=1;i<=m;i++)
{
    minVal = min(Search(i,1,n,r), minVal);
}

//x and y are start and end of array:
decimal Search(i,x,y,r)
{
   if (i/x > r)
      return i/x - r;

   decimal middle1 = i/Cill((x+y)/2); 
   decimal middle2 = i/Roof((x+y)/2);

   decimal dist = min(middle1,middle2)

   decimal searchResult = 100000;

   if( middle > r)
     searchResult = Search (i, x, cill((x+y)/2),r)
  else
     searchResult = Search(i, roof((x+y)/2), y,r)

  if  (searchResult < dist)
     dist = searchResult;

  return dist;
}

den Index als Hausaufgabe für den Leser zu finden.

Beschreibung: Ich denke, Sie können verstehen, was ist die Idee von Code, aber lassen Sie eine Spur von einer for-Schleife: wenn i=1:

sollten Sie innerhalb der folgenden Nummern suchen: 1,1/2,1/3,1/4,....,1/n Sie überprüfen die Zahl mit (1,1/cill(n/2)) und (1/floor(n/2), 1/n) und führen eine ähnliche binäre Suche durch, um die kleinste Zahl zu finden.

Diese for-Schleife sollte für alle Elemente durchgeführt werden, damit sie erledigt werden kann m Zeit. und in jeder Zeit dauert es O(log(n)). diese Funktion kann durch einige mathematische Regeln verbessert werden, aber es wird kompliziert sein, ich überspringe es.