Factorisation et test de primalité 32 bits ultra optimisé

Soyez le premier à donner votre avis sur cette source.

Vue 5 756 fois - Téléchargée 930 fois

Description

Bonjour,
voici une source qui permet de factoriser un nombre entier sur 32 bits (non signé, donc de 0 à 4294967295), ou de vérifier sa primalité. Retour aux sources : ici, l'on ne trouvera pas d'algorithme mathématique très compliqué. Pour de si petits nombres, il est plus rapide d'utiliser l'algorithme naïf le plus simple, je me suis donc tourné vers un défi d'optimisation davantage que vers un défi mathématique. Ainsi, les mathématiques derrière ce code sont extrêmement simples que même un collégien pourra probablement les comprendre, en revanche le code n'est pas si clair que ça si vous n'êtes pas initiés au Delphi (c'est pourquoi j'ai bourré le code de commentaires !).

Donc dans cette source, vous trouvez l'unité Factorization.pas, qui contient deux fonctions : Factorize, qui factorise un nombre sur 32 bits quelconque et renvoie les résultats dans un tableau d'entiers, et Primality, qui teste la primalité d'un nombre. J'inclus dans la source une application exemple qui montrera le code en action, en même temps que ses performances (le temps mis pour effectuer les opérations).

Même si ça n'en a pas forcément l'air, les fonctions suivantes sont ultra optimisées :
- SmallestFactor
- Factorize
- Primality

Quand je dis ultra optimisé, je ne rigole pas : le temps d'exécution de ces fonctions se joue à la microseconde. Chez moi, le temps n'excède jamais 50 µs quelque soit le nombre testé. Factorize me renvoie des temps plus ou moins cohérents (de façon générale, le temps augmente lorsque le nombre augmente), mais Primality fluctue grandement, et n'aura un temps d'exécution maximal que lorsque le nombre est effectivement premier, car dans ce cas le test s'effectue jusqu'au bout sans s'arrêter avant en déclarant le nombre composé.

Le reste est moyennement optimisé car il ne sert que pour le précalcul des nombres premiers (j'aurai pu inclure une mégaliste de plus de six mille nombres premiers dans un tableau const, mais ça aurait été horrible et franchement pas élégant).

Voilà, donc je pense que cette source peut être intéressante pour ceux qui cherchent des astuces d'optimisation, etc ... si vous avez des idées d'optimisation n'hésitez pas à me les communiquer ! J'ai déjà pensé à charger la table des nombres premiers dans le cache primaire (L1) du processeur pour un accès instantané mais je cherche encore comment faire ...

PS : pour ceux qui cherchent une comparaison concrète, j'ai repris le snippet de f0xi (IsPrimeNumber avec une UDivMod en assembleur). Lors de plusieurs tests sur des nombres vraiment premiers, IsPrimeNumber me renvoyait dans les 150 µs, tandis que Primality me renvoyait 35 µs environ.

Source / Exemple :


// In the zip

Conclusion :


Voilà, tous commentaires, critiques, remarques, conseils, optimisations, n'hésitez pas.

Codé sous Delphi 6 Personal Edition, Windows Vista SP2.

Cordialement, Bacterius !

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
3793
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
3 juin 2016
8
J'ai pris cette source de Barbichette, et il avait dit qu'il était inutile d'essayer d'optimiser le Result * 2 + 1 car le compilateur le faisait automatiquement ^^
Mais merci quand même. Remarque que cette fonction n'est pas cruciale, elle sert juste à précalculer les nombres premiers jusqu'à 65521.

Cordialement, Bacterius !
Messages postés
1154
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
5 avril 2012

Bonsoir

J'ai pas testé ton application, juste regardé brievement le code, mais vu que l'on parle d'optimisation, ne serait-il pas plus rapide de changer la fonction root comme suit :

function Root(N: Longword): Longword;
var
Temp : LongWord ;
begin
Result := 1;
Temp := 3;
while ( N > Temp ) do
begin
Dec(N, Temp);
Inc(Result);
Inc(Temp,2);
end;
Inc(Result);
end;

Ceci afin d'éviter la répétition du calcul Result*2 + 1.

N.B. La fonction proposée, si ça se trouve, est elle aussi améliorable ;)

Cordialement.
Messages postés
3793
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
3 juin 2016
8
Dans un fichier ressource ? Si, ça serait possible, mais je pense que la vitesse resterait la même, car on serait obligé de copier la liste depuis le fichier ressource dans un tableau d'entiers, donc on gagnerait probablement un peu de performance au niveau des précalculs mais ça serait kif-kif au niveau des fonctions intéressantes elles-mêmes.

Mais je vais essayer pour voir ...

Cordialement, Bacterius !
Messages postés
384
Date d'inscription
vendredi 18 juin 2004
Statut
Membre
Dernière intervention
7 mai 2009

J'aime bien ce genre d'optimisations ^^

Au niveau rapidité, c'est pas mieux d'inclure la megaliste de premier dans un fichier ressource ?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.