¿El juego" adivina el número " para números racionales arbitrarios?

Tomemos los números racionales, en forma reducida, y escríbalos en orden primero del denominador, luego del numerador.

1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, ...

Nuestra primera suposición será 1/2. Luego iremos a lo largo de la lista hasta que tengamos 3 en nuestro rango. Entonces tomaremos 2 conjeturas para buscar esa lista. Luego iremos a lo largo de la lista hasta que tengamos 7 en nuestro rango restante. Luego tomaremos 3 conjeturas para buscar en esa lista. Y así sucesivamente.

En n pasos cubriremos las primeras 2O(n) posibilidades, que está en el orden de magnitud de la eficiencia que estabas buscando.

Actualización: La gente no entendió el razonamiento detrás de esto. El razonamiento es simple. Sabemos cómo caminar un árbol binario de manera eficiente. Hay O(n2) fracciones con máximo denominador n. Por lo tanto, podríamos buscar hasta cualquier tamaño de denominador en pasos O(2*log(n)) = O(log(n)). El problema es que tenemos un número infinito de posibles racionales para buscar. Así que no podemos alinearlos, ordenarlos., y empezar a buscar.

Por lo tanto, mi idea era alinear unos pocos, buscar, alinear más, buscar, y así sucesivamente. Cada vez que nos alineamos más nos alineamos alrededor del doble de lo que hicimos la última vez. Así que necesitamos una conjetura más que la última vez. Por lo tanto, nuestro primer pase utiliza 1 conjetura para atravesar 1 racional posible. Nuestro segundo utiliza 2 conjeturas para atravesar 3 posibles racionales. Nuestra tercera usa 3 conjeturas para atravesar 7 posibles racionales. Y nuestro k'th utiliza k conjeturas para atravesar 2k-1 posible racional. Para cualquier racional m/n en particular, eventualmente terminará poniendo ese racional en una lista bastante grande que sabe cómo hacer una búsqueda binaria de manera eficiente.

Si hiciéramos búsquedas binarias, y luego ignoráramos todo lo que habíamos aprendido cuando agarramos más racionales, entonces pondríamos todos los racionales hasta e incluyendo m/n en O(log(n)) pases. (Eso es porque en ese punto vamos a llegar a un pase con suficientes racionales para incluir todos los racionales hasta e incluyendo m/n.) Pero cada uno pass toma más conjeturas, por lo que sería O(log(n)2) conjeturas.

Sin embargo en realidad lo hacemos mucho mejor que eso. Con nuestra primera suposición, eliminamos la mitad de los racionales en nuestra lista como demasiado grandes o pequeños. Nuestras próximas dos conjeturas no cortan el espacio en cuartos, pero no se alejan demasiado de él. Nuestras próximas 3 conjeturas de nuevo no cortan el espacio en octavos, pero no se alejan demasiado de él. Y así sucesivamente. Cuando lo juntas, estoy convencido de que el resultado es que encuentras m/n en O(log(n)) pasos. Aunque en realidad no tengo pruebas.

Pruébelo: Aquí está el código para generar las conjeturas para que pueda jugar y ver qué tan eficiente es.

#! /usr/bin/python

from fractions import Fraction
import heapq
import readline
import sys

def generate_next_guesses (low, high, limit):
    upcoming = [(low.denominator + high.denominator,
                 low.numerator + high.numerator,
                 low.denominator, low.numerator,
                 high.denominator, high.numerator)]
    guesses = []
    while len(guesses) < limit:
        (mid_d, mid_n, low_d, low_n, high_d, high_n) = upcoming[0]
        guesses.append(Fraction(mid_n, mid_d))
        heapq.heappushpop(upcoming, (low_d + mid_d, low_n + mid_n,
                                     low_d, low_n, mid_d, mid_n))
        heapq.heappush(upcoming, (mid_d + high_d, mid_n + high_n,
                                  mid_d, mid_n, high_d, high_n))
    guesses.sort()
    return guesses

def ask (num):
    while True:
        print "Next guess: {0} ({1})".format(num, float(num))
        if 1 < len(sys.argv):
            wanted = Fraction(sys.argv[1])
            if wanted < num:
                print "too high"
                return 1
            elif num < wanted:
                print "too low"
                return -1
            else:
                print "correct"
                return 0

        answer = raw_input("Is this (h)igh, (l)ow, or (c)orrect? ")
        if answer == "h":
            return 1
        elif answer == "l":
            return -1
        elif answer == "c":
            return 0
        else:
            print "Not understood.  Please say one of (l, c, h)"

guess_size_bound = 2
low = Fraction(0)
high = Fraction(1)
guesses = [Fraction(1,2)]
required_guesses = 0
answer = -1
while 0 != answer:
    if 0 == len(guesses):
        guess_size_bound *= 2
        guesses = generate_next_guesses(low, high, guess_size_bound - 1)
    #print (low, high, guesses)
    guess = guesses[len(guesses)/2]
    answer = ask(guess)
    required_guesses += 1
    if 0 == answer:
        print "Thanks for playing!"
        print "I needed %d guesses" % required_guesses
    elif 1 == answer:
        high = guess
        guesses[len(guesses)/2:] = []
    else:
        low = guess
        guesses[0:len(guesses)/2 + 1] = []

Como ejemplo para probarlo probé 101/1024 (0.0986328125) y encontré que tomó 20 conjeturas para encontrar la respuesta. Intenté 0.98765 y me tomó 45 conjeturas. Probé 0.0123456789 y necesité 66 conjeturas y alrededor de un segundo para generarlas. (Nota, si llama al programa con un número racional como argumento, llenará todas las conjeturas para usted. Esta es una conveniencia muy útil.)

¡Lo tengo! Lo que necesita hacer es usar una búsqueda paralela con bisección y fracciones continuas.

La bisección le dará un límite hacia un número real específico, representado como una potencia de dos, y las fracciones continuas tomarán el número real y encontrarán el número racional más cercano.

La forma de ejecutarlos en paralelo es la siguiente.

En cada paso, tienes l y u siendo los límites inferior y superior de la bisección. La idea es, usted tiene una opción entre la reducción a la mitad del rango de bisección, y la adición de un término adicional como una representación de fracción continua. Cuando tanto l como u tienen el mismo término siguiente como una fracción continua, entonces toma el siguiente paso en la búsqueda de fracciones continuas y realiza una consulta usando la fracción continua. De lo contrario, se reduce a la mitad el rango usando bisección.

Dado que ambos métodos aumentan el denominador por al menos un factor constante (la bisección pasa por factores de 2, las fracciones continuas pasan por al menos una factor de phi = (1+sqrt(5))/2), esto significa que su búsqueda debe ser O(log(q)). (Puede haber cálculos continuos repetidos de fracciones, por lo que puede terminar como O(log(q)^2).)

Nuestra búsqueda continua de fracciones necesita redondear al entero más cercano, no usar piso (esto es más claro a continuación).

Lo anterior es una especie de manual. Usemos un ejemplo concreto de r = 1/31:

1. L = 0, u = 1, query = 1/2. 0 no es expresable como una fracción continua, por lo que usamos la búsqueda binaria hasta que l != 0.

2. L = 0, u = 1/2, query = 1/4.

3. L = 0, u = 1/4, query = 1/8.

4. L = 0, u = 1/8, query = 1/16.

5. L = 0, u = 1/16, query = 1/32.

6. L = 1/32, u = 1/16. Ahora 1 / l = 32, 1 / u = 16, estos tienen diferentes repeticiones cfrac, así que sigue bisectando., query = 3/64.

7. L = 1/32, u = 3/64, consulta = 5/128 = 1/25.6

8. L = 1/32, u = 5/128, query = 9/256 = 1/28.4444....

9. L = 1/32, u = 9/256, query = 17/512 = 1/30.1176... (redondear a 1/30)

10. L = 1/32, u = 17/512, query = 33/1024 = 1/31.0303... (redondear a 1/31)

11. L = 33/1024, u = 17/512, query = 67/2048 = 1/30.5672... (redondear a 1/31)

12. L = 33/1024, u = 67/2048. En este punto, tanto l como u tienen el mismo término de fracción continua 31, por lo que ahora usamos una suposición de fracción continua. consulta = 1/31.

¡ÉXITO!

Para otro ejemplo usemos 16/113 (= 355/113 - 3 donde 355/113 es bastante cercano a pi).

[para continuar, tengo que ir a alguna parte]

En una reflexión posterior, las fracciones continuas son el camino a seguir, no importa la bisección, excepto para determinar el siguiente término. Más cuando vuelva.

Creo que encontré un algoritmo O(log^2(p + q)).

Para evitar confusiones en el siguiente párrafo, una "consulta" se refiere a cuando el adivino le da al retador una conjetura, y el retador responde "más grande" o "más pequeño". Esto me permite reservar la palabra "adivinar" para otra cosa, una conjetura para p + q que no se le pide directamente al retador.

La idea es encontrar primero p + q, usando el algoritmo que describes en tu pregunta: adivina un valor k, si k es demasiado pequeño, duplícalo y intentarlo. Luego, una vez que tenga un límite superior e inferior, haga una búsqueda binaria estándar. Esto toma consultas O(log (p+q)T), donde T es un límite superior para el número de consultas que se necesita para verificar una conjetura. Vamos a encontrar T.

Queremos comprobar todas las fracciones r/s con r + s

Nunca vamos a adivinar un valor de k mayor que 2(p + q). Por lo tanto podemos tomar T = O(log(p+q)).

Cuando adivinemos el valor correcto para k (es decir, k = p + q), enviaremos la consulta p/q al retador en el curso de verificar nuestra conjetura para k, y ganaremos el juego.

El número total de consultas es entonces O(log^2(p + q)).

Bien, creo que me di cuenta de una O(lg² q) algoritmo para este problema que se basa en la visión más excelente de Jason S sobre el uso de fracciones continuas. Pensé en desarrollar el algoritmo hasta aquí para que tengamos una solución completa, junto con un análisis de tiempo de ejecución.

La intuición detrás del algoritmo es que cualquier número racional p / q dentro del rango se puede escribir como

A₀ + 1 / (a₁ + 1 / (a₂ + 1 / (a₃ + 1 / ...))

Para las opciones apropiadas de a _i. Esto se llama fracción continua. Más importante aún, aunque estos a_i se pueden derivar ejecutando el algoritmo euclidiano en el numerador y denominador. Por ejemplo, supongamos que queremos representar 11/14 de esta manera. Comenzamos señalando que 14 entra once veces cero, por lo que una aproximación bruta de 11/14 sería

0 = 0

Ahora, supongamos que tomamos la recíproco de esta fracción para obtener 14/11 = 1 ³/₁₁. Así que si escribimos

0 + (1 / 1) = 1

Obtenemos una aproximación ligeramente mejor a 11/14. Ahora que nos quedamos con 3 / 11, podemos tomar el recíproco de nuevo para obtener 11/3 = 3 ²/₃, por lo que podemos considerar

0 + (1 / (1 + 1/3)) = 3/4

Que es otra buena aproximación a 11/14. Ahora, tenemos 2/3, así que considere el recíproco, que es 3/2 = 1 ¹/₂. Si luego escribimos

0 + (1 / (1 + 1/(3 + 1/1))) = 5/6

Obtenemos otra buena aproximación a 11/14. Finalmente, nos quedamos con 1/2, cuyo recíproco es 2/1. Si finalmente escribimos

0 + (1 / (1 + 1/(3 + 1/(1 + 1/2)))) = (1 / (1 + 1/(3 + 1/(3/2)))) = (1 / (1 + 1/(3 + 2/3)))) = (1 / (1 + 1/(11/3)))) = (1 / (1 + 3/11)) = 1 / (14/11) = 11/14

Que es exactamente la fracción que queríamos. Por otra parte, mira el secuencia de coeficientes que terminamos usando. Si se ejecuta el algoritmo euclidiano extendido en 11 y 14, se obtiene que

11 = 0 x 14 + 11 > > a0 = 0 14 = 1 x 11 + 3 > > a1 = 1 11 = 3 x 3 + 2 > > a2 = 3 3 = 2 x 1 + 1 > > a3 = 2

Resulta que (usando más matemáticas de las que actualmente sé hacer!) que esto no es una coincidencia y que los coeficientes en la fracción continua de p/q siempre se forman usando el algoritmo euclidiano extendido. Esto es genial, porque nos dice dos cosas:

1. Puede haber como máximo coeficientes O(lg (p + q)), porque el algoritmo euclidiano siempre termina en estos muchos pasos, y
2. Cada coeficiente es máximo{p, q}.

Dados estos dos hechos, podemos llegar a un algoritmo para recuperar cualquier número racional p / q, no solo aquellos entre 0 y 1, aplicando el algoritmo general para adivinar enteros arbitrarios n uno a la vez para recuperar todos los coeficientes en la fracción continua para p / q. Por ahora, sin embargo, solo nos preocuparemos por los números en el rango (0, 1], ya que la lógica para manejar números racionales arbitrarios se puede hacer fácilmente dado esto como una subrutina.

Como primer paso, supongamos que queremos encontrar el mejor valor de un₁ para que 1 / a₁ está lo más cerca posible de p / q y a₁ es un entero. Para hacer esto, podemos ejecutar nuestro algoritmo para adivinar arbitrariamente enteros, tomando el recíproco cada vez. Después de hacer esto, una de dos cosas habrá sucedido. Primero, podríamos por pura coincidencia descubrir que p / q = 1 / k para algún entero k, en cuyo caso hemos terminado. Si no, encontraremos que p / q está intercalado entre 1/(a₁ - 1) y 1 / a₀ para algunos un₁. Cuando hacemos esto, entonces empezamos a trabajar en la fracción continua un nivel más profundo mediante la búsqueda de la a₂ tal que p / q está entre 1 / (a₁ + 1/a₂) y 1 / (a)₁ + 1/( a₂ + 1)). Si mágicamente encontramos p / q, eso es genial! De lo contrario, vamos un nivel más abajo en la fracción continua. Eventualmente, encontraremos el número de esta manera, y no puede tomar mucho tiempo. Cada búsqueda binaria para encontrar un coeficiente toma como máximo O(lg (p + q)) tiempo, y hay como máximo O(lg(p + q)) niveles para la búsqueda, por lo que solo necesitamos O (lg²(p + q)) operaciones aritméticas y sondas para recuperar p/q.

Un detalle que quiero señalar es que tenemos que hacer un seguimiento de si estamos en un nivel impar o un nivel par al hacer la búsqueda porque cuando emparedamos p/q entre dos fracciones continuas, necesitamos saber si el coeficiente que estábamos buscando era la fracción superior o inferior. Declararé sin prueba que para un _i con i impar quieres usar la parte superior de los dos números, y con un _i incluso usas la parte inferior de los dos números.

Estoy casi 100% seguro de que este algoritmo funciona. Me voy para tratar de escribir una prueba más formal de esto en la que llene todos los vacíos en este razonamiento, y cuando lo haga, publicaré un enlace aquí.

Gracias a todos por contribuir con la información necesaria para que esta solución funcione, especialmente Jason S por sugerir una búsqueda binaria sobre fracciones continuas.

Recuerde que cualquier número racional en (0, 1) puede representarse como una suma finita de fracciones unitarias distintas (positivas o negativas). Por ejemplo, 2/3 = 1/2 + 1/6 y 2/5 = 1/2 - 1/10. Puede usar esto para realizar una búsqueda binaria directa.

Aquí hay otra manera de hacerlo. Si hay suficiente interés, intentaré completar los detalles esta noche, pero no puedo ahora porque tengo responsabilidades familiares. Aquí hay un fragmento de una implementación que debería explicar el algoritmo:

low = 0
high = 1
bound = 2
answer = -1
while 0 != answer:
    mid = best_continued_fraction((low + high)/2, bound)
    while mid == low or mid == high:
        bound += bound
        mid = best_continued_fraction((low + high)/2, bound)
    answer = ask(mid)
    if -1 == answer:
        low = mid
    elif 1 == answer:
        high = mid
    else:
        print_success_message(mid)

Y aquí está la explicación. Lo que best_continued_fraction(x, bound) debe hacer es encontrar la última fracción continua aproximación a x con el denominador a lo sumo bound. Este algoritmo tomará pasos de polylog para completar y encuentra muy bueno (aunque no siempre la mejor) aproximaciones. Así que para cada bound obtendremos algo cercano a una búsqueda binaria a través de todas las fracciones posibles de ese tamaño. Ocasionalmente no encontraremos una fracción en particular hasta que aumentemos el límite más de lo que deberíamos, pero no estaremos lejos.

Así que ahí lo tienen. Un número logarítmico de preguntas encontradas con el trabajo de polylog.

Actualización: Y código de trabajo completo.

#! /usr/bin/python

from fractions import Fraction
import readline
import sys

operations = [0]

def calculate_continued_fraction(terms):
    i = len(terms) - 1
    result = Fraction(terms[i])
    while 0 < i:
        i -= 1
        operations[0] += 1
        result = terms[i] + 1/result
    return result

def best_continued_fraction (x, bound):
    error = x - int(x)
    terms = [int(x)]
    last_estimate = estimate = Fraction(0)
    while 0 != error and estimate.numerator < bound:
        operations[0] += 1
        error = 1/error
        term = int(error)
        terms.append(term)
        error -= term
        last_estimate = estimate
        estimate = calculate_continued_fraction(terms)
    if estimate.numerator < bound:
        return estimate
    else:
        return last_estimate

def ask (num):
    while True:
        print "Next guess: {0} ({1})".format(num, float(num))
        if 1 < len(sys.argv):
            wanted = Fraction(sys.argv[1])
            if wanted < num:
                print "too high"
                return 1
            elif num < wanted:
                print "too low"
                return -1
            else:
                print "correct"
                return 0

        answer = raw_input("Is this (h)igh, (l)ow, or (c)orrect? ")
        if answer == "h":
            return 1
        elif answer == "l":
            return -1
        elif answer == "c":
            return 0
        else:
            print "Not understood.  Please say one of (l, c, h)"

ow = Fraction(0)
high = Fraction(1)
bound = 2
answer = -1
guesses = 0
while 0 != answer:
    mid = best_continued_fraction((low + high)/2, bound)
    guesses += 1
    while mid == low or mid == high:
        bound += bound
        mid = best_continued_fraction((low + high)/2, bound)
    answer = ask(mid)
    if -1 == answer:
        low = mid
    elif 1 == answer:
        high = mid
    else:
        print "Thanks for playing!"
        print "I needed %d guesses and %d operations" % (guesses, operations[0])

Parece un poco más eficiente en conjeturas que el solución anterior, y hace muchas menos operaciones. Para 101/1024 requirió 19 conjeturas y 251 operaciones. Para .98765 necesitaba 27 conjeturas y 623 operaciones. Para 0.0123456789 requirió 66 conjeturas y 889 operaciones. Y para risitas y sonrisas, para 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (eso es 10 copias de la anterior) se requiere 665 conjeturas y 23289 operaciones.

Puede ordenar los números racionales en un intervalo dado por ejemplo el par (denominador, numerador). A continuación, para jugar el juego se puede

1. Encuentre el intervalo [0, N] usando el enfoque de paso doble
2. Dado un intervalo [a, b] dispara por el racional con el denominador más pequeño en el intervalo que es el más cercano al centro del intervalo

Esto es sin embargo probablemente todavía O(log(num/den) + den) (no estoy seguro y es demasiado temprano en la mañana aquí para hacerme pensar claramente ;-) )