Hola, descubrimos la respuesta a tu búsqueda, desplázate y la hallarás un poco más abajo.
Solución:
Sabes que al menos un factor es <= sqrt (A). Hagamos esa X.
La longitud de X en bits será aproximadamente la mitad de la longitud de A.
Los bits superiores de X, por lo tanto, los que tienen un valor más alto que sqrt (A), son todos 0, y los bits correspondientes en B deben tener el mismo valor que los bits correspondientes en Y.
Conocer los bits superiores de Y le da un rango bastante pequeño para el factor correspondiente X = A / Y. Calcule Xmin y Xmax correspondientes a los valores más grandes y más pequeños posibles para Y, respectivamente. Recuerde que Xmax también debe ser <= sqrt (A).
Luego, pruebe todas las X posibles entre Xmin y Xmax. No habrá demasiados, por lo que no tardará mucho.
La otra forma sencilla de resolver este problema se basa en el hecho de que el menor norte bits de XY y X xor Y dependen solo de la norte bits de X e Y. Por lo tanto, puede utilizar las posibles respuestas para los norte bits para restringir las posibles respuestas para los n + 1 bits, hasta que haya terminado.
He descubierto que, desafortunadamente, puede haber más de una posibilidad para una sola norte. No sé con qué frecuencia habrá un lote de posibilidades, pero probablemente no sea con demasiada frecuencia, por lo que esto puede estar bien en un contexto competitivo. Probabilísticamente, solo habrá unas pocas posibilidades, ya que una solución para norte bits proporcionarán 0 o dos soluciones para n + 1 bits, con igual probabilidad.
Parece funcionar bastante bien para la entrada aleatoria. Aquí está el código que usé para probarlo:
public static void solve(long A, long B)
List sols = new ArrayList<>();
List prevSols = new ArrayList<>();
sols.add(0L);
long tests=0;
System.out.print("Solving "+A+","+B+"... ");
for (long bit=1; (A/bit)>=bit; bit<<=1)
tests += sols.size();
List t = prevSols;
prevSols = sols;
sols = t;
final long mask = bit
tests += sols.size();
List t = prevSols;
prevSols = sols;
sols = t;
sols.clear();
for (long testx: prevSols)
if (A/testx >= testx)
long testy = B^testx;
if (testx * testy == A)
sols.add(testx);
System.out.println("" + tests + " checks -> X=" + sols);
public static void main(String[] args)
Random rand = new Random();
for (int range=Integer.MAX_VALUE; range > 32; range -= (range>>5))
=1;
long Y = A/X;
if (Y==0)
Y = rand.nextInt(65536);
Y
Puedes ver los resultados aquí: https://ideone.com/cEuHkQ
Parece que por lo general solo se necesitan un par de miles de cheques.
Aquí hay una recursividad simple que observa las reglas que conocemos: (1) los bits menos significativos de X e Y se establecen ya que solo los multiplicandos impares producen un múltiplo impar; (2) si configuramos X para que tenga el bit establecido más alto de B, Y no puede ser mayor que sqrt (A); y (3) establecer bits en X o Y de acuerdo con el bit actual en B.
El siguiente código de Python resultó en menos de 300 iteraciones para todos menos uno de los pares aleatorios que elegí del código de ejemplo de Matt Timmermans. Pero el primero tomó 231,199 iteraciones 🙂
from math import sqrt
def f(A, B):
i = 64
while not ((1< i):
i = j + 1
memo = "it": 0, "stop": False, "solution": []
def g(b, x, y):
memo["it"] = memo["it"] + 1
if memo["stop"]:
return []
if y > sqrtA or y * x > A:
return []
if b == 0:
if x * y == A:
memo["solution"].append((x, y))
memo["stop"] = True
return [(x, y)]
else:
return []
bit = 1 << b
if B & bit:
return g(b - 1, x, y | bit) + g(b - 1, x | bit, y)
else:
return g(b - 1, x | bit, y | bit) + g(b - 1, x, y)
g(i - 1, X, 1)
return memo
vals = [
(6872997084689100999, 2637233646), # 1048 checks with Matt's code
(3461781732514363153, 262193934464), # 8756 checks with Matt's code
(931590259044275343, 5343859294), # 4628 checks with Matt's code
(2390503072583010999, 22219728382), # 5188 checks with Matt's code
(412975927819062465, 9399702487040), # 8324 checks with Matt's code
(9105477787064988985, 211755297373604352), # 3204 checks with Matt's code
(4978113409908739575,67966612030), # 5232 checks with Matt's code
(6175356111962773143,1264664368613886), # 3756 checks with Matt's code
(648518352783802375, 6) # B smaller than sqrt(A)
]
for A, B in vals:
memo = f(A, B)
[(x, y)] = memo["solution"]
print "x, y: %s, %s" % (x, y)
print "A: %s" % A
print "x*y: %s" % (x * y)
print "B: %s" % B
print "x^y: %s" % (x ^ y)
print "%s iterations" % memo["it"]
print ""
Producción:
x, y: 4251585939, 1616572541
A: 6872997084689100999
x*y: 6872997084689100999
B: 2637233646
x^y: 2637233646
231199 iterations
x, y: 262180735447, 13203799
A: 3461781732514363153
x*y: 3461781732514363153
B: 262193934464
x^y: 262193934464
73 iterations
x, y: 5171068311, 180154313
A: 931590259044275343
x*y: 931590259044275343
B: 5343859294
x^y: 5343859294
257 iterations
x, y: 22180179939, 107776541
A: 2390503072583010999
x*y: 2390503072583010999
B: 22219728382
x^y: 22219728382
67 iterations
x, y: 9399702465439, 43935
A: 412975927819062465
x*y: 412975927819062465
B: 9399702487040
x^y: 9399702487040
85 iterations
x, y: 211755297373604395, 43
A: 9105477787064988985
x*y: 9105477787064988985
B: 211755297373604352
x^y: 211755297373604352
113 iterations
x, y: 68039759325, 73164771
A: 4978113409908739575
x*y: 4978113409908739575
B: 67966612030
x^y: 67966612030
69 iterations
x, y: 1264664368618221, 4883
A: 6175356111962773143
x*y: 6175356111962773143
B: 1264664368613886
x^y: 1264664368613886
99 iterations
x, y: 805306375, 805306369
A: 648518352783802375
x*y: 648518352783802375
B: 6
x^y: 6
59 iterations
Tienes la opción de ayudar nuestro ensayo mostrando un comentario o dejando una puntuación te estamos agradecidos.