algorithm math puzzle rational-numbers

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



math puzzle (8)

¡Lo tengo! Lo que debe 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.

Cómo los ejecutas en paralelo es el siguiente.

En cada paso, tienes l y u los límites inferior y superior de la bisección. La idea es que puede elegir entre dividir por dos el rango de bisección y agregar un término adicional como representación de fracción continua. Cuando ambos, l y u tienen el mismo término siguiente que una fracción continua, se da el siguiente paso en la búsqueda continua de fracciones y se realiza una consulta con la fracción continua. De lo contrario, reduce a la mitad el rango con la bisección.

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

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

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

  1. l = 0, u = 1, consulta = 1/2. 0 no se puede expresar como una fracción continua, por lo que usamos la búsqueda binaria hasta l! = 0.

  2. l = 0, u = 1/2, consulta = 1/4.

  3. l = 0, u = 1/4, consulta = 1/8.

  4. l = 0, u = 1/8, consulta = 1/16.

  5. l = 0, u = 1/16, consulta = 1/32.

  6. l = 1/32, u = 1/16. Ahora 1 / l = 32, 1 / u = 16, estos tienen diferentes representantes de cfrac, así que sigue biseccionando., Query = 3/64.

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

  8. l = 1/32, u = 5/128, consulta = 9/256 = 1 / 28.4444 ....

  9. l = 1/32, u = 9/256, consulta = 17/512 = 1 / 30.1176 ... (alrededor de 1/30)

  10. l = 1/32, u = 17/512, consulta = 33/1024 = 1 / 31.0303 ... (de 1/31 a 1/31)

  11. l = 33/1024, u = 17/512, consulta = 67/2048 = 1 / 30.5672 ... (de 1/31 a 1/31)

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

¡ÉXITO!

Para otro ejemplo, usemos 16/113 (= 355/113 - 3 donde 355/113 está muy cerca de pi).

[Continuará, tengo que ir a algún lado]

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

Una vez recibí lo siguiente como una pregunta de entrevista:

Estoy pensando en un entero positivo n. Propón un algoritmo que pueda adivinarlo en consultas O (lg n). Cada consulta es la que elija, y responderé "inferior", "superior" o "correcta".

Este problema se puede resolver mediante una búsqueda binaria modificada, en la que se enumeran las potencias de dos hasta que encuentre una que exceda n, luego ejecute una búsqueda binaria estándar sobre ese rango. Lo que creo que es tan genial acerca de esto es que puedes buscar un espacio infinito para un número en particular más rápido que la fuerza bruta.

La pregunta que tengo, sin embargo, es una ligera modificación de este problema. En lugar de elegir un número entero positivo, supongamos que selecciono un número racional arbitrario entre cero y uno. Mi pregunta es: ¿qué algoritmo puede usar para determinar de manera más eficiente qué número racional seleccioné?

En este momento, la mejor solución que tengo puede encontrar p / q en el máximo de O (q) tiempo al caminar implícitamente el árbol Stern-Brocot , un árbol binario de búsqueda sobre todos los racionales. Sin embargo, esperaba obtener un tiempo de ejecución más cercano al tiempo de ejecución que obtuvimos para el caso entero, tal vez algo así como O (lg (p + q)) o O (lg pq). ¿Alguien sabe de una forma de obtener este tipo de tiempo de ejecución?

Inicialmente consideré usar una búsqueda binaria estándar del intervalo [0, 1], pero esto solo encontrará números racionales con una representación binaria no repetitiva, que omite casi todos los racionales. También pensé en usar alguna otra forma de enumerar los racionales, pero parece que no puedo encontrar una forma de buscar en este espacio, dado que solo hay comparaciones mayores / iguales / menos.

Aquí hay otra forma de hacerlo. Si hay interés suficiente, trataré de completar los detalles esta noche, pero no puedo hacerlo ahora porque tengo responsabilidades familiares. Aquí hay un trozo 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) debería hacer es encontrar la última aproximación de fracción continua a x con el denominador a lo máximo. Este algoritmo tomará pasos de Polylog para completar y encuentra muy buenas (aunque no siempre las mejores) aproximaciones. Por lo tanto, para cada bound obtendremos algo parecido a una búsqueda binaria a través de todas las fracciones posibles de ese tamaño. Ocasionalmente no encontraremos una fracción particular hasta que aumentemos el límite más de lo que deberíamos, pero no estaremos lejos.

Entonces ahí lo tienes. Se encontró un número logarítmico de preguntas con el trabajo de polígono.

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 suposiciones que la solución anterior, y realiza muchas menos operaciones. Para 101/1024 requirió 19 conjeturas y 251 operaciones. Para .98765, necesitó 27 conjeturas y 623 operaciones. Para 0.0123456789 requirió 66 conjeturas y 889 operaciones. And for giggles and grins, for 0.0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 (that''s 10 copies of the previous one) it required 665 guesses and 23289 operations.

Bien, creo que descubrí un algoritmo O (lg 2 q) para este problema que se basa en la más excelente idea de Jason S sobre el uso de fracciones continuas. Pensé que puliría el algoritmo todo el camino hasta aquí para tener 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 puede escribirse como

a 0 + 1 / (a 1 + 1 / (a 2 + 1 / (a 3 + 1 / ...))

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

0 = 0

Ahora, supongamos que tomamos el recíproco de esta fracción para obtener 14/11 = 1 3/11. Entonces si escribimos

0 + (1/1) = 1

Obtenemos una aproximación un poco mejor al 11/14. Ahora que nos quedan 3/11, podemos tomar el recíproco nuevamente para obtener 11/3 = 3 2/3, así que podemos considerar

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

Lo cual es otra buena aproximación al 11/14. Ahora, tenemos 2/3, así que considere el recíproco, que es 3/2 = 1 1/2. Si luego escribimos

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

Tenemos otra buena aproximación al 11/14. Finalmente, nos queda 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. Además, observe la secuencia de coeficientes que terminamos usando. Si ejecuta el algoritmo euclidiano extendido en 11 y 14, lo obtiene

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 ahora 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 muchos pasos, y
  2. Cada coeficiente es como máximo max {p, q}.

Dados estos dos hechos, podemos encontrar un algoritmo para recuperar cualquier número racional p / q, no solo aquellos entre 0 y 1, aplicando el algoritmo general para adivinar números enteros arbitrarios n uno a la vez para recuperar todos los coeficientes la fracción continua para p / q. Por ahora, sin embargo, 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 a 1 para que 1 / a 1 esté lo más cerca posible de p / qy a 1 sea ​​un número entero. Para hacer esto, podemos simplemente ejecutar nuestro algoritmo para adivinar números enteros arbitrarios, tomando el recíproco cada vez. Después de hacer esto, una de dos cosas habrá sucedido. En primer lugar, podríamos descubrir, por pura coincidencia, que p / q = 1 / k para un entero k, en cuyo caso hemos terminado. De lo contrario, veremos que p / q está intercalado entre 1 / (a 1 - 1) y 1 / a 0 para algunos a 1 . Cuando hacemos esto, entonces comenzamos a trabajar en la fracción continua un nivel más profundo al encontrar el a 2 tal que p / q está entre 1 / (a 1 + 1 / a 2 ) y 1 / (a 1 + 1 / (a 2 + 1)). Si mágicamente encontramos p / q, ¡eso es genial! De lo contrario, seguiremos 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 2 (p + q)) operaciones aritméticas y sondeos para recuperar p / q.

Un detalle que quiero señalar es que debemos hacer un seguimiento de si estamos en un nivel impar o un nivel parejo cuando realizamos la búsqueda, porque cuando intercalamos p / q entre dos fracciones continuas, necesitamos saber si el coeficiente lo que buscábamos era la fracción superior o inferior. Declararé sin pruebas que para una i con i impar quieres usar la parte superior de los dos números, y con una i incluso usas el menor de los dos números.

Estoy casi 100% seguro de que este algoritmo funciona. Voy a tratar de escribir una prueba más formal de esto en la que complete todas las lagunas en este razonamiento, y cuando lo haga, publicaré un enlace aquí.

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

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

Para evitar confusiones en el párrafo siguiente, una "consulta" se refiere a cuando el adivinador adivina al rival y el rival responde "más grande" o "más pequeño". Esto me permite reservar la palabra "adivinar" para otra cosa, una adivinanza para p + q que no se solicita 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, doblalo y vuelve a intentarlo. Luego, una vez que tenga un límite superior e inferior, realice una búsqueda binaria estándar. Esto requiere consultas O (log (p + q) T), donde T es un límite superior para el número de consultas que se necesitan para verificar una conjetura. Encontremos T.

Queremos verificar todas las fracciones r / s con r + s <= k, y doble k hasta que k sea suficientemente grande. Tenga en cuenta que hay fracciones O (k ^ 2) que necesita comprobar para un valor dado de k. Construya un árbol de búsqueda binaria equilibrado que contenga todos estos valores, luego búsquelo para determinar si p / q está en el árbol. Toma O (log k ^ 2) = O (log k) consultas para confirmar que p / q no está en el árbol.

Nunca adivinaremos 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 ganar el juego.

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

De acuerdo, aquí está mi respuesta usando fracciones continuas solo.

Primero vamos a obtener un poco de terminología aquí.

Deje X = p / q sea la fracción desconocida.

Deje Q (X, p / q) = signo (X - p / q) sea la función de consulta: si es 0, hemos adivinado el número, y si es +/- 1 que nos indica el signo de nuestro error .

La notación convencional para fracciones continuas es A = [a 0 ; a 1 , a 2 , a 3 , ... a k ]

= a 0 + 1 / (a 1 + 1 / (a 2 + 1 / (a 3 + 1 / (... + 1 / a k ) ...)))

Seguiremos el siguiente algoritmo para 0 <p / q <1.

  1. Inicializa Y = 0 = [0], Z = 1 = [1], k = 0.

  2. Bucle externo : las condiciones previas son las siguientes:

    • Y y Z son fracciones continuas de k + 1 términos que son idénticos, excepto en el último elemento, donde difieren en 1, de modo que Y = [y 0 ; y 1 , y 2 , y 3 , ... y k ] y Z = [y 0 ; y 1 , y 2 , y 3 , ... y k + 1]

    • (-1) k (YX) <0 <(-1) k (ZX), o en términos más simples, para k par, Y <X <Z y para k impar, Z <X <Y.

  3. Extienda el grado de la fracción continua en 1 paso sin cambiar los valores de los números. En general, si los últimos términos son y k e y k + 1, lo cambiamos a [... y k , y k + 1 = ∞] y [... y k , z k + 1 = 1]. Ahora aumenta k por 1.

  4. Bucles internos : Esto es esencialmente lo mismo que la pregunta de entrevista de @ templatetypedef sobre los enteros. Hacemos una búsqueda binaria en dos fases para acercarnos:

  5. Lazo interno 1 : y k = ∞, z k = a, y X está entre Y y Z.

  6. Tercer término de Double Z: calcule M = Z pero con m k = 2 * a = 2 * z k .

  7. Consulta el número desconocido: q = Q (X, M).

  8. Si q = 0, tenemos nuestra respuesta y vamos al paso 17.

  9. Si q y Q (X, Y) tienen signos opuestos, significa que X está entre Y y M, entonces configure Z = M y vaya al paso 5.

  10. De lo contrario, configure Y = M y vaya al siguiente paso:

  11. Bucle interno 2. y k = b, z k = a, y X está entre Y y Z.

  12. Si a y b difieren en 1, cambie Y y Z, vaya al paso 2.

  13. Realice una búsqueda binaria: calcule M donde m k = piso ((a + b) / 2, y consulta q = Q (X, M).

  14. Si q = 0, hemos terminado y vamos al paso 17.

  15. Si q y Q (X, Y) tienen signos opuestos, significa que X está entre Y y M, entonces configure Z = M y vaya al paso 11.

  16. De lo contrario, q y Q (X, Z) tienen signos opuestos, significa que X está entre Z y M, por lo tanto, configure Y = M y vaya al paso 11.

  17. Hecho: X = M.

Un ejemplo concreto para X = 16/113 = 0.14159292

Y = 0 = [0], Z = 1 = [1], k = 0 k = 1: Y = 0 = [0; &#8734;] < X, Z = 1 = [0; 1] > X, M = [0; 2] = 1/2 > X. Y = 0 = [0; &#8734;], Z = 1/2 = [0; 2], M = [0; 4] = 1/4 > X. Y = 0 = [0; &#8734;], Z = 1/4 = [0; 4], M = [0; 8] = 1/8 < X. Y = 1/8 = [0; 8], Z = 1/4 = [0; 4], M = [0; 6] = 1/6 > X. Y = 1/8 = [0; 8], Z = 1/6 = [0; 6], M = [0; 7] = 1/7 > X. Y = 1/8 = [0; 8], Z = 1/7 = [0; 7] --> the two last terms differ by one, so swap and repeat outer loop. k = 2: Y = 1/7 = [0; 7, &#8734;] > X, Z = 1/8 = [0; 7, 1] < X, M = [0; 7, 2] = 2/15 < X Y = 1/7 = [0; 7, &#8734;], Z = 2/15 = [0; 7, 2], M = [0; 7, 4] = 4/29 < X Y = 1/7 = [0; 7, &#8734;], Z = 4/29 = [0; 7, 4], M = [0; 7, 8] = 8/57 < X Y = 1/7 = [0; 7, &#8734;], Z = 8/57 = [0; 7, 8], M = [0; 7, 16] = 16/113 = X --> done!

En cada paso de calcular M, el rango del intervalo se reduce. Probablemente sea bastante fácil de probar (aunque no haré esto) que el intervalo se reduce por un factor de al menos 1 / sqrt (5) en cada paso, lo que mostraría que este algoritmo es O (log q) pasos.

Tenga en cuenta que esto se puede combinar con la pregunta de entrevista original de templatetypedef y aplicarlo a cualquier número racional p / q, no solo entre 0 y 1, primero calculando Q (X, 0), luego para enteros positivos / negativos, acotando entre dos consecutivos enteros, y luego usar el algoritmo anterior para la parte fraccionaria.

Cuando tenga la oportunidad, publicaré un programa de Python que implementa este algoritmo.

editar : también, tenga en cuenta que no tiene que calcular la fracción continua en cada paso (que sería O (k), hay aproximaciones parciales a las fracciones continuas que pueden calcular el siguiente paso del paso anterior en O (1). )

edición 2 : definición recursiva de aproximadores parciales:

Si A k = [a 0 ; a 1 , a 2 , a 3 , ... a k ] = p k / q k , luego p k = a k p k-1 + p k-2 , y q k = a k q k-1 + q k-2 . (Fuente: Niven & Zuckerman, 4th ed, Theorems 7.3-7.5. Ver también Wikipedia )

Ejemplo: [0] = 0/1 = p 0 / q 0 , [0; 7] = 1/7 = p 1 / q 1 ; entonces [0; 7, 16] = (16 * 1 + 0) / (16 * 7 + 1) = 16/113 = p 2 / q 2 .

Esto significa que si dos fracciones continuas Y y Z tienen los mismos términos, excepto el último, y la fracción continua excluyendo el último término es p k-1 / q k-1 , entonces podemos escribir Y = (y k p k- 1 + p k-2 ) / ( yk q k-1 + q k-2 ) y Z = (z k p k-1 + p k-2 ) / (z k q k-1 + q k-2 ) Debería ser posible mostrar a partir de esto que | YZ | disminuye en al menos un factor de 1 / sqrt (5) en cada intervalo más pequeño producido por este algoritmo, pero el álgebra parece estar más allá de mí en este momento. :-(

Aquí está mi programa de Python:

import math # Return a function that returns Q(p0/q0,p/q) # = sign(p0/q0-p/q) = sign(p0q-q0p)*sign(q0*q) # If p/q < p0/q0, then Q() = 1; if p/q < p0/q0, then Q() = -1; otherwise Q()=0. def makeQ(p0,q0): def Q(p,q): return cmp(q0*p,p0*q)*cmp(q0*q,0) return Q def strsign(s): return ''<'' if s<0 else ''>'' if s>0 else ''=='' def cfnext(p1,q1,p2,q2,a): return [a*p1+p2,a*q1+q2] def ratguess(Q, doprint, kmax): # p2/q2 = p[k-2]/q[k-2] p2 = 1 q2 = 0 # p1/q1 = p[k-1]/q[k-1] p1 = 0 q1 = 1 k = 0 cf = [0] done = False while not done and (not kmax or k < kmax): if doprint: print ''p/q=''+str(cf)+''=''+str(p1)+''/''+str(q1) # extend continued fraction k = k + 1 [py,qy] = [p1,q1] [pz,qz] = cfnext(p1,q1,p2,q2,1) ay = None az = 1 sy = Q(py,qy) sz = Q(pz,qz) while not done: if doprint: out = str(py)+''/''+str(qy)+'' ''+strsign(sy)+'' X '' out += strsign(-sz)+'' ''+str(pz)+''/''+str(qz) out += '', interval=''+str(abs(1.0*py/qy-1.0*pz/qz)) if ay: if (ay - az == 1): [p0,q0,a0] = [pz,qz,az] break am = (ay+az)/2 else: am = az * 2 [pm,qm] = cfnext(p1,q1,p2,q2,am) sm = Q(pm,qm) if doprint: out = str(ay)+'':''+str(am)+'':''+str(az) + '' '' + out + ''; M=''+str(pm)+''/''+str(qm)+'' ''+strsign(sm)+'' X '' print out if (sm == 0): [p0,q0,a0] = [pm,qm,am] done = True break elif (sm == sy): [py,qy,ay,sy] = [pm,qm,am,sm] else: [pz,qz,az,sz] = [pm,qm,am,sm] [p2,q2] = [p1,q1] [p1,q1] = [p0,q0] cf += [a0] print ''p/q=''+str(cf)+''=''+str(p1)+''/''+str(q1) return [p1,q1]

y un resultado de muestra para ratguess(makeQ(33102,113017), True, 20) :

p/q=[0]=0/1 None:2:1 0/1 < X < 1/1, interval=1.0; M=1/2 > X None:4:2 0/1 < X < 1/2, interval=0.5; M=1/4 < X 4:3:2 1/4 < X < 1/2, interval=0.25; M=1/3 > X p/q=[0, 3]=1/3 None:2:1 1/3 > X > 1/4, interval=0.0833333333333; M=2/7 < X None:4:2 1/3 > X > 2/7, interval=0.047619047619; M=4/13 > X 4:3:2 4/13 > X > 2/7, interval=0.021978021978; M=3/10 > X p/q=[0, 3, 2]=2/7 None:2:1 2/7 < X < 3/10, interval=0.0142857142857; M=5/17 > X None:4:2 2/7 < X < 5/17, interval=0.00840336134454; M=9/31 < X 4:3:2 9/31 < X < 5/17, interval=0.00379506641366; M=7/24 < X p/q=[0, 3, 2, 2]=5/17 None:2:1 5/17 > X > 7/24, interval=0.00245098039216; M=12/41 < X None:4:2 5/17 > X > 12/41, interval=0.00143472022956; M=22/75 > X 4:3:2 22/75 > X > 12/41, interval=0.000650406504065; M=17/58 > X p/q=[0, 3, 2, 2, 2]=12/41 None:2:1 12/41 < X < 17/58, interval=0.000420521446594; M=29/99 > X None:4:2 12/41 < X < 29/99, interval=0.000246366100025; M=53/181 < X 4:3:2 53/181 < X < 29/99, interval=0.000111613371282; M=41/140 < X p/q=[0, 3, 2, 2, 2, 2]=29/99 None:2:1 29/99 > X > 41/140, interval=7.21500721501e-05; M=70/239 < X None:4:2 29/99 > X > 70/239, interval=4.226364059e-05; M=128/437 > X 4:3:2 128/437 > X > 70/239, interval=1.91492009996e-05; M=99/338 > X p/q=[0, 3, 2, 2, 2, 2, 2]=70/239 None:2:1 70/239 < X < 99/338, interval=1.23789953207e-05; M=169/577 > X None:4:2 70/239 < X < 169/577, interval=7.2514738621e-06; M=309/1055 < X 4:3:2 309/1055 < X < 169/577, interval=3.28550190148e-06; M=239/816 < X p/q=[0, 3, 2, 2, 2, 2, 2, 2]=169/577 None:2:1 169/577 > X > 239/816, interval=2.12389981991e-06; M=408/1393 < X None:4:2 169/577 > X > 408/1393, interval=1.24415093544e-06; M=746/2547 < X None:8:4 169/577 > X > 746/2547, interval=6.80448470014e-07; M=1422/4855 < X None:16:8 169/577 > X > 1422/4855, interval=3.56972657711e-07; M=2774/9471 > X 16:12:8 2774/9471 > X > 1422/4855, interval=1.73982239227e-07; M=2098/7163 > X 12:10:8 2098/7163 > X > 1422/4855, interval=1.15020646951e-07; M=1760/6009 > X 10:9:8 1760/6009 > X > 1422/4855, interval=6.85549088053e-08; M=1591/5432 < X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9]=1591/5432 None:2:1 1591/5432 < X < 1760/6009, interval=3.06364213998e-08; M=3351/11441 < X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1]=1760/6009 None:2:1 1760/6009 > X > 3351/11441, interval=1.45456726663e-08; M=5111/17450 < X None:4:2 1760/6009 > X > 5111/17450, interval=9.53679318849e-09; M=8631/29468 < X None:8:4 1760/6009 > X > 8631/29468, interval=5.6473816179e-09; M=15671/53504 < X None:16:8 1760/6009 > X > 15671/53504, interval=3.11036635336e-09; M=29751/101576 > X 16:12:8 29751/101576 > X > 15671/53504, interval=1.47201634215e-09; M=22711/77540 > X 12:10:8 22711/77540 > X > 15671/53504, interval=9.64157420569e-10; M=19191/65522 > X 10:9:8 19191/65522 > X > 15671/53504, interval=5.70501257346e-10; M=17431/59513 > X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1, 8]=15671/53504 None:2:1 15671/53504 < X < 17431/59513, interval=3.14052228667e-10; M=33102/113017 == X

Dado que Python maneja la matemática de biginteger desde el principio, y este programa usa solo matemática entera (excepto para los cálculos de intervalo), debería funcionar para racionales arbitrarios.

edición 3 : Esquema de la prueba de que esto es O (log q), no O (log ^ 2 q):

Primero note que hasta que se encuentre el número racional, el número de pasos n k para cada nuevo término de fracción continua es exactamente 2b (a_k) -1 donde b (a_k) es el número de bits necesarios para representar a_k = ceil (log2 (a_k) )): es b (a_k) pasos para ampliar la "red" de la búsqueda binaria, yb (a_k) -1 pasos para restringirla). Vea el ejemplo anterior, notará que el número de pasos es siempre 1, 3, 7, 15, etc.

Ahora podemos usar la relación de recurrencia q k = a k q k-1 + q k-2 y la inducción para demostrar el resultado deseado.

Vamos a decirlo de esta manera: que el valor de q después de los pasos de N k = suma (n k ) requeridos para alcanzar el término k tiene un mínimo: q> = A * 2 cN para algunas constantes fijas A, c. (Entonces, para invertir, obtendríamos que el # de pasos N es <= (1 / c) * log 2 (q / A) = O (log q).)

Casos base:

  • k = 0: q = 1, N = 0, entonces q> = 2 N
  • k = 1: para N = 2b-1 pasos, q = a 1 > = 2 b-1 = 2 (N-1) / 2 = 2 N / 2 / sqrt (2).

Esto implica que A = 1, c = 1/2 podría proporcionar los límites deseados. En realidad, q no puede duplicar cada término (contraejemplo: [0; 1, 1, 1, 1, 1] tiene un factor de crecimiento de phi = (1 + sqrt (5)) / 2) entonces usemos c = 1 / 4.

Inducción:

  • para el término k, q k = a k q k-1 + q k-2 . De nuevo, para los n k = 2b-1 pasos necesarios para este término, a k > = 2 b-1 = 2 (n k -1) / 2 .

    Entonces a k q k-1 > = 2 (N k -1) / 2 * q k-1 > = 2 (n k -1) / 2 * A * 2 N k-1 /4 = A * 2 N k / 4 / sqrt (2) * 2 n k / 4 .

Argh: la parte difícil aquí es que si a k = 1, q puede no aumentar mucho para ese término, y necesitamos usar q k-2, pero eso puede ser mucho más pequeño que q k-1 .

Recuerde que cualquier número racional en (0, 1) se puede representar como una suma finita de fracciones de unidades 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.

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 va a ser 1/2 . Luego iremos a lo largo de la lista hasta que tengamos 3 en nuestro rango. Luego 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 esa lista. Y así.

En n pasos, cubriremos las primeras 2 O(n) posibilidades, que están en el orden de magnitud de 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(n 2 ) fracciones con el máximo denominador n . Por lo tanto, podríamos buscar cualquier tamaño de denominador particular en O(2*log(n)) = O(log(n)) pasos. El problema es que tenemos un número infinito de racionales posibles para buscar. Entonces no podemos alinearlos, ordenarlos y comenzar a buscar.

Por lo tanto, mi idea era alinear algunos, buscar, alinear más, buscar, etc. Cada vez que formamos más nos alineamos el doble de lo que hicimos la última vez. Entonces, necesitamos una conjetura más que la última vez. Por lo tanto, nuestro primer pase usa 1 conjetura para atravesar 1 posible racional. Nuestro segundo usa 2 conjeturas para atravesar 3 posibles racionales. Nuestro tercero usa 3 conjeturas para atravesar 7 racionales posibles. Y nuestro k ''th usa k conjeturas para atravesar 2 k -1 posibles racionales. Para cualquier m/n racional 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, luego ignoramos todo lo que habíamos aprendido cuando tomamos 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 llegaremos a un pase con suficientes racionales para incluir todos los racionales hasta e incluyendo m/n .) Pero cada pasada requiere más suposiciones, por lo que serían 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 por ser demasiado grandes o pequeños. Nuestras próximas dos conjeturas no recortan el espacio en cuatro, pero no se alejan mucho de él. Nuestras próximas 3 conjeturas nuevamente no reducen el espacio a octavos, pero no se alejan mucho de él. Y así. Cuando lo juntas, estoy convencido de que el resultado es que encuentras m/n en O(log(n)) pasos. Aunque en realidad no tengo una prueba.

Pruébelo: aquí está el código para generar las suposiciones 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 probar intenté 101/1024 (0.0986328125) y encontré que se necesitaron 20 conjeturas para encontrar la respuesta. Intenté 0.98765 y me llevó 45 conjeturas. Intenté 0.0123456789 y necesité 66 conjeturas y aproximadamente un segundo para generarlas. (Tenga en cuenta que si llama al programa con un número racional como argumento, completará todas las conjeturas por usted. Esta es una conveniencia muy útil).

You can sort rational numbers in a given interval by for example the pair (denominator, numerator). Then to play the game you can

  1. Encuentre el intervalo [0, N]utilizando el enfoque de paso doble
  2. Dado un [a, b]lanzamiento de intervalo para 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 muy temprano en la mañana para hacerme pensar claramente ;-))