TROUVER LES DIVISEURS D'UN NOMBRE ENTIER
f0xi
Messages postés
4205
Date d'inscription
samedi 16 octobre 2004
Statut
Modérateur
Dernière intervention
12 mars 2022
-
21 janv. 2008 à 04:08
amiga68 Messages postés 54 Date d'inscription dimanche 23 février 2003 Statut Membre Dernière intervention 21 décembre 2009 - 3 déc. 2008 à 19:13
amiga68 Messages postés 54 Date d'inscription dimanche 23 février 2003 Statut Membre Dernière intervention 21 décembre 2009 - 3 déc. 2008 à 19:13
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/45480-trouver-les-diviseurs-d-un-nombre-entier
https://codes-sources.commentcamarche.net/source/45480-trouver-les-diviseurs-d-un-nombre-entier
3 déc. 2008 à 19:13
si Delphi possedait l'operateur ++ et -- ce qui serait le minimum quand même! (>_<) *
}
DivisorsCount := DivisorsCount + 1;
Il existe inc(divisorsCount); mais je ne sais pas si c'est plus rapide...
3 déc. 2008 à 12:56
ton logiciel est super !!!!!!!!
est-il libre ?
je désirerais l'utiliser en classe pour vérifier facilement les calculs de simplification de fractions et de nombre en général.
adeline
18 sept. 2008 à 13:02
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
3 sept. 2008 à 23:33
Excusez-moi pour mon incompétence suprême en informatique, mais j'ai trouvé votre logiciel et il pourrait m'être bien utile. Malheureusement je n'ai aucune idée de comment l'ouvrir car le dossier est sous Win rar, mais une fois dedans je suis perdu.
Merci d'avance
31 janv. 2008 à 16:25
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;
31 janv. 2008 à 15:34
Si le nombre à étudier est impair, alors on peut optimiser encore.
En effet, on peut tester en "sautant" les diviseurs potentiels qui sont pairs, puisque les nombres pairs ne "génèrent" (à la multiplication) que des nombres pairs.
Dans ce cas
DivisorA := DivisorA + 2;
fait l'affaire.
Statistiquement parlant, c'est un gain de 25% (50% de tests en moins pour 50% des nombres à étudier possibles...)
30 janv. 2008 à 02:11
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é ^^
29 janv. 2008 à 20:52
Un chouilla, un chouilla, a peine 5 a 10 cycles en moins...
je pense que cela viens de la multiplication et peut etre du repeat until.
la faudrait voir ce que Delphi nous pond comme assembleur sur une while et sur un repeat.
y'aura même peut etre des differences avec des goto et des label ...
mais on est tout les deux dans des performances identiques, de 0 a 10 cycles prés a peine.
@Cirec :
Je suis content que tu te montre enfin, je croyais que tu me faisais la gueule suite a notre petit "malentendus", donc j'en profite pour m'excuser d'avoir pus etre blessant si ça été le cas :)
potes ?
pour ce qui est des performances, la il est certains qu'ils faut prendre 2 choses en comptes :
La frequences du processeur (plus elle est élévées plus on a de cycles/secondes)
Le cache processeur (plus ou moins veloce il ralentira ou non la fonction)
La ram (plus ou moins rapide pour le transfer des données)
L'utilisation d'un tableau fixe permet de ne pas faire de redim en cours de route (ce qui prend enormement de temps) comme me la signaler Brunews. c'est en partie ce qui nous fait gagner le plus de temps (quasiment le double avec un tableau dynamique).
Pour depasser la limite (4000) de diviseurs il faudrait taper dans le int64 afin d'avoir un nombre qui en possede autant.
La aussi Brunews m'a expliquer que Windows alloue les pages memoires par 4Ko (4096 octets) donc un tableau de 4000 longint nous donne 4 pages memoires soit 16Ko au total (4000*4, 1000 par pages).
Bon brunews l'expliquerais mieux que moi.
Ensuite viens finalement les diverses regles d'ecriture de l'algorithme, qui permettent de limiter le nombre de boucle (divmod) de sortir a temps (les deux condition while ou repeat et break).
Bref il est certains que nous sommes en presence d'un bel exercice d'optimisation permettant de constater comment une methode se comporte quand on l'ecrit de diverse maniere.
29 janv. 2008 à 13:28
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
29 janv. 2008 à 12:34
Pourrais tu faire des tests avec le code ci-dessous sur ta machine, car sur la mienne j'ai l'impression que cette méthode me donne des temps plus rapide par rapport à l'autre :
procedure GetDivisors(const Number: Longint; const pDivisors: pLongintArray;
out DivisorsCount: Longint; out AsPrime: boolean);
var
i,i2 : Integer;
Divisor, Modulo : Longint;
begin
DivisorsCount := 0 ;
i := 1;
repeat
i2 := i*i ;
if i2 > Number then break ;
IDivMod(Number, i, Divisor, Modulo);
if Modulo = 0 then
begin
pDivisors^[DivisorsCount] := i;
DivisorsCount := DivisorsCount + 1;
if Number<>i2 then
begin
pDivisors^[DivisorsCount] := Divisor;
DivisorsCount := DivisorsCount + 1;
end ;
end;
Inc(i);
until false ; AsPrime :(DivisorsCount 2) and ((pDivisors^[0] = 1) and (pDivisors^[1] = Number));
end;
Cordialement.
29 janv. 2008 à 06:26
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
29 janv. 2008 à 00:10
Voici une version modifiée, et comme tu n'aimes pas les divisions, basculement vers les multiplications :
function GetIntDivider3(const Number: integer): TIntArray;
var i,i2 : Integer;
begin
i := 1;
repeat
i2 := i*i ;
if i2 > Number then break ;
if (Number Mod i) = 0 then
begin
SetLength(Result, Length(Result)+1);
Result[High(Result)] := i ;
if Number<>i2 then
begin
SetLength(Result, Length(Result)+1);
Result[High(Result)] := Number div i ;
end ;
end;
Inc(i);
until false ;
end;
Cordialement.
28 janv. 2008 à 23:53
je vais mettre a jours la source avec une petite modif que je te doit :)
28 janv. 2008 à 23:42
P.S. pour une valeur comme 994917094, nombre non premier, j'obtiens à priori de meilleure résultats qu'avec la méthode optimized.
Cordialement.
28 janv. 2008 à 23:34
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 :)
28 janv. 2008 à 23:31
Essaye avec la version que j'ai fourni et la optimized sur un nombre comme 42949483 par exemple, histoire de voir ;P
Cordialement.
28 janv. 2008 à 23:22
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 :)
28 janv. 2008 à 23:15
Ok, mais regarde le nombre de cycles gagnés en contrepartie.
"et le control des doublons ?!"
Des doublons ??? ou ça ???
Cordialement.
28 janv. 2008 à 23:03
Result[High(Result)] := i ;
Result[High(Result)-1] := Number div i ; << et le control des doublons ?!
j'ai ajouter des commentaires detaillés ...
28 janv. 2008 à 22:16
De légères modifications peuvent grandement l'améliorer, même si cela ne la rend pas optimale :
function GetIntDivider2(const Number: integer): TIntArray;
var i : Integer;
begin
i := 1;
while i <= (Number div i) do
begin
if (Number Mod i) = 0 then
begin
SetLength(Result, Length(Result)+2);
Result[High(Result)] := i ;
Result[High(Result)-1] := Number div i ;
end;
Inc(i);
end;
end;
Cordialement.
28 janv. 2008 à 11:23
28 janv. 2008 à 11:16
26 janv. 2008 à 10:40
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.
21 janv. 2008 à 15:14
En tout cas ça fait logntemps que l' on a pas de tes nouvelles!
Alors oui, la 2eme fonction est légèrement plus rapide, mais léger ... lol
Je mets 10/10 pour t' encourager à améliorer encore cela :)
A+
21 janv. 2008 à 04:08