¿En qué circunstancias termina este procedimiento?

Question

Esta pregunta anterior (esencialmente) se le preguntó por qué el siguiente bucle terminará. (Este es el código de Java, por lo que se supone que estás trabajando con firmado, enteros de 32 bits:)

final int initial    = 2;
final int multiplier = 12381923;

for (int i = initial; i != 0; i += i * multiplier)
    ;

Ziyao Wei es excelente respuesta se explica por qué este proceso termina para esta combinación en particular de un valor inicial y un multiplicador.

Mi pregunta es esta: ¿qué es una condición necesaria y suficiente en initial y multiplier tal que este proceso está garantizado para terminar?

Gracias!

Answer 1

Desde i += i * multiplier es equivalente a i *= (multiplier + 1), las condiciones para la terminación son:

• inicial es cero, y/o
• el multiplicador es un número impar

Puesto que los números impares tienen inversos modulo 2ⁿ, multiplicando por ellos no se puede dar como resultado cero (a menos que sea cero, para empezar). Multiplicar por un número de forma irreversible conjuntos de al menos uno de los bits a cero.

---

Quizás una manera más intuitiva para explicar que viene directamente de binaria la multiplicación.

Al igual que en decimal, un número de sub-resultados se suman. En binario, el sub-resultados son más fáciles de calcular, ya que cuando se trata de calcular el sólo tiene que multiplicar por 0 o 1 (y cambio). Por ejemplo (adaptado de wiki:binary_multiplier para ser modular modulo 2⁴ y con los operandos intercambiar)

  1011
x 1110
======
  1110   (this is 1110 x 1)
  110    (this is 1110 x 1, shifted one position to the left)
  00     (this is 1110 x 0, shifted two positions to the left)
+ 0      (this is 1110 x 1, shifted three positions to the left)
=========
  1010

Por lo tanto, si un multiplicand / multiplicando es impar, el otro multiplicand / multiplicando se agrega en su unshifted versión. Observar que la adición lleva a la izquierda, por lo que no puede afectar a cualquier dígitos a la derecha de la derecha es 1, y no otros, además nunca se puede "tocar" por la derecha es 1 en ese número, porque a partir de ese punto sólo cambió los números (con su derecha 1 más a la izquierda o a tirar completamente). Así que una vez que se encuentra más a la derecha 1 es que se quede allí, y ya que tener una derecha 1 en todos los medios, el número no puede ser cero, multiplicar cualquier número distinto de cero por un número impar no puede dar como resultado cero.