PREMIER OU PAS?
Bacterius
Messages postés
3792
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
3 juin 2016
-
30 déc. 2009 à 23:53
blueperfect Messages postés 234 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 21 novembre 2013 - 5 janv. 2010 à 01:56
blueperfect Messages postés 234 Date d'inscription mardi 13 novembre 2007 Statut Membre Dernière intervention 21 novembre 2013 - 5 janv. 2010 à 01:56
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/51038-premier-ou-pas
https://codes-sources.commentcamarche.net/source/51038-premier-ou-pas
5 janv. 2010 à 01:56
4 janv. 2010 à 23:41
Moi j'aime particulièrement les optimisations mathématiques, par exemple un modulo couteux qui se résume à deux opérations logiques et une addition ... quand le modulo est un nombre de Mersenne.
Si tu veux vraiment voir de l'assembleur en pleine action, cherche l'UnitGInt sur internet : c'est une très bonne librairie de grands nombres entièrement codée en assembleur, et je m'en sers quotidiennement ;)
Cordialement, Bacterius !
4 janv. 2010 à 22:51
Maintenant je trouve assez fun de voir des gens qui se consacre à des écritures de code Assembleur et personnellement ce que je trouve extraordinaire avec ce type de code c'est de voir la rapidité des machines à notre disposition
Recherche de 0 à 10 millions sur un quart de processeur ( soit 4 secondes pour un code optimisé sur les 4 corps et 664579 nombres trouvés)
Heure début :
22:40:29
664579
Heure fin :
22:40:45
J'avais essayé à l'époque en basic puis en turbo pascal ( 100 fois plus rapide ) ce genre de programme de division (non assemblé) , je ne vous dis pas les nuits blanches de l'ordinateur de l'époque pour arriver à 1 million !
En ce qui concerne le "sérieur" c'est clair qu'un bon algorithme c'est d'abord la meilleure méthode mathématique et hardware et ensuite le bon code sur un bon compilateur. Mais je suis persuadé que dans certains programmes notamment graphique le code assembleur est utilisé, même indirectement, pour améliorer les performances. je ne sais pas, par contre, si il y en a beaucoup dans Windows.... au vu des performances ...
A+
4 janv. 2010 à 13:12
De toute façon, ne nous leurrons pas. Aujourd'hui, ce code "rapide" ne tient pas la route pour une quelconque utilisation sérieuse. C'est pourquoi je proposais à Ludokk de se concocter ses implémentations de Miller-Rabin, Fermat, ou encore AKS (ou c'est plus dur, et alors ?), afin de toujours les avoir sous la main en cas de besoin :p
Cordialement, Bacterius !
4 janv. 2010 à 13:02
Merci aux auteurs
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Edit1: TEdit;
Button1: TButton;
Memo1: TMemo;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Déclarations privées }
public
{ Déclarations publiques }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure UDivMod(const Dividend, Divisor: LongWord; var Result, Remainder: LongWord); register;
asm
push ebx;
mov ebx,edx;
xor edx,edx;
div ebx;
mov ebx,Remainder;
mov [ecx],eax;
mov [ebx],edx;
pop ebx;
end;
function IsPrimeNumber(const Number: LongWord): boolean;
var DivisorA,
DivisorB,
Modulo,
DivisorsCount : LongWord;
begin
Result := false;
if Number < 2 then
exit;
DivisorA := 1;
DivisorB := Number;
Modulo := 0;
DivisorsCount := 0;
if DivisorA < DivisorB then
repeat
UDivMod(Number, DivisorA, DivisorB, Modulo);
if Modulo = 0 then
DivisorsCount := DivisorsCount + 2;
DivisorA := DivisorA + 1;
until (DivisorA >= DivisorB) or (DivisorsCount >= 3); Result :DivisorsCount 2;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i,nb,max,min : integer;
begin
nb:=0;
form1.Memo1.Clear;
min := strtoint(form1.Edit2.Text);
max := strtoint(form1.Edit1.Text);
form1.Memo1.Lines.Add('Heure début :' ) ;
form1.Memo1.Lines.Add(timetostr(now)) ;
for i := min to max do
begin
//form1.Memo1.Lines.Add(inttostr(i)) ;
if IsPrimeNumber(i) then
begin
inc(nb);
// form1.Memo1.Lines.Add(inttostr(i))
end;
end;
form1.Memo1.Lines.Add(inttostr(nb)) ;
form1.Memo1.Lines.Add('Heure fin : ') ;
form1.Memo1.Lines.Add(timetostr(now)) ;
end;
end.
4 janv. 2010 à 04:30
31 déc. 2009 à 00:10
30 déc. 2009 à 23:53
bienvenue sur CodeS-SourceS.
C'est un bon début, pense à toujours renommer les composants, ça fait plus propre et tu t'y retrouves plus vite quand tu veux replonger dans ton code deux mois plus tard.
Travailler sur des nombres réels est pénible pour l'ordinateur, alors je te propose une petite optimisation :
- tu stockes tout en Integer (ou Int64), et quand tu veux avoir la racine, tu en prends la valeur approchée avec Round(Sqrt(nombre)).
- travailler sur des entiers te donne un autre avantage : tu peux utiliser un opérateur rapide, qui est "mod", qui te permet entre autres de tester si a divise b : si a mod b = 0, alors a divise b, sinon il ne le divise pas.
- tu as deux fois le même code dans deux événements différents, c'est redondant et ça augmente le code. Pourquoi ne pas faire une fonction EstPremier, qui prend en paramètre un nombre entier, et retourne un Boolean (vrai/faux), qui contient le code de recherche, ainsi tu n'as plus qu'à appeller cette fonction, et à traiter la couleur des TEdits et l'affichage du résultat selon le résultat de la fonction :)
Pour tes prochains programmes, je te propose d'implémenter le test de primalité de Fermat, puis celui de Miller-Rabin. :)
Cordialement, Bacterius !