Deux bibliothèques pour calculer avec des entiers très grands
Soyez le premier à donner votre avis sur cette source.
Vue 9 641 fois - Téléchargée 1 117 fois
Description
NewGInt et NewGCent sont deux unités .pas pour effectuer des calculs divers sur des entiers très grands (en principe "illimités"). Toutes deux, elles offrent de nombreuses fonctions et procédures utilisables facilement dans des applications Delphi. Citons pour mémoire les calculs arithmétiques élémentaires : addition, soustraction, multiplication, division, puissance, factorielle... mais aussi les opérations d'arithmétique modulaire et les opérations de logique... et autres bien intéressantes.
Ces bibliothèques sont le fruit de mes recherches depuis plusieurs années et tous les essais et améliorations ont été portés à systémisation par la grande participation active de Pseudo3. Il s'agit donc déjà d'un ensemble très élaboré et en principe bien abouti qui ne demande qu'à être utilisé par tout un chacun.
Source / Exemple :
NewGInt s'applique à des nombres codés en base 256 alors que NewGCent manipule des entiers codés en base 100 avec tous les avantages d'une approche décimale. L'une et l'autre peuvent s'utiliser séparément ou conjointement grâce à des passerelles. Elles forment un ensemble assez complexe nécessitant des précautions d'utilisation en raison des énormes volumes d'octets manipulés dans les calculs. Malgré cela elles sont relativement rapides car les noyaux calculatoires de base ont été optimisés en ASM 32bits. Pour faciliter leur utilisation, un fascicule explicatif d'accompagnement est fourni dans le zip de téléchargement.
Conclusion :
Ces bibliothèques sont le fruit de mes recherches depuis plusieurs années et tous les essais et améliorations ont été portés à systémisation par la grande participation active de Pseudo3. Il s'agit donc déjà d'un ensemble très élaboré et en principe bien abouti qui ne demande qu'à être utilisé par tout un chacun.
Codes Sources
A voir également
- Deux bibliothèques pour calculer avec des entiers très grands
- Ephéméride calcul entre deux dates - Forum Delphi / Pascal
- Calculer age avec date de naissance ✓ - Forum Visual Basic 6
- Calculer un azimut entre deux points - Forum PHP
- Calcul d azimut entre deux points geodesiques - Forum Visual Basic
- Différence entre deux heures ✓ - Forum VB.NET
12 déc. 2011 à 06:45
Je pensais depuis longtemps à faire ce genre de boulot... j'y connais rien en asm... c'est fait ?
Une suggestion : serait-il difficile d'implémenter un FGIntToStrF (formaté en paquets de trois chiffres) ? Cela irait plus vite en asm qu'à partir du programme appelant...
12 déc. 2011 à 11:05
A Caribensila le : "Bon ! Certains vont te reprocher d'avoir négligé les Réels. Ou plutôt, de laisser le boulot à l'utilisateur."
... Eh bin non : Les Réels n'ont pas été négligés, ni même les nombres complexes, car j'ai utilisé les GCent (version n-1 des NewGCent ci-dessus) dans une appli incluant d'une part la résolution des équations polynomiales de degré N, et d'autre part une calculette pour grands ou petits nombres réels ou complexes.
Voici par exemple l'en-tête de l'unit pour les Grands ou petits Réels :
unit UnitGR;
interface //*********************************************************
// Pour calculs avec Grands Réels à nombre de chiffres *
// significatifs supérieur à 20 *
// Code : EXPERIMENTAL *
//*********************************************************
uses Windows, Dialogs, Controls, SysUtils, math, Forms, Graphics,
clipbrd, UnitIntGCent, uFun2, uConstPrecalculees, uFlotte2, buttons;
type tGR = record
Signe : ShortString;
Sv : GCent; // chaîne numérique représentée en base 100 expurgée des puissances de 10
Expo : Int64; // Expo correspond aux puissances de 10 mais renseigne aussi sur la position du DecimalSeparator
// dans la représentation décimale après conversion du nombre :
// - si Expo < 0 alors Expo = Décalage du Séparateur Décimal par rapport à la fin de la chaîne Sv // - si Expo 0 alors Sv valeur entière
// - si Expo > 0 alors Sv = valeur entière et Expo équivaut au nombre de '0' à ajouter en fin de Sv
// dans une représentation intégrale du nombre (représentation au format non scientifique)
end;
Et voici celle de l'unit pour les nombres complexes :
unit UnitGC;
interface //*********************************************************
// Pour calculs avec Grands nombres Complexes *
// avec part réelle et imaginaire du type tGR *
// Code : EXPERIMENTAL *
//*********************************************************
uses Windows, UnitGR, classes, Math, Dialogs, Sysutils, uFun2, clipbrd;
type tGC = record
a : tGR; // part réelle
b : tGR; // part imaginaire
end;
Le seul inconvénient est que j'ai eu la flemme de refaire tout ce boulot pour l'adapter à la version actuelle des NewGCent mais il donne des idées sur les possibilités offertes par l'utilisation des bibliothèques publiées ici par Rekin85.
Donc si ça intéresse quelqu'un :
- soit il me passe son adresse e-mail et je lui envoie le zip contenant le code qui utilise l'ancienne version des GCent,
- soit je peux placer ici dans un commentaire les codes de l'unit UnitGR et de l'unit UnitGC dans leur état actuel,
- soit je peux publier carrément l'appli de résolution des équations associée à la calculette dans son état actuel et dans une discussion distincte de la présente.
... Mais ma principale gêne est que mon appli utilise la version n-1 des NewGCent et que l'on reproche que cela fait un peu désordre sur ce site.
Par contre vu que Caribensila a dit "Négligé ... Ou plutôt, de laisser le boulot à l'utilisateur" j'ajouterais que la publication présenterait l'avantage de réduire l'importance du boulot laissé à l'utilisateur puisqu'il ne lui reste plus qu'à adapter l'unit UnitGR et la UnitGC à la version actuelle des NewGCent OU des NewGint.
Qu'en pensez vous ?
A+.
12 déc. 2011 à 12:18
Alors pour tous, je voudrais apporter quelques précisions de génèse et de destination de ce boulot de quelques années.
Je suis tout nouveau membre ici et je ne connais pas trop bien les usages, mais je vais m'adapter vite. Si ces unités ont été placées là c'est à la demande de mon ami Pseudo3 qui en est le co-auteur, mais elles sont aussi sur un autre site dédié à Delphi où elles ont été téléchargées maintenant presque 2000 fois sans aucune remontée négative depuis plus d'un an.
A l'origine, la destination était la cryptologie... donc domaine des entiers naturels (et moi je cherche toujours à fabriquer des nombres premiers géants rapidement... en vain). Le but étant d'avoir des routines arithmétiques de base pour des nombres plus grands que 32 bits. L'ASM a donné des possibilités énormes pour les vitesses. Et un jour Pseudo3 (Gilbert) qui cherchait des routines rapides pour un de ses programmes (calculette scientifique) m'a contacté et proposé ses services pour les tests et applications. Son aide m'a été très précieuse et a fait faire un énorme bond en avant pour les optimisations. Surtout, il est à l'origine de la création des GCents. Alors voilà c'est un travail collectif à deux extrêmement abouti (nous sommes champions de la racine carrée goutte à goutte et de la multiplication Karatsubée...).
Ces deux unités sont ouvertes : elles sont là pour servir de base à tous besoins numératoires; ainsi pour les réels, Gilbert l'a déjà fait grâce à une unité de son cru et moi j'ai déjà proposé par ailleurs des aménagements dans le domaine des entiers relatifs. Donc ouvertes et libres d'utilisation...
@Caribensila : je comprends ton souci d'inachevé, mais le but n'était pas de refaire une librairie complète comme celles qui sont utlisables en C. L'usage de l'ASM pour les implémentations n'est pas du travail relax et je ne pense pas étendre mon travail personnels au-delà (sauf dans le domaine de la primalité).
@AMIGA68 : Oui, par paquets de trois, c'est humainement plus lisible, mais tu sais quand on dépasse plusieurs milliers de digits... Mais je vais tartiner une petite routine ASM comme tu le souhaites et quand je serai prêt je la placerai ici. Alors patience, il faut être très prudent en ASM car il faut gérer la RAM et surtout ne pas se faire piéger par le gestionnaire de variables de Delphi (une poisse !). Alors à bientôt.
13 déc. 2011 à 19:24
« soit je peux publier carrément l'appli de résolution des équations associée à la calculette dans son état actuel et dans une discussion distincte de la présente »
Ben, je n'ai pas autorité pour donner mon avis. Mais je le donne quand même :)
- ce serait une bonne idée, je pense... Avec un lien vers ce topic.
@Rekin85
« A l'origine, la destination était la cryptologie... »
Ok, je comprends mieux l'absence de la virgule ou du point.
J'ai jeté un oeil sur le code. QUE DE L'ASM ! lol Mais, heureusement c'est commenté.
Deux petites remarques :
1) En général, on choisit les tableaux plutôt que le type string pour manipuler ces nombres.
Mais j'avais aussi fait ce choix à l'époque. Je pensais comme toi que ce serait plus facile, mais à tort, m'a-t'on dit...
Enfin, peut-être qu'en assembleur, String ou Array ne font pas grandes différences ?
2) ATTENTION : Randomize est une commande pour le programmeur !
Ce n'est pas bien de l'utiliser dans son dos car il peut vouloir obtenir toujours la même séquence de nombres pseudo-aléatoires. Ne serait-ce que pour tester une routine.
D'autre part, Randomize est appelé dans les deux unités, sans compter que le programmeur peut lui-même l'appeler dans son propre programme s'il utilise ces unités à l'aveuglette. Ces appels répétés peuvent perturber le générateur de Delphi qui est déjà de bien piètre qualité. D'ailleurs l'Aide Delphi le précise bien :
« pour initialiser le générateur de nombre aléatoire, ajoutez un seul appel Randomize ».
Il faut donc supprimer Randomize dans les procédures PRndGIntMize de l'unité NewGint et PRndGCentMize de l'unité NewGCent. Ce sera au programmeur de l'utiliser, ou pas, selon ses besoins.
Du coup, j'ai testé (avec D7) le générateur de nombres pseudo-aléatoires. Hélas, il semble souffrir des mêmes faiblesses que ceux de Delphi. Sur des unités de cette qualité, destinées quand même à faire des calculs scientifiques, on pourrait s'attendre à mieux, je pense.
VOIR: http://www.alrj.org/docs/algo/random.php
Sinon, c'est assez facile à utiliser.
Allez ! 10/10 !
PS:
Au sujet des générateurs de nombres premiers, JP DELAHAYE a écrit un article très intéressant sur l'état actuel de cette science dans le numéro d'octobre 2011 de "Pour la Science".
Cet article est téléchargeable ci-dessous (2€, mais ça vaut le coup pour un passionné) :
http://www.pourlascience.fr/ewb_pages/f/fiche-article-la-maitrise-des-nombres-premiers-27975.php
19 déc. 2011 à 16:37
Un bug cependant dans le calcul de la racine carrée par FRacineGint:
racine carrée de 2^(2*n) et 2^(2*n+1) donne le même résultat 2^n
il me semble que l'erreur vient de:
" i:=IsDiv2GInt(Nb,P);
if P then begin Result:=FDeuxPowerN(i shr 1); Exit; end;"
à modifier ainsi:
i:=IsDiv2GInt(Nb,P);
if P and (i mod 2=0) then begin Result:=FDeuxPowerN(i shr 1); Exit; end;
//valable seulement pour les puissances paires de 2
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.