¿Qué complejidad tienen los métodos multiply, divide y pow en BigInteger actualmente? No se menciona la complejidad computacional en la documentación (ni en ningún otro lugar).¿Qué complejidad tienen las operaciones en BigInteger de Java 7?
Si nos fijamos en el código para BigInteger (siempre con JDK), me parece que tiene multiply(..)O (n^2) (en realidad el método es multiplyToLen(..)). El código para los otros métodos es un poco más complejo, pero puedes verte a ti mismo.
Nota: esto es para Java 6. Asumo que no diferirá en Java 7.
Existen varias complejidades de la multiplicación: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations ... ¿Puedes decir O (n^2) aparte de O (n^1.585) o O (n^1.465)? – Joey
Creo que ha habido cambios en Java 7. No recuerdo los detalles que encontré buscando, pero eran escasos. –
Rössel: Existen _exist_ otros algoritmos para la multiplicación, pero Java 6 no los usa. Al multiplicar números grandes sin duda notará la diferencia entre el algoritmo del libro de texto y la multiplicación de Karatsuba. Los otros son menos saltones a menos que llenes la memoria primaria con los números. – Charles
medirlo. Realice operaciones con operandos de aumento lineal y dibuje los tiempos en un diagrama. No olvide calentar la JVM (varias ejecuciones) para obtener resultados válidos de referencia.
Si las operaciones son lineales O (n), cuadrática O (n^2), polinomio o exponencial debe ser obvio.
EDITAR: Aunque puede dar algoritmos límites teóricos, puede que no sean tan útiles en la práctica. En primer lugar, la complejidad no da el factor. Algunos algoritmos lineales o subcuadráticos simplemente no son útiles porque consumen tanto tiempo y recursos que no son adecuados para el problema en cuestión (por ejemplo, la multiplicación de la matriz de Coppersmith-Winograd). Entonces su computación puede tener todos los kludges que solo puede detectar por experimento. Están preparando algoritmos que no hacen nada para resolver el problema, sino para acelerar el solucionador real (acondicionamiento de la matriz). Hay implementaciones subóptimas. Con longitudes más largas, su velocidad puede disminuir drásticamente (falta memoria caché, memoria moviéndose, etc.). Entonces para propósitos prácticos, aconsejo hacer experimentación.
Lo mejor es duplicar cada vez la longitud de la entrada y comparar los tiempos. Y sí, usted haga descubra si un algoritmo tiene complejidad n^1.5 o n^1.8. Simplemente cuadruplica la longitud de entrada y solo necesitas el medio tiempo para 1.5 en lugar de 2. Obtienes de nuevo casi la mitad del tiempo para 1.8 si multiplicas la longitud 256 veces.
Eso podría funcionar. Necesitaría probar valores grandes de n. Si medí el tiempo para multiplicar dos BigIntegers de n bits (t_0) y luego dos BigIntegers de 2n bits (t_1). Entonces podría esperar que la complejidad sea O (n^(log2 (t_1/t_0))). En general, soy un poco escéptico de los métodos empíricos (posiblemente injustamente). –
Este es un enfoque difícil de tomar, sin embargo. _A priori_, no hay razón para pensar que se use un solo algoritmo en lugar de una combinación de algoritmos. Por lo tanto, la escala de 10 dígitos a 1000 dígitos puede ser diferente de la escala de 1000 dígitos a 3000 dígitos. – Charles
Hay una nueva clase de BigInteger "mejor" que no está siendo utilizada por sun jdk para el conservadurismo y la falta de pruebas de regresión útiles (grandes conjuntos de datos). El tipo que hizo los mejores algoritmos podría haber discutido el antiguo BigInteger en los comentarios.
Aquí tiene http://futureboy.us/temp/BigInteger.java
Usted puede comprobar el código fuente. – uckelman
En realidad, ya lo he intentado. Pero parece bastante difícil de analizar sin mucho conocimiento. Espero que alguien que lea StackOverflow tenga ese conocimiento. Quizás eso es ser demasiado optimista? –
¿Hay alguna razón específica por la que menciones Java 7? 'BigInteger' existe desde Java 1.1. –