Factorisation et test de primalité 32 bits ultra optimisé
0/5 (4 avis)
Vue 6 659 fois - Téléchargée 1 070 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.
Voilà, tous commentaires, critiques, remarques, conseils, optimisations, n'hésitez pas.
Codé sous Delphi 6 Personal Edition, Windows Vista SP2.
Cordialement, Bacterius !
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
- Factorisation et test de primalité 32 bits ultra optimisé
- 32 bits en décimal ✓ - Forum VB.NET
- Test de non regression - Forum VB.NET
- Test nom de domaine - Forum PHP
- Sockets de test ✓ - Forum C / C++ / C++.NET
- Chr(32) ✓ - Forum IRC
17 juil. 2010 à 01:33
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 !
16 juil. 2010 à 21:04
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.
14 juil. 2010 à 01:56
Mais je vais essayer pour voir ...
Cordialement, Bacterius !
13 juil. 2010 à 18:17
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.