Factorisation et test de primalité 32 bits ultra optimisé
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é
- Test nom de domaine - Forum PHP
- Sockets de test ✓ - Forum C / C++ / C++.NET
- Test de non regression - Forum VB.NET
- Test technique java - Conseils pratiques -C# / .NET
- Test de connection - Forum Delphi / Pascal
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.