Espero que te hayas divertido con el Desafío 4. En el futuro, si tienes alguna idea que pueda ser un buen Desafío, házmelo saber. ¡Siempre busco buen material!
¡Felicitaciones, @landon ! Tuviste las participaciones más rápidas (sin personal) en los desafíos de 100 pares de 1000 dígitos (9,88 segundos) y de dígitos más largos (7150). No solo fue el único script capaz de leer los 100 pares de números de 1000 dígitos en menos de 10 segundos (el siguiente más cercano solo pudo leer 10), sino que también pudo multiplicar dos números 3,5 veces más grandes que el siguiente más cercano. Además, fue el script más corto de todos (personal y no personal), con poco más de 1000 caracteres. Lo he incluido en los scripts a continuación. La puntuación total después de cuatro desafíos es:
Antes de hablar de multiplicar números grandes, hablemos de desempaquetar o vectorizar una cadena de dígitos: convertir una cadena de dígitos en un vector de números. Como vimos el mes pasado, analizar una cadena de dígitos uno a uno usando Sust. en un bucle es extremadamente lento. Esto nos deja dos alternativas generales: 1) deconstruir la cadena en unidades individuales y luego volver a unirlas en una forma que pueda convertirse en un vector (usando Analizar gramaticalmente , por ejemplo) o 2) usar la coincidencia de patrones. Mi inclinación inicial sería usar el enfoque 1. Durante años, me he resistido a aprender sobre las funciones de coincidencia de patrones de JSL. El esfuerzo era demasiado grande, la información y los ejemplos demasiado escasos, y yo era demasiado perezoso. Pensé que tenía todo lo que necesitaba con la función Expresión regular , algo que conocía muy bien. No más.
Estos desafíos me han abierto los ojos a la velocidad y eficiencia de la coincidencia de patrones. Como me explicó @Craige_Hales , el desarrollador responsable de estas funciones y participante regular de los desafíos, las rutinas de coincidencia de patrones en JSL son la base sobre la que se construye Expresión regular . Para demostrar su eficiencia, ejecute el código en Ejemplo de vectorización.JSL , que compara cuatro métodos diferentes de vectorización. También he incluido una función corta para generar una cadena larga de números aleatorios en el script. Para una cadena de 10,000 números, analizar los dígitos uno a la vez en un bucle es, por lejos, lo más lento, tomando aproximadamente 11 segundos en mi máquina. Usar Palabras y Lista de concatenaciones para deconstruir y reconstruir los dígitos en una cadena que se pueda analizar en un vector es mucho mejor (0.0965 segundos).
Hacer lo mismo con Expresión regular y Analizar gramaticalmente es ligeramente mejor (0,08543). La coincidencia de patrones reduce este tiempo en unas impresionantes 4 veces (0,02179). Si bien las diferencias de tiempo son minúsculas para 50 000 dígitos, si consideramos 5 000 000 de dígitos, ambos métodos de análisis tardan unos 10 minutos, mientras que la coincidencia de patrones tarda 2 segundos, con una escala casi lineal, a diferencia de los otros métodos. Si quieres saber más sobre la coincidencia de patrones en JSL, consulta los scripts de @Craige_Hales o @David_Burnham (quien tiene algunas entradas de blog con más información y ejemplos ).
Adelante con las rutinas de multiplicación. La coincidencia de patrones se utiliza para toda la vectorización. Además, los algoritmos de suma más rápidos del último desafío se utilizan en el primer ejemplo. El primer enfoque ( multiplyBig Slow.JSL ) no utiliza nada más allá de lo que hemos aprendido en los desafíos hasta ahora. Multiplica los dígitos de dos en dos, asegurándose de agregar ceros dependiendo de la posición del multiplicando y el multiplicador (por ejemplo, agregar cinco ceros cuando un dígito de las centenas se multiplica por un dígito de las decenas). A pesar de que la función ordena las entradas para que la primera sea mayor, esto no es de ninguna utilidad. Se realiza el mismo número de operaciones. Sin embargo, esto cambiará en el ejemplo final. La función es lenta, tardando casi 30 segundos en pasar por un conjunto de 100 números de 100 dígitos.
En multiplyBig Faster.JSL, el número de dígitos de un registro aumenta de uno a siete, aproximadamente la mitad de los dígitos que JSL puede representar sin desbordamiento. La razón de esta elección es evidente al multiplicar dos números grandes de siete dígitos, cuyo resultado puede ser de hasta catorce dígitos. Dado que un registro de siete dígitos puede contener 14, la rutina de suma utilizada en el último ejemplo debe modificarse para que cualquier valor posterior al séptimo dígito se transfiera al siguiente registro. A pesar de esto, el código resultante es considerablemente más corto, ya que solo se consideran números positivos. Además, los resultados mejoran sustancialmente al multiplicar 100 pares de números de 100 dígitos (0,04375 s). Esta implementación también realiza una buena multiplicación de 100 pares de 1000 dígitos (1,54 s).
Con un simple cambio, puedes ir aún más rápido. En lugar de multiplicar un registro a la vez, multiplyBig Fastest.JSL utiliza operaciones matriciales JSL para multiplicar cada registro del número más corto por el número más grande. Este método es más rápido que el anterior, con un tiempo de ejecución de 0,3015 segundos para 100 pares de 1000 dígitos, una mejora de 5 veces.
Y puedes ir incluso más rápido. El archivo multiplyBig – Brady.JSL , aunque ligeramente más lento para multiplicar números de 1000 dígitos, fue superior cuando el tamaño de los números alcanzó alrededor de 2000 dígitos y más. Esto se logró cambiando el orden de las operaciones para que las multiplicaciones y las sumas se pudieran hacer en el mismo bucle. Los detalles detrás de esto están más allá de lo que me importa cubrir, pero @brady_brady me dice que estaría encantado de hacer una breve redacción que puedo agregar a esta publicación si hay interés. ¿Más rápido? Tal vez. Hay dos algoritmos de multiplicación notables que se usan típicamente en criptología que reducen el número de operaciones de multiplicación de O(n 2 ) a O(n 1.58 ) o menor . Debido a que requieren más operaciones de suma con números grandes, es difícil decir si serían más rápidos en JSL. Al momento de esta publicación, intenté pero no pude implementar una versión JSL rápida de ninguno de estos algoritmos.
1 de agosto de 2020: Gracias a @Craige_Hales por detectar un error en multiplyBig Fastest.JSL . He corregido el problema. También he añadido el script multiplyBig de Craige, que tenía pensado hacer pero olvidé. Utiliza tablas de búsqueda para acelerar el algoritmo (con algunas salvedades). Su script está completamente comentado, como siempre.
