true - while python 3

Python while loop nunca se detiene aunque debería

Question

He estado pasando por algunos ejercicios de un libro sobre algoritmos (con énfasis en Python), y tengo un comportamiento extraño cuando trato de resolver un cierto problema. El ejercicio es bastante directo y el objetivo es generar un entero aleatorio k partir del range(n) , y luego ubicar este número a través de una secuencia de preguntas "sí / no". El siguiente código funciona siempre que n no sea demasiado grande, pero cuando lo hago obtengo un ciclo infinito. Pero esto no debería suceder porque, en el peor de los casos, step_size eventualmente step_size a uno y la position se arrastrará hacia el valor de k hasta la position == k .

Cuando step_size y position parece que la position no se actualiza cuando se vuelve demasiado grande, así que supongo que tiene algo que ver con el valor aproximado y truncado (esta es la razón por la que traté de lanzarlo explícitamente como long , que de hecho no puede estar haciendo nada). Ciertas partes menores del código son innecesarias, pero quería que funcionaran para general n . ¿Alguna idea sobre lo que está pasando (probablemente tendrá que aumentar n para obtener el comportamiento del que estoy hablando)?

from random import randrange
from math import ceil

n = 10**15
k = randrange(n)

success = False
step_size = ceil(n / 2.0)
position = long(ceil(n / 2.0))

print(k)

while success == False:
    if position == k:
        success = True
        print(str(int(position)) + '' is the value of k.'')
    elif k < position:
        step_size = ceil(step_size / 2.0)
        position -= step_size
        print(step_size, position)
    else:
        step_size = ceil(step_size / 2.0)
        position += step_size
        print(step_size, position)

Answer 1

Necesita usar la position += long(step_size) y la position -= long(step_size)

  if position == k:
        success = True
        print(str((position)) + '' is the value of k.'')
    elif k < position:
        step_size = ceil(step_size / 2.0)
        position -= long(step_size)
        print(step_size, position,k)
    else:
        step_size = ceil(step_size / 2.0)
        position += long(step_size)
        print(step_size, position)

Si no te position , será un flotador no muy largo.

Con el cambio para n = 10 ** 200 obtenemos un valor de:

11008769984569663730780658772914869218303604494435631537943840906720756507580926318660187453313745419228469341648307070867052432521026422402953409000922062458195678772749579263632191432518529106302726
11008769984569663730780658772914869218303604494435631537943840906720756507580926318660187453313745419228469341648307070867052432521026422402953409000922062458195678772749579263632191432518529106302726 is the value of k.

Answer 2

Te encuentras con problemas de precisión. Asegúrese de que sus valores siempre se representen como enteros (no como flotantes). Los enteros de Python tienen una precisión arbitraria, pero los números de coma flotante no.