Misez p'tit Optimisez n°54 : simplification de racines

[Céline]

Dans le code de C.Ret N prend alternativement les valeurs 6k+1 et 6k-1 dont on est sûr qu'elles ne sont divisibles ni par 2 ni par 3.
Avec ta bascule B qui prend les valeurs 2 ou 4 tu testes parfois des multiples de 3, donc tu as plus de tests que C.Ret, mais moins que moi ou babaorhum qui testons tous les entiers

[jxano]

Avec ta bascule B qui prend les valeurs 2 ou 4 tu testes parfois des multiples de 3,

Précisément pas. Mon système évite les multiples de 3 impairs (9, 15, 21, etc.) :
5 (->2) 7 (-> 4) 11 (-> 2) 13 (-> 4) 17 (-> 2) 19 (-> 4) 23 (-> 2) 25 etc.

Mais je commence à 5, ce qui m'oblige à tester 2 et 3 à part.

En testant l'algo de C.Ret, j'ai été un peu déçu : il fait le même travail. Je pensais qu'il sauterait des multiples de 5... mais non.

[Céline]

D'accord, je n'avais pas suffisamment regardé ton code

[C.Ret]

[...]En testant l'algo de C.Ret, j'ai été un peu déçu : il fait le même travail. Je pensais qu'il sauterait des multiples de 5... mais non.

Très juste et excellente analyse.

En effet nos deux codes se valent et vont tester les mêmes facteurs.

La seule diffèrence provient du fait que j'utilise une varaible intermédiaire qui me permet , par le jeu de l'initialisation, de tester les facteurs 2 et 3 avant de parcourrir la liste des 6k-1 et 6k+1

Cela permet de "recycler" les lignes de code; les tests sont identiques

Le code de jxano peut être optimisé à l'aide d'un sous-programme, ce qui est aussi une façon de "recycler" les lignes de code:

Code : Tout sélectionner

40 "S": INPUT "√ ? ";R:F=1
42 N=2:GOSUB 50
43 N=3:GOSUB 50
45 N=5:B=4
46 GOSUB 50
47 B=6-B,N=N+B: IF N*N<R GOTO 46
48 PRINT F;"√";R: END

50 T=R/N/N: IF T= INT T LET F=N*F,R=T: GOTO 50
52 RETURN

J'aime bien la 'bascule' avec B. Elle va remplacer mon habitude du 6*K+S qui nécessite en fait une variable de plus.



Il existe une autre façon de générer une liste de facteurs premier plus nombreux. Elle se base sur la relative périodicité des intervalles entre les nombre premiers.

Une première méthode considère une période de 30 ( 2*3*5 = 30 ) :
Une seconde considère de plus le facteur 7 et nécessite donc de programmer les intervalles sur 210 (=2*3*5*7) nombre
Il faut que je retrouve ces deux méthodes.

En attendant, j'améliore mon algorithme (grâce à l'astuce de jxano ! )

Code : Tout sélectionner

1 "S" AREAD X : F=1,B=1,I=2
2 Q=X/F/I/I:IF Q=INT Q LET F=F*I*I:GOTO 2
3 IF Q>1 LET I=I+B,B=2+(4-B)*(I>5):GOTO 2
4 PRINT "√";X;"=";√F;".√";X/F;"=";√x : END

J'aime bien la ligne 4 - Parfaitemment illisible

[huc6don9]

Dans la ligne:

Code : Tout sélectionner

Q=X/F/I/I:IF Q=INT Q LET F=F*I*I:GOTO 2

il y a beaucoup de division (qui normalement sont plus coûteuse que les multiplications).
suggestion: créer une nouvelle variable P=(F*I*I) ce qui évite de refaire ce calcul.

Avoir des variables de type float, ce ne doit pas être le plus rapide,
est-ce que vous avez des opérations division entière ou modulo à disposition ?

[Céline]

est-ce que vous avez des opérations division entière ou modulo à disposition ?

Non, pas sur le pc-1500A

[C.Ret]

Dans la ligne:

Code : Tout sélectionner

Q=X/F/I/I:IF Q=INT Q LET F=F*I*I:GOTO 2

il y a beaucoup de division (qui normalement sont plus coûteuse que les multiplications).
suggestion: créer une nouvelle variable P=(F*I*I) ce qui évite de refaire ce calcul.

Excellente suggestion !

Code : Tout sélectionner

1 "S" AREAD X : F=1,B=1,I=2
2 P=F*I*I:Q=X/P:IF Q=INT Q LET F=P:GOTO 2
3 IF Q>1 LET I=I+B,B=2+(4-B)*(I>5):GOTO 2
4 PRINT "√";X;"=";√F;".√";X/F;"=";√x : END

Avoir des variables de type float, ce ne doit pas être le plus rapide,
est-ce que vous avez des opérations division entière ou modulo à disposition ?

Le SHARP PC-1211 utilise deux processeurs 4 bits; il n'y a donc pas de format 'float', tous les calculs sont en quelque sorte du BCD (binaire codé décimal).

[jxano]

Il existe une autre façon de générer une liste de facteurs premier plus nombreux. Elle se base sur la relative périodicité des intervalles entre les nombre premiers.

Une première méthode considère une période de 30 ( 2*3*5 = 30 ) :
Une seconde considère de plus le facteur 7 et nécessite donc de programmer les intervalles sur 210 (=2*3*5*7) nombre
Il faut que je retrouve ces deux méthodes.

Il s'agit en fait de réduire l'ensemble des entiers susceptibles d'être premiers.

Pour 2.3.5, on peut tabler sur huit valeurs à ajouter successivement au diviseur N (comparé à 10 pour 2.3 sur le même intervalle), tout en plombant la performance du programme, puisqu'il y a une multiplication sous-jacente pour l'accès à la variable indicée.

J'ai fait il y a dix ans une étude pour 2.3.5.7.11 (produit 2310). Son résultat est matérialisé sous la forme d'un tableau Excel de 480 lignes (et d'un mètre de haut sur papier, que j'ai affiché chez moi) contenant tous les premiers jusqu'à 120 103. Sur les 480 valeurs de la colonne de gauche, toutes ne sont pas premières. En effet, les entiers factorisables par des premiers à partir de 13 et inférieurs à 2310 sont susceptibles de « produire » des premiers sur les intervalles supérieurs 2310p à 2310(p+1), p strictement positif. Détail amusant : tout k de l'ensemble des 480 entiers de référence a son symétrique 2310-k dans l'ensemble, 2 excepté.

[huc6don9]

Un autre idée: Calculer et garder les "résidus" de la décomposition en facteur premier, c'est à dire stocker le produit des nombres premiers avec une décomposition impaire,
et diviser Q par ce produit, cela permettrait de réduire le nombre d'itération (et de ne pas tester des nombres premiers qui sont trop grands). est-ce rentable ...

[ledudu]

Machine : CASIO Pro FX-1
Langage : Fortran Casio
111 pas / 127

Code : Tout sélectionner

ST#0 : ENT 0 : 1 = K2 : 2 = K1 : 9 = K10 10x:              ' Pas 23
ST#1 : 6 = 1 x 1 : IF 6 = 0 : 2 : 2 : 5 :                  ' Pas 43
ST#2 : 3 = 0 / 6 : 4 = 3 + 9 - 9 : IF 3 = 4 : 3 : 4  : 3 : ' Pas 71
ST#3 : 1 = 1 + K1 : GOTO 1 :                               ' Pas 84
ST#4 : 0 = 3 : 2 = 2 x 1 : GOTO 1 :                        ' Pas 100
ST#5 : ANS 2 : 0 : GOTO 0:                                 ' Pas 111

START
Etape ENT 0 : saisir 7936 puis appuyer sur ENT
Etape ANS 2 : affichage de 16 en 10' - appuyer sur ANS
Etape ANS 0 : affichage de 31

vous connaissez la fx-92 Collège ? Entre autres extraordinaires fonctionnalités, elle simplifie les racines carrées

C'est vrai. Il faut prendre des versions un peu récentes tout de même.

Merci pour ce MPO.

D'autres programmes pour PRO Fx-1.