Resolución de un sistema de ecuaciones mediante operaciones aritméticas y operaciones bit a bit

Question

Al principio hice esta pregunta en Stackoverflow, donde me aconsejaron que preguntara aquí. Así que ahí está la pregunta:

Tengo un sistema de ecuaciones bastante simples:

\begin{align} x + y &= A \\ f(x,y) + y &= B \end{align}

$A$ y $B$ son conocidos. Todas las variables son enteros positivos de 64 bits, incluyendo $f(x,y)$ .

Pero el problema es que $f(x,y)$ utiliza operaciones bit a bit : $$ f(x,y) = x \oplus (x << 3) \oplus y \oplus (y >> 14) $$ donde $\oplus$ indica XOR y $<<$ y $>>$ denotan la izquierda y la derecha cambios de bits respectivamente.

Intenté resolverlo representando la suma aritmética con opperaciones bit a bit y bits de acarreo. También intenté representar cada bit como un valor booleano y luego resolver un sistema de ecuaciones booleanas. No tuve mucho éxito. ¿Existe algún método para hacerlo correctamente?

Answer 1

Esto no es en absoluto una respuesta, pero es demasiado largo para un comentario.

Una primera idea:

Tal vez hacer método de subespacios de Krylov en dos vectores binarios $\bf x,y$ . Defina $f$ para ser la operación que hace lo que sea, trátala como una multiplicación de matriz dentro del algoritmo. Entonces el valor escalar para $x$ y $y$ viene dado por el producto escalar con estos vectores binarios: $x = [2^{63},2^{62},\cdots,1] {\bf x}$ y análogamente para $y, \bf y$ .

No he puesto en práctica los métodos de subespacios de Krylov en aritmética de punto no flotante, así que no puedo prometer que funcione.

Algunas observaciones más generales.

Podemos comprobando el signo de:

$B-A= f(x,y) -x$

$B-2A= f(x,y) -y- 2x$

$B-4A= f(x,y) -3y- 4x$

$B-8A= f(x,y) -7y- 8x$

Estimar la relación de tamaño entre $x$ y $y$ .

Además $x+y=A$ será mayor que el mayor de $x,y$ pero menor que el mayor de $2x$ y $2y$ . Estos son $y<<1$ y $x<<1$

$x \oplus (x<<3)$ marcará la magnitud de $x$ con el bit establecido más alto. Los dos bits siguientes también serán bits x no modificados. La complicación aquí es, por supuesto, si $y$ es varios órdenes de magnitud mayor que $x$ entonces empezará a corromper estos bits cuando $\oplus y$ entra en juego.