Usualmente usan árboles de sumadores 4 sobre 2, que son sumadores de tiempo constante que suman cuatro números a dos calculando bits de acarreo y suma de bits en paralelo, sin la necesidad de propagar el acarreo. Se usa un sumador normal (p. Ej., Sumador de búsqueda anticipada) en la parte inferior para obtener un solo número.
Los sumandos se obtienen de la manera obvia al distribuir un multiplicador sobre el otro, utilizando el hecho de que la multiplicación de un solo bit con una cadena de bits se puede calcular utilizando una compuerta AND paralela.
Por lo tanto, la demora es logarítmica. El costo es cuadrático.
- En Codeforces Round # 308 (Div. 2), ¿cómo descubrieron todos la cantidad de dígitos de un número usando un algoritmo eficiente de toma de tiempo? ¿Alguien puede explicarlo?
- ¿Cómo son los problemas de programación competitiva? ¿Son problemas que afectan a la sociedad que pueden resolverse mediante algoritmos informáticos? ¿Puede dar un ejemplo?
- ¿Cuáles son algunos problemas prácticos en los que no se puede evitar el uso de algoritmos con big-O muy grande?
- ¿Hay algoritmos con complejidad [math] \ mathcal {O} [/ math] [math] (\ sqrt {\ log (n)}) [/ math]?
- ¿Hay diferentes algoritmos para diferentes lenguajes de programación?
Para ahorrar un factor constante de cable y, por lo tanto, retrasar, a menudo se usa la decodificación de la cabina.
También existen otros algoritmos, como el algoritmo Karatsuba. y reduzca el costo a algo como [matemáticas] O (n ^ {1.5}) [/ matemáticas]
Creo que Müller-Paul (Computer Architecture) tiene una construcción de tal unidad de multiplicación.
