Voila j'avais un peu de temps à perdre alors je me suis lancé dans le codage d'un programme qui cherche tous les nombres parfaits, mais mon algo est un peu poussif je voudrait savoir si c'est possible de l'optimiser avec les instruction mmx ou sse par exemple
 
Je sais pas du tout me servir de tout ca mais je croi que ca doit etre possible de faire faire au proco plusieur calcul en même temps, je pensai notamment à faire cette comparaison "if (n%j==0)" pour +sieur valeurs de j à la fois ...
 
Si vous voyez comment optimiser cet algo vos remarques sont les bienvenues
 
 

le modulo est une opération gourmande il me semble...

éjection du sqrt() hors du for.

c'est une question d'algo. pre-calcul le maximum de choses, amis surtout, revois ton algo, par ce que si j est divisible par 2n il le sera pas n. cela dit, ç'est quand meme dejà assez rapide
 
'optimiser avec les instruction mmx ou sse par exemple'
 
masturbation de newbie détectée

 
http://msdn.microsoft.com/library/ [...] isualC.asp
 
attends tu peux gagner jusqu'a 3% c'est enorme !!!

n%j et n/j sont deux opérations redondantes
(de par la definition de la division euclidienne
a = q*d + r; d etant le diviseur, q le quotient soit a/d et r le reste soit a%d)
 
Ceci dit, si on applique l'algo "beta" de la division
alors on a le reste en bonus mais ce n'est pas dit
que le processeur ne soit pas plus rapide a faire
cette operation du fait d'optimisations qui ne donneront
pas le reste. (ou le modulo obtenu par une autre méthode)
 
Quelqu'un pour eclairer ma lanterne ?
 
Optimisation evidente de ce fait :
 
remplacer n%j par
modulo = n - q * j;
avec q = n/j;
 
[edit] en fait le gain n'est pas si enorme que ca puisque
tu ne fais pas l'operation de division a chaque iteration
 
LeGreg

ecoute, je vois pas pourqoi mosieur aurait besoin de vitesse à ce point... le "system("PAUSE" );" en dit long  

http://membres.lycos.fr/villeminge [...] tm#Parfait

tiens, c'est marrant, c'est là-dessus que mon cousin a fait sa thèse il me semble.

Ca a dû être vite torché, en 10 lignes de C.

http://www.math.jussieu.fr/~rouqui [...] rints.html
Ça doit être là-dedans, je trouve pas (et je comprends rien aux titres).

mouarf le dossier de dingue... en fait c'est trop cho à trouver un nombre parfait c decourageant
le system("pause" ) c'est juste pour eviter que la fenetre dos se referme toute seule quand je test le prog (j'utilise devc++), pkoi tu me fait une remarque la dessus  
 
A part ca je pensait pas que les instructions type mmx ou sse apportait si peu de gain , tant de tapage pour si peu ...

vraiment, tu ferais mieux de te documneter un peu avant de nous répéter les solgans de la pub intel

Ca dépend comment elles sont utilisées... Ce sont des unités SIMD, qui peuvent exécuter un nombre d'opérations simultanées assez conséquent (8 multiplications d'octets en une passe pour le MMX par exemple).
Faut voir le taux de dépendance entre les instructions, etc... Le SSE peut faire très fort (x4 ou plus).

RISC powa    

 
Bien utilise ca apporte beaucoup (tout comme 3Dnow/SSE)
mais bon comme on te l'a dit il y a sans doute
plus de gain a attendre du cote de l'algorithmique.
 
++Taz, il y a une grosse incohérence dans le lien que tu as passé
en gros il dit: tous les nombres parfaits sont de la forme 2^(n-1)(2^n - 1)
Et au dessus il dit qu'on ne sait toujours pas s'il y a des nombres parfaits impairs..  
C'est un peu enorme non??
 
LeGreg
 
 

> legreg : je sais, mais d'un autre coté, si personne n'en a encore trouvé, je doute que meme si notre ami faisait tourner son pentieum toute sa vie il arrive à découvrir un nombre qui n'est déjà été calculé. mais il y a peut etre moyen d'exploiter la dite formule pour calculer plus rapidement

 
Ben il n'a pas besoin de faire tourner son PC toute sa vie pour detecter qu'il y a une contradiction logique.
 
Ou alors il se contente de dire "tous les nombres parfaits que l'on a DEJA trouve sont de la forme [..] et l'on ne sait pas s'il y en a qui ne respectent pas cette forme"..
Bref ca me donne vraiment pas envie de lire ce qu'il a ecrit d'autre sur son site.
 
LeGreg
 

ecoute, ce n'est pas parce que ça à l'air contradictoire, que c'est completement faux. la science avance comme ça. on a pas trouvé de nombre parfait pair, tous les nombres trouvés répondent à cette formule, jusqu'à preuve du contraire, elle fonctionne. le jour ou on la met en déroute, on sera oobliger de la revoir.
 
il s'est passer la meme chose il y a quelques mois avec la célèbre E=mc²

 
pentium pro pawa  

 
je crois que tu n'as pas compris
effectivement en science on emet des theories qui restent
valides un certain temps etc..
 
Sauf que la je ne remets pas en cause une theorie mais l'expression de celle-ci dans un domaine que je connais bien (les mathematiques) et qui sous cette forme n'est pas valide.
 
Quand je mets  
"propriete: tous les nombres parfaits sont sous cette forme"
 
je n'emets pas une theorie mais une propriete que je suis sense pouvoir demontrer, sinon j'appelle ca une conjecture.
 
Bref pour un site qui parle de math ce n'est pas du tout rigoureux.
 
Je suis d'accord que selon les disciples d'Euclide tous les nombres parfaits sont de cette forme (affirmant donc implicitement qu'il n'y avait pas de nombre parfait impair)
mais on ne peut pas mettre les deux affirmations au meme niveau.
 
C'est soit:
- il n'y a pas de nombre parfaits impairs et tous les nombres parfaits sont sous cette forme (forme d'Euclide non démontrée)
- il existe peut-etre des nombres parfaits impairs et tous les nombres parfaits PAIRS sont sous cette forme (forme démontrée).
 
Ceci dit comme on a deja explore pas mal (je dirais pas une grosse partie parce que c'est infini) de l'ensemble des entiers et qu'on n'a pas trouve de nombre parfait impair, il peut raisonnablement se restreindre aux nombres pairs (et a la formule d'Euclide) pour une recherche cantonnee a l'intervalle de validite d'un int.
 
En fait c'est meme plus fort: comme dans cet intervalle de validite il y a un tout petit nombre de nombres parfaits
il sera plus rapide algorithmiquement parlant de tester l'egalite avec ces nombres plutot que de tester la formule avec la somme des diviseurs qui risque d'etre tres longue .
Enfin je parle d'efficacité algorithmique qui est tres eloignee des besoins des mathematiciens.
 
LeGreg

Faut aller sur le lien spécifique: http://membres.lycos.fr/villeminge [...] ixNbPf.htm
 
Euler a montré que tous les nombres parfaits pairs étaient de la forme énoncée plus haut.
 
Le fait qu'il n'y a pas de nombre parfait impair est une conjecture.

Jusqu'à maintenant, on en a découvert que 39 ou 40 je sais plus, nombres premiers, avec beaucoup de chiffres (environ 10000 je crois), je pense donc que l'utilisation d'une bibliotheque de manipulation des grands nombres serait une bonne chose =)
 
[incrust inside] J'ai fait ca en OcamL, j'ai d'ailleurs plus galéré sur des problèmes de syntaxe de BASE ( raynaud à l'aide > http://forum.hardware.fr/forum2.ph [...] h=&subcat= ! )
[/incrust inside]

http://www.pps.jussieu.fr/Livres/o [...] tml#toc108
Kado (désolé pour le lien mais j'ai pas accès à caml.inria.fr)

question en passant: t'aurais un bon algo de division pour une arithmetique exacte sur des grands entiers représenter par  un tableau de caractères?

Non, mais c'est un domaine _vraiment_ merdique, j'ai eu un prof qui a fait sa thèse là dessus (3ans pour une divison ...).

par ce que c'est chouette d'avoir un bon algo pour la multiplication (genre mult indienne) mais si on travaile en base décimal et qu'on à pas un bon truc pour diviser par 2, spa gagner

pour diviser par 2 il suffit de faire un deplacement de bit vers la droite, ca doit pas pomper gros de ressources..
apres si tu veux diviser par un autre chiffre qu'un multiple de 2 c'est une autre histoire..

ben il te suffit de décaler d'autant de bits vers la droite :
diviser par 2 => shr ax,1
diviser par 4 => shr ax,2
diviser par 8 => shr ax,3
etc..
 
même topo pour multiplier, sauf qu'on décale vers la gauche :
multiplier par 2 => shl ax,1
multiplier par 4 => shl ax,2
multiplier par 8 => shl ax,3
etc...
 
c'est diablement efficace !

z'en avez d'autres des comme ça? en base 10 avec représentation en string, spa gagner
 

vi mais le monsieur il était resté bloqué en entier-entier  

rappel: l'instruction div (asm) calcule la division (entiere) et le modulo en même temps.

sans allez jusque là
 
voir div et ldiv de <stdlib.h> qui font également le boulot d'un seul coup

 
LeGreg

et encore, si tres int sont sur 16bits, le 33........ ne passe pas.
 
mais c'est vrai que c'est pas con.

 
c'est comme ca que je ferais si je devais l'utiliser
dans un programme qui sert a quelque chose.
 
Evidemment si l'interet est purement theorique..
 
LeGreg

 
   
 
           
 
Mais le pire c'est que je serais prof, j'y mets 20/20. Parce qu'un bon programmeur c'est celui qui a un minimum de pragmatisme pour résoudre un porblème au plus simple au lieu de pondre des truc alambiqués et inéficaces.

Et surtout ça veut dire que le gars s'est documenté et a trouvé la meilleure solution possible.