J'espère que vous vous êtes bien amusés avec le Défi 4. Si vous avez une idée pour un défi intéressant, n'hésitez pas à me la faire savoir. Je suis toujours à la recherche de contenu intéressant !
Félicitations, @landon ! Vous avez obtenu les réponses les plus rapides (hors personnel) pour les défis des 100 paires de nombres à 1 000 chiffres (9,88 s) et du chiffre le plus long (7 150). Non seulement c'était le seul script capable de lire les 100 paires de nombres à 1 000 chiffres en moins de 10 secondes (le plus proche n'en pouvait lire que 10), mais il pouvait aussi multiplier deux nombres 3,5 fois plus grands que le plus proche ! De plus, c'était le plus court de tous les scripts (personnels et non-personnels) avec un peu plus de 1 000 caractères. Je l'ai inclus dans les scripts ci-dessous. Le total des points après quatre défis est le suivant :
Avant d'aborder la multiplication de grands nombres, parlons de la vectorisation d'une chaîne de chiffres, c'est-à-dire de sa transformation en vecteur. Comme nous l'avons vu le mois dernier, analyser une chaîne de chiffres un par un avec Substr dans une boucle est extrêmement lent. Il nous reste donc deux alternatives : 1) décomposer la chaîne en unités individuelles, puis les reconstituer sous une forme transformable en vecteur (avec Analyser , par exemple) ; 2) utiliser la recherche de motifs. Mon premier réflexe serait d'utiliser la première approche. Pendant des années, j'ai résisté à l'envie d'apprendre les fonctions de recherche de motifs JSL. L'effort était trop important, les informations et les exemples trop rares, et j'étais trop paresseux. Je pensais avoir tout ce qu'il me fallait avec la fonction expression régulière , que je connaissais très bien. Plus maintenant.
Ces défis m'ont ouvert les yeux sur la rapidité et l'efficacité de la correspondance de motifs. Comme me l'a expliqué @Craige_Hales , développeur responsable de ces fonctions et participant régulier aux défis, les routines de correspondance de motifs en JSL constituent la base de la construction d' expressions régulières . Pour démontrer leur efficacité, exécutez le code de Exemple de vectorisation.JSL , qui compare quatre méthodes de vectorisation différentes. J'ai également inclus une courte fonction permettant de générer une longue chaîne de nombres aléatoires dans le script. Pour une chaîne de 10 000 nombres, analyser les chiffres un par un dans une boucle est de loin la plus lente, prenant environ 11 secondes sur ma machine. Utiliser Mots et Liste de concaténation pour décomposer et reconstruire les chiffres en une chaîne analysable en vecteur est bien plus efficace (0,0965 s).
Faire la même chose avec Expression régulière et Analyser est légèrement meilleur (0,08543). La correspondance de motifs réduit ce temps de manière impressionnante de 4 fois (0,02179) ! Si les différences de temps sont minimes pour 50 000 chiffres, si l'on considère 5 000 000 chiffres, les deux approches d'analyse prennent environ 10 minutes, tandis que la correspondance de motifs prend 2 secondes, avec une mise à l'échelle quasi linéaire, contrairement aux autres méthodes ! Pour en savoir plus sur la correspondance de motifs en JSL, consultez les scripts écrits par @Craige_Hales ou @David_Burnham (qui a publié quelques articles de blog avec plus d'informations et d'exemples ).
Passons maintenant aux routines de multiplication. La correspondance de motifs est utilisée pour toute vectorisation. De plus, les algorithmes d'addition les plus rapides du dernier défi sont utilisés dans le premier exemple. La première approche ( multiplierBig Slow.JSL ) n'utilise rien de plus que ce que nous avons appris dans les défis précédents. Elle multiplie les chiffres deux par deux, en veillant à ajouter des zéros en fonction de la position du multiplicande et du multiplicateur (par exemple, ajouter cinq zéros lorsqu'un chiffre des centaines est multiplié par un chiffre des dizaines). Bien que la fonction ordonne les entrées de manière à ce que la première soit plus grande, cela n'apporte aucun avantage. Le même nombre d'opérations est effectué. Cependant, cela changera dans le dernier exemple. La fonction est lente, mettant près de 30 secondes pour traiter un ensemble de 100 nombres de 100 chiffres.
Dans multiplyBig Faster.JSL, le nombre de chiffres d'un registre passe de un à sept, soit environ la moitié du nombre de chiffres que JSL peut représenter sans débordement. La raison de ce choix est évidente lorsque l'on multiplie deux grands nombres à sept chiffres, dont le résultat peut atteindre quatorze chiffres. Un registre à sept chiffres pouvant contenir quatorze chiffres, la routine d'addition utilisée dans le dernier exemple doit être modifiée afin que tout chiffre au-delà du septième soit reporté au registre suivant. Malgré cela, le code obtenu est considérablement plus court, car seuls les nombres positifs sont pris en compte. De plus, les résultats sont nettement meilleurs pour la multiplication de 100 paires de nombres à 100 chiffres (0,04375 s). Cette implémentation multiplie également correctement 100 paires de nombres à 1 000 chiffres (1,54 s).
Grâce à une simple modification, vous pouvez aller encore plus vite. Plutôt que de multiplier un registre à la fois, multiplierBig Fastest.JSL utilise les opérations matricielles JSL pour multiplier chaque registre du nombre le plus court par le nombre entier du nombre le plus grand. Cette approche est plus rapide que la précédente, atteignant 0,3015 seconde pour 100 paires de 1 000 chiffres, soit un gain de 5 fois.
Et vous pouvez aller encore plus vite. Le fichier multiplyBig – Brady.JSL , bien que légèrement plus lent pour multiplier des nombres à 1 000 chiffres, s'est avéré supérieur lorsque la taille des nombres atteignait environ 2 000 chiffres et plus. Cela a été réalisé en modifiant l'ordre des opérations afin que les multiplications et les additions puissent être effectuées dans la même boucle. Les détails de ce processus dépassent mon champ d'application, mais @brady_brady me dit qu'il serait ravi de rédiger un court article que je pourrai ajouter à cet article si cela vous intéresse. Plus rapide ? Peut-être. Il existe deux algorithmes de multiplication notables, généralement utilisés en cryptologie, qui réduisent le nombre d'opérations de multiplication de O(n 2 ) à O(n 1,58 ) ou moins . Comme ils nécessitent davantage d'opérations d'addition avec de grands nombres, il est difficile de dire s'ils seraient plus rapides en JSL. Au moment de la rédaction de cet article, j'ai essayé, sans succès, d'implémenter une version JSL rapide de ces algorithmes.
1er août 2020 : Merci à @Craige_Hales d'avoir détecté un bug dans multiplierBig Fastest.JSL . J'ai corrigé le problème. J'ai également ajouté le script multiplyBig de Craige, que je comptais faire mais que j'avais oublié. Il utilise des tables de correspondance pour accélérer l'algorithme (avec quelques réserves). Son script est entièrement commenté, comme d'habitude.
