Je vous propose une variante aux MPO, le MRA (qui pourra pourquoi pas, aboutir au MPROA qui serait la version la plus optimisée et rapide...).
Bref, c'est en tombant sur un article des PPX Exchange sur Texas Instrument (consultable ici) que m'est venue l'envie de vous proposer cela.
Bon, le sujet est d'une incroyable originalité et devrait passionner les foules (oui, j'ose parler de foule), à savoir la détermination de la primalité d'un nombre (oh non ! Encore un vieux truc éculé -> non, non, il n'y a pas de n dans le dernier mot ).
L'intérêt malgré tout de cette optimisation est quand on doit faire de nombreux traitements sur des nombres premiers (style défi Turing ou Projet Euler), et qu'on veut faire tourner nos algorithmes sur nos vieux tromblons, c'est que l'algo soit performant en temps de réalisation.
In fine, un gain parfois minime peut se transformer en plusieurs minutes de gagnées sur la machine.
Du coup, l'algorithme proposé dans l'article ci-dessus (et que j'ai aussi retrouvé dans le programme assembleur qui a été fait sur HP71B et qu'on trouve dans les Lif) s'appuie sur le principe suivant :
Rien de bien compliqué, on prend le crible d'Eratosthène (je ne sais plus où se met le h d'ailleurs) et on se limite aux trois premiers nombres premiers 2, 3 et 5. On regarde ensuite s'il n'y a pas une cyclicité dans le crible, et ô joie et avec grande surprise, elle apparait tous les 30 nombres (2*3*5).
En fait si on regarde bien, les nombres premiers sont toujours à regarder parmis les suivants : 30n-13, 30n-11, 30n-7, 30n-1, 30n+1, 30n+7, 30n+11, 30n+13 (ce qui fait 8 nombres à tester sur 30, après bien entendu avoir testé les nombres 2, 3, 5 et on démarre ensuite à 30n+7 avec n=0).
Enfin, pour tester un nombre x et voir s'il est premier, il faut donc vérifier s'il est divisible par 2, 3, 5 et par un des nombres de la précédente liste en s'arrêtant à sqr(x).
On retourne alors soit x si le nombre est premier ou le premier diviseur de x.
Je vous propose donc une course de vitesse, rien ne vous empêche d'améliorer l'algo proposé bien au contraire c'est bien le but du jeu (l'implémentation qui en est faite est d'ailleurs déjà largement améliorable, j'en proposerai une version sur TI95).
Le programme doit donc, à partir d'un nombre saisi, renvoyer soit ce nombre s'il est premier, soit son premier diviseur.
Le problème est bien sûr de comparer les perfs entre machines différentes, on pourra toujours faire un tableau des perfs (si en fait ça intéresse au moins quelqu'un, sinon snif, je repartirai tout seul bouder dans mon coin avec mon chrono). L'idéal aussi est d'utiliser, si disponible, les horloges internes (même si parfois, on n'est qu'à la seconde près). Ca pourrait donner aussi quelques benchmarks sympa pour nos machines (je ne dis pas que le sujet est forcément sympa là... )
Bref, sortez vos montres au 1/100e (sauf pour la HP15c, à la minute près suffira ) et bonne optimisation...
Sommaire des MPO
-------------------------------
Résumé des perfs (en prenant le ratio le plus élevé sur les calculs effectués entre la racine carrée du nombre et le temps mis pour le déterminer premier) :
Code : Tout sélectionner
gege - Casio Graph 85 : 562 (soit environ 150 tests de division / s)
- PB700 : 13,1 (3,5) *
- PB100 : 71 (19) **
C.Ret - C128D : 381 (102) **************************************
- TI74 : 111 (30) ***********
- HP28S : 177 (47) ******************
- HP41C : 20,8 (5,5) **
zpalm - HP41CX : 24,8 (6,5) **
- HP29E : 11,5 (3) *
- HP15CLE : 810 (216) *********************************************************************************
alain1261 - PB100 : 75 (20) *******
- Fx702p : 17,2 (4,5) **
caloubugs - TI95 : 45 (12) *****
- X07 : 88 (23,5) *********
- Z-1GR Basic : 375 (100) **************************************
- Z-1GR C : 673 (179) *******************************************************************
- HP39gII : 2750 (733) XXX
- HP71B Assembleur : 333 (89) *********************************
- PSION 5MX : 71870 (19200) XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
- PB-1000 : 95 (25) **********
- FX-880P : 126 (34) *************
- PC-1403 : 32 (9) ***