TROUVER LES DIVISEURS D'UN NOMBRE ENTIER

Commentaire de f0xi le 21/01/2008 04:08:25 administrateur CS

J'ai oublier de preciser qu'on peu renomer le fichier fmd.ex_ en fmd.exe pour ceux qui desire avoir la version compilée (non delphiistes).

Commentaire de Debiars le 26/01/2008 10:40:06

J'aurais aimé avoir quelques commentaires m'expliquant le pourquoi et le comment de la vitesse d'exécution de la fonction optimisée.
Après force recherches, je vous livre le résultat de mes investigations.
Pour faciliter, appelons A la fonction "simpliste" telle que j'aurais pû l'écrire moi-même et B la fonction sophistiquée et optimisée à la Foxi.
Au premier rabord, on pourrait penser que B met deux fois moins de temps que A, vu que l'on divise le nombre testé par deux, en stockant à la fois le diviseur et le quotient,ce qui nous donnerait 26168 ms pour A et 13410 ms pour B. Que nenni, B met 0 ms. Diantre, me dis-je.
En faisant tourner à vide les deux boucles while, j'arrive effectivement à ce résultat. J'en déduis donc que ça se passe à l'intérieur de la boucle. C'est alors que je découvre le petit "break" exécuté quand le diviseur est plus grand que le quotient.
En examinant le résultat de l'opération (1152 chiffres), on constate que le nombre de boucles entre deux chiffres pour trouver la première moitié des diviseurs, varie entre 1 et 318, contre 318 et 432432000 pour la deuxième moitié.
Conclusion : la fonction B effectue 29568 boucles contre 86486400 pour la fonction A. Génial.
Néanmoins, mon cher Foxi, tu aurais pû supprimer ceci :

if (NPrime and $1) = 1 then
    PassMax := (NPrime+1) div 2
  else
    PassMax := NPrime div 2;
    
et remplacer  
     while DivisorA <= PassMax do
par while DivisorA <=  NPrime do

ce qui ne change rien au résultat puisque de toute façon tu breakes avant d'arriver à PassMax, et cela aurait évité de m'embrouiller la comprenette.

Commentaire de MAURICIO le 28/01/2008 11:23:03 administrateur CS

Je suis tout à fait d' accord avec Debiars: ça manque cruellement d' explications!

Commentaire de f0xi le 28/01/2008 23:03:48 administrateur CS

while i <= (Number div i) do << ajoute une division a chaque iteration!

Result[High(Result)]   := i ;
Result[High(Result)-1] := Number div i ; << et le control des doublons ?!


j'ai ajouter des commentaires detaillés ...

Commentaire de f0xi le 28/01/2008 23:22:24 administrateur CS

@debiars :

tu aurais pû supprimer ceci :

if (NPrime and $1) = 1 then
    PassMax := (NPrime+1) div 2
  else
    PassMax := NPrime div 2;
    
et remplacer  
     while DivisorA <= PassMax do
par while DivisorA <=  NPrime do


non non mon amis! comme expliquer dans la source,
la definition de PassMax permet d'avoir une vraie limite calculée par rapport a si le nombre est paire ou impair (+1) dans un premier lieux,
puis fixe une limite certaine dans le cas par exemple des nombres premiers qui ne declanches pas le break conditionné par DivisorA < DivisorB ou DivisorA = DivisorB
puisque aprés la decouverte de 1 par NPrime mod DivisorA puis de NPrime par NPrime div DivisorA, les conditions sont toutes ignorée et c'est la ou il reste encore une petite optimisation possible a faire.

dans le cas des nombres premiers la condition de boucle while DivisorA <= NPrime do
ferait donc en sorte d'etre itérée NPrime fois au lieux de PassMax fois (NPrime/2)
ce qui rendrais la fonction aussi lente que la version basique.

c'est la ou ma fonction optimisée a une faille, c'est qu'en cas d'un nombre premier NPrime n'ayant que pour diviseur 1 et NPrime lui meme, on doit quand même essayer jusqu'a NPrime/2 comme valeur de DivisorA, ce qui est un peu mieux que la basique mais pas encore parfait.

il nous faudrait donc ajouter une condition if DivisorA > DivisorB then break; avant la condition if (NPrime mod DivisorA) = 0 then ...
mais cela revient a ajouter une division (div) puis un saut conditionnel (cmp,  jl) a chaque iteration de la boucle ce qui pourrait penaliser la fonction sur les nombres non premier (donc les plus frequents).
d'ou le pourquoi du non ajout de cette condition, bien qu'au vus des performances globale ce ne serait pas forcement TRES penalisant.

voila, aprés cette lourde explication qui donne mal au crane, je vous remercie pour vos commentaires :)

Commentaire de f0xi le 28/01/2008 23:34:45 administrateur CS

@whitehippo :

je devrais la fermer avant d'avoir tester!
ta fonction est trés trés bien sauf pour certains chiffre (doublons de diviseurs)
qui peut etre résolus par une petite condition :
DA < DB /// DA = DB
:)

par contre tu m'a fait trouver un truc qui permet d'ameliorer encore la mienne :)

Commentaire de f0xi le 28/01/2008 23:53:59 administrateur CS

essaye avec : 1, 4, 9, 16, 25, 49 et surrement d'autres :)

je vais mettre a jours la source avec une petite modif que je te doit :)

Commentaire de f0xi le 29/01/2008 06:26:15 administrateur CS

J'ai battus le score de BruNews!

pour 864 864 000 :
1657 cycles (version actuelle de l'algo)
1769 cycles (version C de brunews)

mais bon connaissant le bonhomme, il vas me pondre un truc version pur Asm qui dechire tout par calcul simplifié des parallélisations quantique du temps courbe via la simple ligne de code :
pqkkmovtsqu qppm0, [qppm1+$2A];

(°.o)

hihihi

Commentaire de cirec le 29/01/2008 13:28:53 administrateur CS

@WhiteHippo :
je venais exactement pour le même type de remarque !

Sauf que chez moi ta procédure donne quasiment les mêmes résultats que le dernière de F0xi !!!

Et justement je voulais signaler que chez moi la toute première version
optimisée de F0xi reste la procédure la plus rapide (moins de cycles)
et que même GetIntDivider3 (de WhiteHippo) donne des résultats parfois en dessous de ceux de te dernière mouture ?

On en déduis donc que : arrivé à un certain niveau d'optimisation
c'est le processeur qui fera la différence entre des résultats plus performant sur les nouvelles machines (Normal) mais en revanche, sur des
machines plus anciennes ce même code peut donner des résultats moins bon qu'un code moins optimisé.

Sur AMD Athlon XP 1800+ 1.53 Ghz  512 Ram  (c'est pas un cheval de course ;) )

Belle démonstration d'optimisation que vous nous offrez ici
Bravo tous les deux

Commentaire de cirec le 30/01/2008 02:11:49 administrateur CS

@F0xi :
vu ton inquiétude je suppose que tu n'as pas lu mon message sur le forum ...
je te rassure je ne fais pas la gueule ... et c'est bizarre parce que je pensais la même chose de toi puisque tu n'avais pas répondu au message ... (du forum)

"Potes ?" bien sur que oui, le contraire ne m'a même pas effleuré ^^

Commentaire de Albedo039 le 31/01/2008 16:25:58

On peut opérer les tests de "haut en bas" (du plus grand au plus petit diviseur possible)
puisqu'on sait déjà que le plus grand diviseur possible est le nombre en entrée divisé par 2.

Si ce premier "diviseur à tester" est pair, alors après l'avoir tester, on peut le diviser par 2 de nouveau: c'est le prochain "diviseur possible".... et ainsi de suite.

Faire le test p.e. avec 2717908992: 81 x 2 x 2 x... (25 fois 'par2')
on pourrait alors optimiser cette partie du code:
- chercher les combinaisons possibles des 25 fois 'par2' (2, 4, 8, 16, 32... 33554432)
- le résultat de la dernière division par 2 est 81. calculer les combinaisons de ce nombre avec les combis précédentes.
- étudier "81" pour voir s'il est lui-même "divisible" : s'il est divisible, alors les diviseurs peuvent être "combinés" avec les nombres précédents...
Par exemple ici:
81 = 9x9
81 = 3x3x3x3
81 = 27x3
on sait donc que 3, 9 et 27 sont des diviseurs
mais donc aussi que
3x2
3x4
3x8
3x16
...
3x33554432
et ainsi de suite avec 9 et 27.

++++++++++++++++++++++++++++++++++
Je pense que l'on peut optimiser beaucoup plus encore :)

Par exemple en utilisant des embranchements de code:

if JeSuisPair then
TrouveDiviseursProc:= Ma_Proc_Speciale_Nombres_Pairs
else
TrouveDiviseursProc:= Ma_Proc_Speciale_Nombres_Impairs;
TrouveDiviseursProc(...);

et bien sûr qqc comme:

procedure Ma_Proc_Speciale_Nombres_Pairs(...);
Begin
...
End;

Commentaire de geulbuif le 18/09/2008 13:02:23

JACK169 :

Il faut que tu decompresse tout les fichiers
(surtout fmd.ex_)

Puis renommer fmd.ex_ en fmd.exe
Ensuite tu lance le prog a partir de fmd.exe ;)
en espérant avoir été clair et t'avoir aider .

PS : si tu compte pas étudier le logiciel / programme tout les autres fichiers tu peut les supprimer ;)
En remerciant f0xi sa m'a bien aider :D