computer-science - español - master of science magister
¿Cómo la computadora multiplica 2 números? (9)
Acabo de codificar un programa simple, multiplicar dos números almacenados en 2 líneas en un archivo usando algoritmo de multiplicación larga Puede multiplicar dos números que tienen más de mil millones de números entre sí.
Ejemplo:
23958233
5830 ×
------------
00000000 ( = 23,958,233 × 0)
71874699 ( = 23,958,233 × 30)
191665864 ( = 23,958,233 × 800)
119791165 ( = 23,958,233 × 5,000)
Código fuente:
Por favor revise y haga su comentario http://code.google.com/p/juniormultiply/source/browse/#svn/trunk/src
¿Cómo realiza una computadora una multiplicación en 2 números, por ejemplo 100 * 55?
Supongo que la computadora hizo una suma repetida para lograr la multiplicación. Por supuesto, este podría ser el caso de los números enteros. Sin embargo, para los números de punto flotante debe haber alguna otra lógica.
Nota: Esto fue pedido en una entrevista.
El método que se usa generalmente se llama productos parciales como los humanos, por lo que, por ejemplo, al tener 100*55 haría algo como
100 X
55
----
500 +
500
----
Básicamente, los enfoques antiguos utilizaban un algoritmo de desplazamiento y acumulación en el que se mantiene la suma mientras se desplazan los productos parciales para cada dígito del segundo número. El único problema de este enfoque es que los números se almacenan en el complemento 2, por lo que no puede hacer una simple multiplicación de bits por bit mientras realiza shifing.
Hoy en día, la mayoría de las optimizaciones pueden sumar todos los parciales en solo 1 ciclo, lo que le permite tener un cálculo más rápido y una paralelización más sencilla.
Eche un vistazo aquí: http://en.wikipedia.org/wiki/Binary_multiplier
Al final puedes encontrar algunas implementaciones como
Está bien, aquí tienes. Escribí esto hace un tiempo (¡1987!), Así que algunas cosas han cambiado, mientras que otras siguen siendo las mismas ...
Intuitivamente puede minimizar las adiciones repetidas utilizando también los cambios.
En términos de flotadores este artículo parece bastante relevante:
http://oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_14/CH14-1.html#HEADING1-19
La respuesta es, depende. Como han señalado otros, puedes usar el mismo algoritmo que nos enseñaron en la escuela, pero en lugar de eso usar binario. Pero para números pequeños hay otras formas.
Digamos que quiere multiplicar dos números de 8 bits, esto se puede hacer con una tabla de consulta grande. Solo concatena los dos números de 8 bits para formar un número de 16 bits y utiliza ese número para indexar en una tabla con todos los productos.
O, simplemente puede tener una gran red de puertas que computa la función de manera directa. Sin embargo, estas redes de puerta tienden a ser bastante difíciles de manejar para la multiplicación de grandes números.
La suma repetida sería una forma muy ineficiente de multiplicar números, imagina multiplicar 1298654825 por 85324154. Mucho más rápido que usar la multiplicación larga utilizando binario.
1100100
0110111
=======
0000000
-1100100
--1100100
---0000000
----1100100
-----1100100
------1100100
==============
1010101111100
Para números de punto flotante se utiliza notación científica.
100 is 1 * 10^2 (10 to the power of 2 = 100)
55 is 5.5 * 10^1 (10 to the power of 1 = 10)
Para multiplicarlas, multiplica las mantisas y suma los exponentes.
= 1 * 5.5 * 10^(2+1)
= 5.5 * 1000
= 5500
La computadora hace esto usando los equivalentes binarios.
100 = 1.1001 * 2^6
55 = 1.10111* 2^5
-> 1.1001 * 1.10111 * 2^(6+5)
Las computadoras usan el algoritmo de Booth u otros algoritmos que hacen cambios y sumas para operaciones aritméticas. Si hubiera estudiado cursos de arquitectura de computadoras, los libros sobre arquitectura de computadoras deberían ser un buen lugar para estudiar estos algoritmos.
Para multiplicar dos números de punto flotante se usa el siguiente procedimiento:
- Multiplica las mantisas
- Sumar los exponentes
- Normalizar el resultado (el punto decimal viene después del primer dígito no cero)
Entonces, en la base 10 para multiplicar 5.1E3 y 2.6E-2
Multiplique las mantisas => 5.1 * 2.6 = 13.26 (NB: esto se puede hacer con la multiplicación de enteros siempre que haga un seguimiento de dónde debería estar el punto decimal)
Suma los exponentes => 3 + -2 = 1
Nos da un resultado de 13.26E1.
Normalizar 13.26E1 => 1.326E2
Una forma es usar la multiplicación larga, en binario:
01100100 <- 100
* 00110111 <- 55
----------
01100100
01100100
01100100
01100100
01100100
---------------
1010101111100 <- 5500
Esto a veces se llama el método de cambio y adición .