Supongo que por “bit-wise” te refieres a “base 2”.
También supongo que está pensando en cómo extender la precisión de una computadora más allá de lo que esté integrado.
Finalmente, consideraremos solo números positivos.
Para simplificar, asumimos que hay un tipo de datos disponible en C en su entorno favorito llamado NIBBLE que representa números del o al 15 (decimal), es decir, 8 bits.
- Para la función general f (x), si x * no es una raíz de f (x), ¿puede x * ser una raíz de f ‘(x)? Además, ¿qué pasa si f (x) es un polinomio?
- ¿Cómo podría encontrar x en a ^ x = bx + c usando álgebra?
- Como ingeniero eléctrico, ¿debo tomar álgebra lineal?
- Matemáticas: ¿Cómo pruebo la independencia / dependencia lineal de las siguientes funciones en un intervalo dado?
- ¿Para qué se usan las matrices dispersas? ¿Cuál es su aplicación en el aprendizaje automático?
También asumimos que su computadora (o su calculadora manual en modo “programador”) puede multiplicar 2 NIBBLES para obtener un valor de 2 NIBBLES (1 BYTE). También suponemos que tiene una forma de agregar valores BYTE de forma nativa. En un paquete de multiprecisión, estos probablemente se escalarían a valores de 32 bits y 64 bits, respectivamente. Una cosa a entender es que cuando trabajamos, por ejemplo, en C o C ++ o C #, es extremadamente importante usar valores sin signo.
Así que echemos un vistazo a la multiplicación de algunos valores de 4 nibbles para obtener un resultado de 8 nibbles.
X = 1 2 3 4
Y = 5 6 7 8
Z = Producto de X e Y = 06260060
Procedemos de esta manera
- 4 * 8 = 20 (hexadecimal) y entonces 0 es el dígito menos significativo del producto, y llevamos 2 al siguiente paso
- Segundo dígito del producto: 2 + 3 * 8 + 4 * 7 = 36 (hexadecimal). Publicar 6, llevar 3
- Tercer dígito: 3 + 2 * 8 + 3 * 7 + 4 * 6 = 40. Post 0 carry 4
- Cuarto dígito: 4 + 1 * 8 + 2 * 7 + 3 * 6 + 4 * 5 = 40. Publicar 0 llevar 4
- Quinto dígito: 4 + 1 * 7 + 2 * 6 + 3 * 5 = 26. Puesto 6 llevar 2
- Sexto dígito: 2 + 1 * 6 + 2 * 5 = 12. Puesto 2 Llevar 1
- Séptimo dígito: 1 + 1 * 5 = 6. Puesto 6 Llevar 0
- Octavo dígito: Llevar desde el paso anterior = 0
La clave es separar un valor de dos unidades en un dígito publicado y un carry para el siguiente paso.
Podemos hacer lo mismo solo con operaciones bit a bit, que pueden ser lo que quieres decir
Para el mismo ejemplo, exprese X e Y como números de 16 bits
X = 0001 0010 0011 0100
Y = 0101 0110 0111 1000
Paso 1: Agregue 16 0 bits a X
El producto P comienza con 32 bits, todos 0
0000 0000 0000 0000 0000 0000 0000 0000
Establecer índice = 0
Establecer X2 = copia de doble ancho de X (agregar 16 bits altos)
Para índice de 0 a 15
hacer
si el índice de bits de Y = 1, entonces agregue X2 a P
Shift X2 dejó 1 bit
hecho
En el caso que nos ocupa, el primer bit de Y que no es cero es el bit 3 (la cuarta interacción del bucle que comienza en 0), por lo que se agrega X << 3 al producto.
En resumen, Y tiene los siguientes bits distintos de cero: 14,12,10,9,6,5,4,3, y así
P = X2 << 14 + X2 << 12 + X2 << 9 + X2 << 6 + X2 << 5 + X2 << 4 + X2 << 3