A medida que me involucro más y más con la teoría detrás de la programación, me siento fascinado y atónito por cosas aparentemente simples. Me doy cuenta de que mi comprensión de la mayoría de los procesos fundamentales se justifica a través de la lógica circular.
P : ¿Cómo funciona esto?
A : porque lo hace!
Odio esta realización! Me encanta el conocimiento y, además, me encanta aprender, lo que me lleva a mi pregunta (aunque sea amplia).
Pregunta:
¿Cómo se evalúan los operadores matemáticos fundamentales con lenguajes de programación?
¿Cómo se han mejorado los métodos actuales?
Ejemplo
var = 5 * 5;
Mi interpretación:
$num1 = 5; $num2 = 5; $num3 = 0;
while ($num2 > 0) {
$num3 = $num3 + $num1;
$num2 = $num2 - 1;
}
echo $num3;
Esto parece ser altamente ineficiente. Con factores superiores, este método es muy lento, mientras que el método estándar incorporado es instantáneo. ¿Cómo simularías la multiplicación sin iterar la suma?
var = 5 / 5;
¿Cómo se hace esto? No se me ocurre una manera de dividirlo literalmente 5 en 5 partes iguales.
var = 5 ^ 5;
¿Iteraciones de iteraciones de suma? Mi interpretación:
$base = 5;
$mod = 5;
$num1 = $base;
while ($mod > 1) {
$num2 = 5; $num3 = 0;
while ($num2 > 0) {
$num3 = $num3 + $num1;
$num2 = $num2 - 1;
}
$num1 = $num3;
$mod -=1;
}
echo $num3;
De nuevo, esto es EXTREMADAMENTE ineficiente, pero no puedo pensar en otra forma de hacerlo. Esta misma pregunta se extiende a todas las funciones relacionadas con las matemáticas que se manejan automáticamente.
fuente
Respuestas:
Para comprender realmente cómo funciona la aritmética dentro de una computadora, debe haber programado en lenguaje ensamblador. Preferiblemente uno con un tamaño de palabra pequeño y sin instrucciones de multiplicación y división. Algo así como el 6502.
En el 6502, prácticamente toda la aritmética se realiza en un registro llamado Acumulador. (Un registro es una ubicación de memoria especial dentro del procesador a la que se puede acceder rápidamente). Entonces, para agregar dos números, cargue el primer número en el acumulador y luego agregue el segundo número.
Pero eso es demasiado simplificador. Debido a que el 6502 es un procesador de 8 bits, solo puede manejar números del 0 al 255. La mayoría de las veces querrá trabajar con números más grandes. Debe agregarlos en trozos, 8 bits a la vez. El procesador tiene un indicador de transporte que se establece cuando el resultado de sumar dos números desborda el acumulador. El procesador agrega eso al hacer una adición, por lo que se puede usar para "llevar el 1", suponiendo que comience con el byte de orden más bajo de un número. Un complemento de varios bytes en el 6502 se ve así:
La sustracción es similar, excepto que usted configura primero el acarreo, usa la instrucción SBC en lugar de ADC, y al final el acarreo es claro si hubo un desbordamiento.
¡Pero espera! ¿Qué pasa con los números negativos? Bueno, con el 6502 estos se almacenan en un formato llamado complemento de dos. Suponiendo un número de 8 bits, -1 se almacena como 255, porque cuando agrega 255 a algo, obtiene uno menos en el acumulador (más un acarreo). -2 se almacena como 254 y así sucesivamente, hasta -128, que se almacena como 128. Entonces, para enteros con signo, la mitad del rango 0-255 de un byte se usa para números positivos y la otra mitad para números negativos. (Esta convención le permite verificar el bit alto de un número para ver si es negativo).
Piense en ello como un reloj de 24 horas: agregar 23 a la hora dará como resultado una hora una hora antes (al día siguiente). Entonces 23 es el equivalente modular del reloj a -1.
Cuando usa más de 1 byte, debe usar números más grandes para los negativos. Por ejemplo, los enteros de 16 bits tienen un rango de 0-65536. Entonces 65535 se usa para representar -1, y así sucesivamente, porque agregar 65535 a cualquier número da como resultado uno menos (más un carry).
En el 6502 solo hay cuatro operaciones aritméticas: sumar, restar, multiplicar por dos (desplazamiento a la izquierda) y dividir por dos (desplazamiento a la derecha). La multiplicación y la división se pueden hacer usando solo estas operaciones cuando se trata en binario. Por ejemplo, considere multiplicar 5 (binario 101) y 3 (binario 11). Al igual que con la multiplicación decimal larga, comenzamos con el dígito derecho del multiplicador y multiplicamos 101 por 1, dando 101. Luego cambiamos el multiplicando a la izquierda y multiplicamos 1010 por 1, dando 1010. Luego sumamos estos resultados, dando 1111, o 15. Como siempre estamos multiplicando por 1 o 0, en realidad no multiplicamos; cada bit del multiplicador simplemente sirve como una bandera que nos dice si agregar el multiplicando (desplazado) o no.
La división es análoga a la división larga manual usando divisores de prueba, excepto en binario. Si está dividiendo por una constante, es posible hacer esto de forma análoga a la resta: en lugar de dividir por X, multiplica por una interpretación precalculada de 1 / X que produce el resultado deseado más un desbordamiento. Incluso hoy, esto es más rápido que la división.
Ahora intente hacer cálculos de punto flotante en el ensamblaje, o convertir números de punto flotante a formatos de salida agradables en el ensamblaje. Y recuerde, es 1979 y la velocidad del reloj es de 1 MHz, por lo que debe hacerlo de la manera más eficiente posible.
Las cosas todavía funcionan más o menos así hoy, excepto que con tamaños de palabra más grandes y más registros, y por supuesto, la mayoría de las matemáticas se realizan ahora por hardware. Pero todavía se hace de la misma manera fundamental. Si suma la cantidad de turnos y adiciones requeridas para una multiplicación, por ejemplo, se correlaciona bastante bien con la cantidad de ciclos requeridos para una instrucción de multiplicación de hardware en los primeros procesadores que tienen dicha instrucción, como el 6809, donde se realizó en microcódigo de la misma manera que lo haría manualmente. (Si tiene un presupuesto de transistores más grande, hay formas más rápidas de hacer los cambios y las adiciones, por lo que los procesadores modernos no realizan estas operaciones secuencialmente y pueden realizar multiplicaciones en tan solo un ciclo).
fuente
Binary Multiplierpara más detalles.Al final, las operaciones aritméticas básicas se realizan en hardware. Más específicamente, en la CPU (o en realidad, una subparte de la misma)
En otras palabras, son circuitos electrónicos. Establezca los bits apropiados como entrada y obtendrá los bits apropiados como salida. Es una combinación de puertas lógicas básicas.
http://en.wikipedia.org/wiki/Adder_%28electronics%29
http://en.wikipedia.org/wiki/Binary_multiplier
fuente
Todo esto está cubierto con mucha paciencia en El arte de la programación informática de Don Knuth.
Los algoritmos eficientes para sumar, restar, multiplicar y dividir se describen con todo detalle.
Puedes leer cosas como esta que cubren muy bien la división.
http://research.microsoft.com/pubs/151917/divmodnote.pdf
fuente
Se realiza en picosegundos por circuitos electrónicos. Google 'multiplicador de hardware' etc. para más detalles. Las CPU modernas son el resultado extremadamente complejo de décadas de mejora continua.
Por cierto, como no multiplicas por la suma repetida, ¿por qué imaginas que lo haría una computadora?
fuente
Esto no pretende ser una respuesta exhaustiva de ninguna manera, pero debería darle una idea de cómo se implementan las cosas. Como probablemente sepa, los números están representados en binario. Por ejemplo, una computadora podría representar el número 5 como 00000101. Una operación muy básica que una computadora puede hacer es desplazarse hacia la izquierda, lo que daría 00001010 que es decimal 10. Si se desplazara a la derecha dos veces sería 00010100 (20 decimal). Cada vez que desplazamos los dígitos a la izquierda 1 vez, duplicamos el número. Digamos que tenía un número x y quería multiplicarlo por 17. Podría cambiar x a la izquierda 4 veces y luego agregar x al resultado (16x + x = 17x). Esta sería una forma eficiente de multiplicar un número por 17. Esto debería darle una idea de cómo una computadora puede multiplicar números grandes sin simplemente usar la suma repetida.
La división puede usar combinaciones de suma, resta, desplazamiento a la derecha, desplazamiento a la izquierda, etc. También hay numerosos trucos para elevar números a exponentes.
fuente
shl r0, 4.Cuando era niño, aprendí a multiplicar y dividir con un bolígrafo y un papel, sin perder el tiempo con demasiadas adiciones. Más tarde aprendí que las raíces cuadradas también son computables de esa manera.
En la universidad aprendí a calcular operaciones trigonométricas y logarítmicas con una docena de multiplicaciones, divisiones y sumas. Lo llamaron serie Taylor.
Antes de eso, mi padre me dio un libro donde esas operaciones complejas ya se calcularon para cientos de valores y se presentaron en tablas. También hubo algunas explicaciones para estimar el error cuando deseaba el seno de un valor entre dos valores calculados.
Las unidades enteras, las unidades de coma flotante, la GPU y el DSP simplemente implementan todas esas técnicas antiguas en silicio.
fuente
Trataré de darle una idea de cómo están diseñados los circuitos digitales para resolver problemas de procesamiento digital utilizando los problemas que plantea: cómo las CPU implementan adiciones y multiplicaciones.
En primer lugar, eliminemos la pregunta directa: cómo un lenguaje de programación evalúa eficientemente las multiplicaciones y las sumas. La respuesta es simple, los compilan en multiplicar y agregan instrucciones. Por ejemplo, el siguiente código:
simplemente se compila a algo como:
(tenga en cuenta que el ensamblaje anterior es para una CPU imaginaria que no existe, por simplicidad).
En este punto, se da cuenta de que la respuesta anterior simplemente cambia el problema y lo resuelve con magia de hardware. La pregunta de seguimiento es, obviamente, ¿cómo funciona esa magia de hardware?
Veamos primero el problema más simple: la suma.
Primero hacemos un problema familiar, agregando números regulares de base 10:
El primer paso sería agregar 7 y 8. Pero esto da como resultado 15, que es más que un solo dígito. Entonces llevamos el 1:
Ahora sumamos 1, 1 y 2 juntos:
Entonces de esto obtenemos las siguientes reglas:
cuando el resultado de la suma es más de un dígito, mantenemos el dígito menos significativo y llevamos el dígito más significativo hacia adelante
si tenemos un dígito transferido a nuestra columna, lo agregamos junto con los números que estamos agregando
Ahora es el momento de interpretar las reglas anteriores en la base 2: álgebra booleana.
Entonces, en álgebra booleana, sumar 0 y 1 juntos = 1. Sumar 0 y 0 = 0. Y sumar 1 y 1 = 10, que es más de un dígito, entonces llevamos el 1 hacia adelante.
De esto podemos construir una tabla de verdad:
A partir de esto, podemos construir dos circuitos / ecuaciones booleanas: una para la salida de suma y otra para la salida de acarreo. La forma más ingenua es simplemente enumerar todas las entradas. Cualquier tabla de verdad, no importa cuán grande y complejo se pueda replantear de esta forma:
Esto es básicamente la suma de productos de forma. Solo miramos las salidas que dan como resultado un 1 e ignoramos los 0:
Reemplacemos AND AND y NOT con símbolos de lenguaje de programación para que sea más fácil de leer:
Básicamente, hemos convertido la tabla de esta manera:
Esto se puede implementar directamente como un circuito:
En este punto, los lectores observadores notarán que la lógica anterior se puede implementar como una sola puerta, una puerta XOR que convenientemente tiene el comportamiento requerido por nuestra tabla de verdad:
Pero si su hardware no le proporciona una puerta XOR, los pasos anteriores son cómo definiría e implementaría en términos de puertas AND, OR y NOT.
La forma en que convertiría las puertas lógicas en hardware real depende del hardware que tenga. Se pueden implementar utilizando diversos mecanismos físicos siempre que el mecanismo proporcione algún tipo de comportamiento de conmutación. Las puertas lógicas se han implementado con todo, desde chorros de agua o bocanadas de aire (fluidos) hasta transistores (electrónicos) y canicas que caen. Es un gran tema en sí mismo, así que voy a pasarlo por alto y decir que es posible implementar puertas lógicas como dispositivos físicos.
Ahora hacemos lo mismo para la señal de transporte. Como solo hay una condición en la que la señal de transporte es verdadera, la ecuación es simplemente:
Así que llevar es simple:
Combinándolos juntos obtenemos lo que se conoce como el medio sumador:
Por cierto, las ecuaciones para el circuito anterior se ven así:
Al medio sumador le falta algo. Hemos implementado la primera regla, si el resultado es más de un dígito que el avance, pero no hemos implementado la segunda regla, si hay un acarreo, agréguelo junto con los números.
Entonces, para implementar un sumador completo, un circuito de suma que pueda agregar números que tengan más de un dígito, necesitamos definir una tabla de verdad:
La ecuación para la suma es ahora:
Podemos pasar por el mismo proceso para factorizar y simplificar la ecuación e interpretarla como un circuito, etc., como hemos hecho anteriormente, pero creo que esta respuesta se está haciendo demasiado larga.
A estas alturas ya debería tener una idea de cómo está diseñada la lógica digital. Hay otros trucos que no he mencionado, como los mapas de Karnaugh (utilizados para simplificar las tablas de verdad) y los compiladores lógicos como el espresso (para que no tenga que factorizar ecuaciones booleanas a mano), pero lo básico es básicamente lo que he resaltado arriba:
Descomponga el problema hasta que pueda trabajar a nivel de un solo bit (dígito).
Defina las salidas que desea utilizando una tabla de verdad.
Convierta la tabla a una ecuación booleana y simplifique la ecuación.
Interpreta la ecuación como puertas lógicas.
Convierta su circuito lógico en circuitos de hardware real mediante la implementación de puertas lógicas.
Así es como realmente se resuelven los problemas fundamentales (o más bien, de bajo nivel): muchas, muchas tablas de verdad. El verdadero trabajo creativo consiste en desglosar una tarea compleja como la decodificación de MP3 a nivel de bits para que pueda trabajar en ella con tablas de verdad.
Lo siento, no tengo tiempo para explicar cómo implementar la multiplicación. Puede intentar descifrarlo descubriendo las reglas de cuánto tiempo funciona la multiplicación, luego interpretándola en binario y luego intente dividirla en tablas de verdad. O puede leer Wikipedia: http://en.wikipedia.org/wiki/Binary_multiplier
fuente
Las instrucciones aritméticas básicas se realizan con instrucciones de montaje que son altamente eficientes.
Las instrucciones más complejas (o abstractas) se realizan en conjunto con mecanismos de bucle o se manejan en bibliotecas estándar.
A medida que estudies matemáticas en la universidad, comenzarás a estudiar cosas como el cálculo Lambda y la notación Big-O. Todos estos, y muchos más, son utilizados por los programadores para evaluar y crear algoritmos eficientes. De todos modos, las cosas básicas generalmente se logran en el nivel bajo, como en el ensamblaje o en c con punteros.
Una gran introducción a este tema es "Código" de Charles Petzold.
fuente
Obtenga un libro como Fundamentals of Digital Logic ... , que creo que todavía es bastante estándar para los estudiantes de Freshman / Sophomore EE, y trabaje en él (ed: cuesta una pequeña fortuna, así que busque una edición usada o anterior de eso). Eso lo llevará a través de los sumadores y multiplicadores, y le brindará suficientes antecedentes para comenzar a comprender algunos de los principios detrás de lo que está haciendo el hardware.
Su respuesta, en el corto plazo, se convertirá en "porque reúne innumerables piezas de lógica más simple para evocar este comportamiento complejo" en lugar de "porque lo hace".
Si desea intentar comprender todos los principios de cómo se compilan y ejecutan los programas, hágalo en conjunto, para que finalmente pueda ver cómo todo se encuentra en el medio.
fuente
Hay muchas buenas respuestas aquí. También comenzó con la idea correcta: las operaciones complejas como la multiplicación se crean a partir de operaciones más simples. Como habrás adivinado, hay formas más rápidas de multiplicar sin una instrucción de multiplicación que usar una serie de sumas. Cualquier multiplicación puede implementarse como la suma de multiplicaciones más pequeñas, o como una combinación de turnos y adiciones. Ejemplos:
La división también se puede dividir en operaciones más pequeñas. XOR (^) es una instrucción incorporada en todos los procesadores que he visto, pero aun así puede implementarse como una combinación de AND, OR y NOT.
Sin embargo, tengo la sensación de que las respuestas específicas serán menos satisfactorias para usted que una idea general de los tipos de instrucciones que proporciona un procesador y cómo esas instrucciones pueden combinarse en operaciones más complejas. No hay nada mejor para ese tipo de curiosidad que una buena dosis de lenguaje ensamblador. Aquí hay una introducción muy accesible al lenguaje ensamblador MIPS.
fuente
Así es como un procesador moderno podría implementar la multiplicación de dos enteros de 64 bits:
Sabes cómo hacer una multiplicación de mano larga. Para multiplicar dos números de 10 dígitos, debe multiplicar un número de 10 dígitos por cada uno de los 10 dígitos del otro número, escribir el resultado de 11 dígitos uno debajo del otro y desplazarlo, luego agregar todo el número.
Un procesador moderno hace esto con todos los 64 por 64 bits. Sin embargo, una multiplicación de dos números de un solo bit es muy simple: 1 x 1 = 1, todos los demás productos son cero. Esto se implementa con una lógica y. Y a diferencia del producto decimal, donde el resultado puede ser de dos dígitos, un producto binario de números de un solo bit es siempre un bit.
Entonces ahora tiene 64 filas de 64 bits que deben agregarse. Pero 64 adiciones de números de 64 bits son muuuuchas. Por lo tanto, el procesador utiliza un sumador 3/2 o un sumador 7/3: si agrega 3 números de un solo bit, el resultado puede ser 0, 1, 2 o 3, que cabe en dos bits. Si agrega 7 números de un solo bit, el resultado es un número del 0 al 7, que puede representarse con 3 bits. IBM afirma que pueden hacer un sumador 7/3 con solo 18 circuitos primitivos (documentación de PowerPC), apuesto a que Intel y ARM también pueden hacer esto.
Tiene 4096 bits, agrúpelos en aproximadamente 600 grupos de 7 bits en las mismas posiciones de bits y use aproximadamente 600 sumadores 7/3 para reducir el resultado de 4096 bits a menos de 2,000. Luego haces lo mismo una y otra vez, hasta que terminas con pares de bits que se pueden alimentar a un sumador completo ordinario.
fuente