Ojalá te hayas divertido Reto 4 . En el futuro, si tienes una idea de algo que sería un buen desafío, házmelo saber. ¡Siempre estoy buscando buen material!
Felicidades, @aterrizar !Tuviste las entradas más rápidas (que no pertenecen al personal) tanto para los desafíos de 100 pares de 1000 dígitos (9,88 segundos) como para los de dígitos más largos (7150). No solo era 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 podía manejar 10), sino que también podía multiplicar dos números 3,5 veces más grandes que la siguiente entrada más cercana. Además, era el más corto de todos los guiones (personal y no personal) con poco más de 1.000 caracteres. Lo he incluido en los scripts a continuación. Los puntos totales después de cuatro desafíos son:
Antes de hablar de multiplicar números grandes, hablemos de descomprimir 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 la vez usando substrato en un bucle es dolorosamente lento. Esto nos deja dos alternativas generales: 1) deconstruir la cadena en unidades individuales, luego juntarlas nuevamente en una forma que pueda convertirse en un vector (usando Analizar gramaticalmente , por ejemplo) o, 2) usando la coincidencia de patrones. Mi inclinación inicial sería utilizar el enfoque 1. Durante años, me he resistido a aprender sobre las funciones de coincidencia de patrones JSL. El esfuerzo fue demasiado grande, la información y los ejemplos demasiado escasos y yo era demasiado vago. Pensé que tenía todo lo que necesitaba con el expresión regular función, 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 habitual de los desafíos, las rutinas de coincidencia de patrones en JSL son la base sobre la cual expresión regular está construído. 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 incluí una función corta para generar una larga cadena 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, con diferencia, el más lento, ya que en mi máquina lleva unos 11 segundos. Usando Palabras y Lista de concatenaciones deconstruir y reconstruir los dígitos en una cadena que pueda analizarse en un vector es mucho mejor (0,0965 segundos).
Haciendo lo mismo usando expresión regular y Analizar gramaticalmente es ligeramente mejor que eso (0,08543). ¡La coincidencia de patrones reduce este tiempo en un sorprendente 4X (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, escalando casi linealmente, ¡a diferencia de los otros métodos! Si desea obtener más información sobre la coincidencia de patrones en JSL, eche un vistazo a los scripts escritos por @Craige_Hales o @David_Burnham (quién tiene algunas publicaciones de blog propias con más información y ejemplos .)
Pasemos a las rutinas de multiplicación. La coincidencia de patrones se utiliza para toda la vectorización. Además, en el primer ejemplo se utilizan los algoritmos de suma más rápidos del último desafío. El primer enfoque ( multiplicarBig Slow.JSL ) no utiliza nada más allá de lo que hemos aprendido en los desafíos hasta ahora. Multiplica dígitos de dos en dos, asegurándose de agregar ceros dependiendo de la posición del multiplicando y del multiplicador (por ejemplo, sumando 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 más grande, esto no tiene ningún beneficio. Se realiza el mismo número de operaciones. Sin embargo, esto cambiará en el ejemplo final. La función es lenta y tarda casi 30 segundos en completar un conjunto de 100 números de 100 dígitos.
En multiplicarBig Faster.JSL el número de dígitos en un registro aumenta de uno a siete, aproximadamente la mitad del número de dígitos que JSL puede representar sin desbordamiento. La razón de esta elección es evidente cuando multiplicamos dos números grandes de siete dígitos, cuyo resultado puede llegar a catorce dígitos. Dado que un registro de siete dígitos puede contener 14 dígitos, la rutina de suma utilizada en el último ejemplo debe modificarse para que todo lo que supere el séptimo dígito se lleve al siguiente registro. A pesar de esto, el código resultante es considerablemente más corto ya que sólo es necesario considerar números positivos. Además, los resultados mejoran sustancialmente al multiplicar 100 pares de números de 100 dígitos (0,04375 segundos). Esta implementación también hace un trabajo razonable al multiplicar 100 pares de 1000 dígitos (1,54 segundos).
Con un simple cambio, puedes ir aún más rápido. En lugar de multiplicar un registro a la vez, multiplicarBig Fastest.JSL utiliza operaciones matriciales JSL para multiplicar cada registro en el número más corto con el número entero más grande. Este enfoque es más rápido que el anterior, registrando 0,3015 segundos para 100 pares de 1000 dígitos, una mejora 5 veces mayor.
Y puedes ir aún más rápido. El archivo multiplicarBig – 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ó aproximadamente 2000 dígitos y más. Esto se logró cambiando el orden de las operaciones para que las multiplicaciones y sumas pudieran realizarse en el mismo ciclo. Los detalles detrás de esto están más allá de lo que me gustaría cubrir, pero @brady_brady me dice que le encantaría escribir un breve artículo 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 utilizan normalmente en criptología y que reducen el número de operaciones de multiplicación de O(n 2 ) a En 1,58 ) o más bajo . 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. En el momento de esta publicación, lo 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 atrapar un error en multiplicarBig Fastest.JSL . He corregido el problema. También agregué el script multipleBig de Craige, que tenía la intención de hacer pero lo olvidé. Utiliza tablas de búsqueda como una forma de acelerar el algoritmo (con algunas advertencias). Su guión está minuciosamente comentado, como es habitual.
