El algoritmo de cuadrado y multiplicación calcula exponentes enteros en $\mathcal{O}(\log n)$ (tiempo logarítmico). La forma ingenua de calcular un exponente $x^n$ es multiplicar $x$ por sí mismo, $n$ veces, lo cual requeriría un tiempo de $\mathcal{O}(n)$ para calcularse.

Supongamos que queremos calcular $x^{20}$. En lugar de multiplicar $x$ por sí mismo 20 veces, comenzamos con $x$ y lo elevamos al cuadrado repetidamente hasta calcular $x^{16}$:

Observa que podemos calcular $x^{20}$ como:

El hecho de que los exponentes se “sumen” de esta manera se conoce en álgebra como la regla del producto de potencias.

Este artículo es parte de una serie sobre el código base de Uniswap V3. Uniswap V3 utiliza el algoritmo de cuadrado y multiplicación para convertir un índice tick a un square root price. Sin embargo, este artículo también está dirigido a cualquiera que desee aprender cómo funciona el algoritmo de cuadrado y multiplicación.

Secuencia de exponentes al cuadrado

Utilizaremos el término “secuencia de exponentes al cuadrado” varias veces en este artículo, la cual es $x^1,x^2,x^4,x^8,\dots$. Cada término es el cuadrado del anterior. La base $x$ puede tener cualquier valor distinto de cero. Por ejemplo, $0.7^1,0.7^2,0.7^4,...$ es una secuencia de exponentes al cuadrado válida. De manera similar, $-1.56,-1.56^2,...,-1.56^{32},-1.56^{64}$ también es una secuencia de exponentes al cuadrado válida.

Cuadrado y multiplicación con una base fraccionaria

Si sabemos de antemano que la base será un valor fijo, y que los exponentes que podríamos calcular tienen un límite superior conocido, entonces podemos precalcular la secuencia de exponentes al cuadrado y hacer búsquedas (lookups) en lugar de multiplicaciones. Por ejemplo, si queremos calcular $0.7^x$ y sabemos de antemano que $x$ no será mayor que 63, podemos precalcular los siguientes valores:

Luego, por ejemplo, si queremos calcular $0.7^{44}$, podemos multiplicar entre sí los valores precalculados apropiados de la secuencia de exponentes al cuadrado de la siguiente manera:

Se anima al lector a recalcular $0.7^{44}$ en su calculadora para comprobarlo.

Cuando guardamos valores en caché de esta manera, debemos conocer de antemano el límite superior del exponente que nuestra aplicación debe manejar.

Algoritmo de cuadrado y multiplicación con exponentes fraccionarios

¿Supongamos que en lugar de calcular $0.7^x$ queremos calcular $\sqrt[3]{0.7^x}$? Esto es equivalente a $0.7^{x/3}$. Todavía podemos usar el algoritmo de cuadrado y multiplicación porque el exponente se divide por un número constante, por lo que la regla del producto de potencias sigue aplicando. En otras palabras,

Para calcular $0.7^{44/3}$, cambiaríamos las potencias de $0.7$ que precalculamos de la siguiente manera:

Luego, para calcular $0.7^{44/3}$ multiplicamos los exponentes precalculados de la siguiente manera:

De nuevo, se anima al lector a rehacer estos cálculos por sí mismo.

Seleccionando los elementos de la secuencia de exponentes al cuadrado

Si queremos calcular $b^{44}$, ¿cómo averiguamos qué potencias de $b$ necesitamos de nuestra secuencia de exponentes al cuadrado? En otras palabras, ¿cómo determinamos rápidamente que necesitamos $b^{32}, b^{8}, b^{4}$ y no $b^{32}, b^{4}, b^{1}$?

Dada una suma objetivo, como 44, ¿cómo determinamos rápidamente que 32, 8 y 4 son los sumandos? Alternativamente, supongamos que estamos intentando calcular $b^{37}$. Los elementos de la secuencia de exponentes al cuadrado que necesitamos son $b^{32},b^{4},b^{1}$ — ¿cómo determinamos rápidamente que necesitamos $b^{32},b^{4},b^{1}$ y no $b^{2},b^{8},b^{16}$?

Un enfoque ingenuo sería hacer una búsqueda lineal desde el exponente precalculado más grande hacia abajo y restar el más grande que no sobrepase el objetivo. Por ejemplo, si estuviéramos calculando $5^{44}$, eso significa que ya hemos calculado la secuencia de exponentes al cuadrado de 5. Escaneamos hacia abajo y encontramos que 32 es el valor más cercano a 44. Luego escaneamos hacia abajo nuevamente para encontrar 16, pero notamos que sumar 32+16 sobrepasa 44, así que omitimos 16 y pasamos a 8, y así sucesivamente.

Usando la representación binaria para extraer los componentes de la suma

En lugar de usar la búsqueda lineal mencionada anteriormente, podemos ser más eficientes al observar que la representación binaria del exponente objetivo nos dice con precisión qué elementos usar de la secuencia de exponentes al cuadrado.

Esto se ilustra mejor con ejemplos.

Para convertir un número binario a un número decimal, utilizamos la siguiente fórmula donde $b_i$ es el $i$-ésimo bit en el número binario:

El valor binario de 13 es 1101 porque

El valor binario de 52 es 110100 porque

Por lo tanto, si queremos calcular $b^{13}$, y nuestra secuencia de exponentes al cuadrado es $b^8,b^4,b^2,b^1$, entonces podemos observar la representación binaria de 1011 y determinar que debemos elegir el exponente 8, el exponente 4 y el exponente 1, para luego calcular

dado que

Así, podemos determinar rápidamente que 13 se puede escribir como 8 + 4 + 1 ya que el 3er bit, el 2do bit y el bit 0 son 1.

Detectando si un bit está activado

Podemos detectar si el n-ésimo bit es 1 en una representación binaria con la siguiente lógica:

Copy
function nthBitSet(uint256 x, uint8 n) public pure returns (bool isSet) {

	isSet = x & uint256(2)**n != 0;
}

Consideremos la representación binaria de las potencias de dos:

uint256(2)**n crea un número con solo el n-ésimo bit activado en 1. Por ejemplo, si n = 3, esto produciría el valor binario 1000. $2^3=8$ y 1000 es la representación binaria de 8, como se muestra en la Tabla anterior. Si el AND bit a bit de x y 2^n no es cero, entonces isSet es true.

Cómo funciona el AND bit a bit

El AND bit a bit devuelve 1 solo si ambos bits correspondientes son 1; de lo contrario, devuelve 0. Por ejemplo, 8 & 13 = 8 porque la representación binaria de 8 es 1000 y la representación binaria de 13 es:

o 1101. Cuando aplicamos un AND bit a bit a 1000 con 1101 obtenemos 1000 ya que tanto 8 como 13 tienen un bit 1 en común en la 3ra posición.

Esto se ilustra a continuación:

Copy
Suppose x = 13 (binary: 1101) and n = 3:

x           = 1101 (decimal 13)
2**n        = 1000 (decimal 8)
------------------------------
bitwise AND = 1000 (decimal 8) != 0, thus true.

Thus, nthBitSet(13, 3) returns true.

Dado que el resultado final 1000 no es igual a cero, entonces sabemos que tuvo que haber una superposición de bits 1 entre x y 2^n — esto indica que ese bit debe ser igual a uno.

Ejemplo 2: ¿Está activado el 1er bit en 13? Podemos crear una “máscara” para el primer bit como 2**1 tal como se muestra a continuación:

Copy
Suppose x = 13 (binary: 1101) and n = 1:

x           = 1101 (decimal 13)
2**n        = 0010 (decimal 2)
------------------------------
bitwise AND = 0000 (decimal 0) == 0, thus false.

Thus, nthBitSet(13, 1) returns false.

Dado que el resultado final es 0000, sabemos que el 1er bit no está activado.

Ejemplo 3: ¿Está activado el bit 0 en 13?

Copy
Suppose x = 13 (binary: 1101) and n = 0:

x           = 1101 (decimal 13)
2**n        = 0001 (decimal 1)
------------------------------
bitwise AND = 0001 (decimal 1) == 1, thus true.

Thus, nthBitSet(13, 0) returns true.

Ejemplo en Python de $0.7^x$

Ahora combinamos todo lo que hemos aprendido para producir la siguiente función, que eleva 0.7 a una potencia de hasta 32:

Copy
pow1 = 0.7
pow2 = 0.48999999999999994 # 0.7^2
pow4 = 0.24009999999999995 # 0.7^4
pow8 = 0.05764800999999997 # 0.7^8
pow16 = 0.0033232930569600965 # 0.7^16

def raise_07_to_p(p):
	# computes 0.7^p
	assert p < 32
	
	# if p = 0, we return 1, which is correct
	# since 0.7^0 = 1
	accumulator = 1
	
	if p & 1 != 0:
		accumulator = accumulator * pow1
	if p & 2 != 0:
		accumulator = accumulator * pow2
	if p & 4 != 0:
		accumulator = accumulator * pow4
	if p & 8 != 0:
		accumulator = accumulator * pow8
	if p & 16 != 0:
		accumulator = accumulator * pow16

	return accumulator

# check correctness
print(0.7**14, raise_07_to_p(14))
print(0.7**18, raise_07_to_p(18))
print(0.7**30, raise_07_to_p(30))

El código anterior evita la multiplicación repetitiva usando solo las potencias de 0.7 que corresponden a los unos (1s) en la representación binaria del exponente.

Hasta ahora, hemos usado números regulares/de coma flotante. Sin embargo, en sistemas del mundo real como los smart contracts, a menudo usamos números de punto fijo (o Q-numbers).

Usando el algoritmo de cuadrado y multiplicación con números de punto fijo

Después de multiplicar números de punto fijo (o Q-numbers) entre sí, el resultado debe ser “normalizado”, es decir, el resultado necesita ser dividido por el factor de escala. Por ejemplo, cuando multiplicamos dos números de punto fijo de 18 decimales entre sí, necesitamos dividir el resultado por $10^{18}$, de lo contrario el resultado final se escribirá con 36 decimales.

Implementación en Python y Solidity de cuadrado y multiplicación precalculado — con números de punto fijo

Primero implementaremos el algoritmo de cuadrado y multiplicación en Python, y luego traduciremos ese código a Solidity. La versión en Solidity utilizará números de punto fijo ya que Solidity no tiene números de coma flotante. A continuación, usamos Python para calcular las potencias de 0.7 como Q-numbers de punto fijo de 128 bits a modo de implementación de referencia:

Copy
from decimal import *
import math
getcontext().prec = 100

for i in [1,2,4,8,16,32]:
    print(f"0.7^{i} * 2**128 =", math.floor(Decimal(0.7) ** Decimal(i) * Decimal(2**128)))

Cuando ejecutamos el código anterior, obtenemos las siguientes constantes

Copy
(base) ➜ python sqmul.py
0.7^1 * 2**128 = 238197656844656909312789480019373064192
0.7^2 * 2**128 = 166738359791259825940851714385556537344
0.7^4 * 2**128 = 81701796297717304344478436853479174360
0.7^8 * 2**128 = 19616601291081919795097291374069314602
0.7^16 * 2**128 = 1130858027394302849221997646234907220
0.7^32 * 2**128 = 3758172630847077410107089115980415

Implementación en Solidity de cuadrado y multiplicación

La siguiente implementación en Solidity usa números de punto fijo de 128 bits, lo que significa que hay 128 bits después del número, o equivalentemente, el número fraccionario es escalado multiplicándolo por $2^{128}$. La operación >> 128 es equivalente a dividir por $2^{128}$.

Copy
contract SquareAndMultiply {

    // z7_x means 0.7^x
    uint256 constant z7_1 = 238197656844656909312789480019373064192;
    uint256 constant z7_2 = 166738359791259825940851714385556537344;
    uint256 constant z7_4 = 81701796297717304344478436853479174360;
    uint256 constant z7_8 = 19616601291081919795097291374069314602;
    uint256 constant z7_16 = 1130858027394302849221997646234907220;
    uint256 constant z7_32 = 3758172630847077410107089115980415;

    function powZ7(uint256 e) public pure returns (uint256) {
        require(e < 64, "e too large");

        // if e is zero, return 1 as a 128-bit fixed point number
        uint256 acc = 1 << 128;

				// powers of 2 are written in hex, 0x10 = 16 and 0x20 = 32
        if (e & 0x1 != 0) acc = (acc * z7_1) >> 128;
        if (e & 0x2 != 0) acc = (acc * z7_2) >> 128;
        if (e & 0x4 != 0) acc = (acc * z7_4) >> 128;
        if (e & 0x8 != 0) acc = (acc * z7_8) >> 128;
        if (e & 0x10 != 0) acc = (acc * z7_16) >> 128;
        if (e & 0x20 != 0) acc = (acc * z7_32) >> 128;

        // check the answer by doing acc / 2**128
        // in a language that has floating points
        // then check that equals 0.7^e
        return acc;
    }
}

¿Por qué no simplemente usar un opcode de exponente?

Al elevar un entero a una potencia entera, generalmente es más eficiente usar el opcode incorporado de una máquina virtual.

Sin embargo, este opcode no incluye el paso de normalización descrito anteriormente. Por lo tanto, si al menos uno de $b$ o $x$ en $b^x$ es un número de punto fijo, entonces no podemos usar el opcode exp de la máquina virtual.

Cuadrado y multiplicación en Uniswap V3

Para convertir un tick a un square root price, Uniswap V3 debe calcular

(con algunas correcciones ya que sqrtPrice es un número Q64.96). Dado que

1. la base es fija y la única variable es el exponente y

2. el rango de ticks se conoce de antemano. Uniswap V3 puede usar (y usa) el algoritmo de cuadrado y multiplicación. Esto se explica en el próximo capítulo.

Como adelanto, aquí hay una captura de pantalla de getSqrtRatioAtTick() de la Uniswap V3 Tickmath Library. Esto debería verse muy similar al código de Solidity que escribimos anteriormente. A un alto nivel, la función verifica si un bit en absTick está activado, y si lo está, multiplica ratio por una potencia precalculada de 1.0001.