“Mejor” de qué manera? Si te refieres al algoritmo más eficiente para una computadora para números muy grandes, entonces es el algoritmo de Schonhage-Strassen, con complejidad de tiempo O (n log (n) log (log (n))), donde n es el número de dígitos .
El algoritmo más simple de todos es “simplemente agregue un número al otro el número de veces indicado por el otro”. Este algoritmo tiene complejidad O (N) = O (B ^ n), donde B es la base yn el número de dígitos, N el tamaño del multiplicador. Este algoritmo, por lo tanto, es poco práctico e imposiblemente lento, excepto por pequeños multiplicadores como 2 y 3.
El siguiente algoritmo más simple, y el que usarías en papel, es el método estándar de multiplicación larga que usas en la escuela. Esto tiene complejidad O (n ^ 2).
Por lo tanto, depende de lo que quieras decir con “mejor”. Si quieres multiplicar números realmente grandes muy rápido, querrás usar el primer algoritmo mencionado. Si desea multiplicar números pequeños, otros algoritmos pueden ser mejores (de hecho, en la práctica, el primer algoritmo mencionado es peor que el tercer algoritmo en esta lista cuando los números son pequeños).
- ¿Qué es Combinatorics on Words y qué problemas resuelve?
- Dada una canasta grande de bolas de colores, ¿cuántas canastas diferentes de un tamaño fijo puedes construir?
- ¿Hay algún teorema que relacione el número de coincidencias perfectas en un gráfico no bipartito con su permanente?
- Dados n números del 1 al n, elija dos con reemplazo. ¿Cuál es la expectativa y la varianza del número mayor? ¿Cuál es la distribución?
- Cómo resolver ‘0 0 pares’ en SPOJ
Los algoritmos que son mejores también pueden cambiar con respecto a la representación de números. Por ejemplo, al implementar la aritmética del complemento a 2 en hardware, se usaría algo como el “algoritmo de multiplicación de Booth”.