¿Cómo se multiplican los números enteros en C++?

Me preguntaba qué tipo de método se utilizó para multiplicar números en C++. ¿Es la larga multiplicación tradicional de libros escolares? Fürer's algorithm? Toom-Cook?¿Cómo se multiplican los números enteros en C++?

Me preguntaba porque tendré que multiplicar números extremadamente grandes y necesitar un alto grado de eficiencia. Por lo tanto, la multiplicación larga de libros escolares tradicionales O(n^2) podría ser demasiado ineficiente, y necesitaría recurrir a otro método de multiplicación.

Entonces, ¿qué tipo de multiplicación usa C++?

Fuente

2012-03-10 fdh

+13

Sea lo que sea que haga el chip, lo hace. – bmargulies

El título me hizo pensar en enteros reproduciéndose :) – harold

@harold Primero deben hacer algo llamado "citas". – Manish

Usted parece que faltan varias cosas cruciales aquí:

Hay una diferencia entre nativa la aritmética y bignum aritmética.
Parece que le interesan bignum aritmética.
C++ no es compatible con bignum aritmética. Los tipos de datos primitivos generalmente son nativos aritmética para el procesador.

Para obtener la aritmética de bignum (precisión arbitraria), debe implementarla usted mismo o utilizar una biblioteca. (como GMP) A diferencia de Java y C# (entre otros), C++ no tiene una biblioteca para la aritmética de precisión arbitraria.

Todos esos algoritmos de lujo:

Karatsuba: O(n^1.585)
Toom-cocción: < O(n^1.465)
FFT-Based: ~ O(n log(n))

son aplicables sólo a bignum aritmética que se implementan en las bibliotecas bignum. Lo que el procesador usa para sus operaciones aritméticas nativas es algo irrelevante ya que es , por lo general, tiempo constante.

En cualquier caso, no recomiendo que intente implementar una biblioteca bignum. Lo he hecho antes y es bastante exigente (especialmente las matemáticas). Entonces es mejor que uses una biblioteca.

Fuente

2012-03-10 19:08:56 Mysticial

+1 para adivinar las intenciones del OP :-) – hirschhornsalz

Hasta llegar a números muy grandes, el método que aprendió en la escuela primaria tendrá un mejor rendimiento en la práctica. Por supuesto, usa una base más grande que 10.:-) Dependiendo de sus necesidades, 2^32, 2^64, o 10^9 hacen bases convenientes (una potencia de 10 es útil para analizar/imprimir sus números en la base 10 es importante para optimizar, y 10^9 es el mayor potencia que cabe en 32 bits). –

Todo depende de la biblioteca y el compilador utilizados.

Fuente

2012-03-10 19:07:07 gangelo

En C++ la multiplicación entera es manejada por el chip. No existe un equivalente de BigNum de Perl en el lenguaje estándar, aunque estoy seguro de que existen tales bibliotecas.

Fuente

2012-03-10 19:07:59 Joel

To nitpick: No necesariamente. Es perfectamente posible que las implementaciones incluyan tipos numéricos (incluso 'int', aunque * que * debería ser bastante raro) que la arquitectura dirigida no admite, y en su lugar implementan operaciones aritméticas en ellos como llamadas a alguna biblioteca en tiempo de ejecución. Considere los enteros de 128 bits o, posiblemente, los enteros de 64 bits en los sistemas de 32 bits. Además, solía haber muchos chips sin unidad de coma flotante (FPU). – delnan

@delnan: Rara, pero no inexistente: el procesador de 8 bits 6502 no tiene instrucciones aritméticas de 16 bits, por lo que el compilador CC65 C debe implementar la aritmética 'int' mediante secuencias de instrucciones de 8 bits y llamadas a bibliotecas. – han

¿Qué quiere decir con "números extremadamente grandes"?

C++, como la mayoría de los demás lenguajes de programación, usa el hardware de multiplicación incorporado en el procesador. Exactamente cómo funciona eso no está especificado por el lenguaje C++. Pero para enteros normales y números de coma flotante, no podrá escribir algo más rápido en el software.

Los números más grandes que pueden ser representados por los diversos tipos de datos puede variar entre diferentes implementaciones, pero algunos valores típicos son 2147483647 para int, 9223372036854775807 para largo, y 1.79769e + 308 para doble.

Fuente

2012-03-10 19:08:37

Se realiza en hardware. por la misma razón, los números grandes no funcionarán. El número más grande que puede representar C++ en el hardware de 64 bits es 18446744073709551616. si necesita números más grandes, necesita una biblioteca de precisión arbitraria.

Fuente

2012-03-10 19:09:42 Dani

¿Qué hay de los dobles? Además, el tamaño exacto de la mayoría de los tipos de datos depende del compilador. También creo que algunos compiladores ofrecen tipos enteros de 128 bits. – delnan

c llanura ++ utiliza instrucciones de la CPU mult (o libro de texto de multiplicación usando bitshifts y adiciones si su CPU no tiene tal instrucción.)

si necesita la multiplicación rápida de un gran número, sugeriría mirar a GMP (http://gmplib.org) y el uso de la ++ interfaz c de gmpxx.h

Fuente

2012-03-10 19:11:27

Si se trabaja con un gran número de la multiplicación de enteros estándar en C++ ya no va a funcionar y que puedes usar una biblioteca que proporciona la multiplicación de precisión arbitraria, como GMP http://gmplib.org/

Además, no debe preocuparse por el rendimiento antes de escribir su aplicación (= optimización prematura). Estas multiplicaciones serán rápidas, y lo más probable es que muchos otros componentes en su software causen mucha más desaceleración.

Fuente

2012-03-10 19:12:37 johanvdw

¿Cuán grandes serán estos números? Incluso los lenguajes como python pueden hacer 1e100*1e100 con números enteros de precisión arbitrarios más de 3 millones de veces por segundo en un procesador estándar. Esa es la multiplicación a 100 lugares significativos que toman menos de una millonésima de segundo. Para poner eso en contexto, hay solo alrededor de 10^80 átomos en el universo observable.

Escriba primero lo que quiere lograr y luego optimícelo si es necesario.

Fuente

2012-03-10 19:21:45 Dunes

¿Cómo se multiplican los números enteros en C++?

Respuesta

Cuestiones relacionadas