Bonjour à tous,
Ça fait maintenant un moment que je cherche la solution à ce problème, mais rien n'y fait (pas même google et wikipedia , c'est dire !)
Enfin voilà, je travaille sur une classe pour faire des calculs sur de très grands nombres (le premier qui me parle de Myracl ou GMP... ) et j'ai toujours le même problème après 2 sujets sur la question: le stockage du nombre (et donc l'écriture et la lecture de ce nombre).
Le nombre sera stocké en base 65536 (2^16) dans un vector <uint16_t> (et chaque case du vector contient donc un chiffre du nombre).
Donc, l'utilisateur de la classe entre par exemple:
Soit le nombre (de type string) et la base dans laquelle il est écrit. Puis il faut convertir ce nombre en base 65536... sans faire de calculs sur le nombre entier ! (bah oui, l'ordinateur en est incapable ) Sinon c'est trop facile, 2-3 petits modulos et le tour est joué
Ou il y a moyens en faisant tous les calculs dans le style "à la main" peut-être...
Et après c'est l'inverse ! transformer ce nombre astronomique de la base 65532 à la base 10 (ou autre...) pour l'afficher.
Bref, je suis perdu, merci de votre aide
C'est exactement pareil que n'importe quelle convertion chaine -> nombre.
1- Avoir un type nombre qui supporte les opérations de base : +=, *= et autres dérivés;
C'est uniquement là que l'utilisation des uint_16 intervient ; c'est un détail d'implémentation de ta classe.
2- parcourrir à l'envers chacun des caractères de ta représentation textuelle et l'accumuler à ton nombre : nb *= base_input (10 ici); nb += caractère-'0';
Oui, mais dans son cas le nombre est trop grand pour cela.
Une solution possible c'est:(jamais testé mais je propose)
constchar *number;
size_t number_len;
while(...condition_pour_que_number!=0...)
{
uint16_t rem=0;
for(int i=number_len-1;i>+0;i--)
rem=((uint32_t)rem*10+number[i]-'0')%BASE;
// !!! rem est le dernier chiffre de la représentation en base BASE de ton nombre, donc tu l'ajoute
list_nombre.push_back(rem);
// là il te faut un algo de division euclidienne qui travaille sur les char *
divide(number,BASE);
}
En fait l'idée c'est que tu peux facilement connaître le dernier *chiffre* en n'importe qu'elle base du nombre, donc tu le calcules puis ensuite tu fais la division euclidienne.
Bien sûr reste à coder cette fameuse division...
Diviser pour mieux régner est une des première leçons à apprendre dans le développement.
Dans la partie 1-, "avoir un type nombre qui ..." signifie "se débrouiller pour l'avoir, l'écrire si on ne l'a pas".
Et une fois qu'on là, la convertion chaine -> nombre, c'est comme d'hab'.
La question à se poser ici, est:
Comment est-ce que je le ferais à la main ?
Une fois que tu y as répondu, il ne te reste plus qu'à coder chaque une des étapes en pensant bien que ton nombre est trop long pour tous les types et que tu devras recoder tous les opérateurs que tu utilises.
Si tu ne sais pas comment le faire à l main, regarde sur le net, ou repasse par ici, je te donnerai la solution.
On peut faire plus rapidement en utilisant diviser pour régner.
Tu divises ton nombre en 2 nombres de taille proche, puis tu convertis les 2 et tu accoles les 2 résultats.
Le problème est dans la division : si tu le fait bien O(N*log N) tu auras une bonne complexité O(N*(log N)^2) je crois.
Il n'y a pas d'algorithme vraiment rapide de division. La méthode qu'on apprend petit à l'école fonctionne très bien.
Tu peux aussi utiliser une approche divide-and-conquer (diviser pour mieux régner) en découpant ton nombre au départ et en effectuant les divisions sur des petits blocs. Mais c'est beaucoup plus compliqué comme algorithme et pas forcément plus rapide surtout à ce niveau là.
Ouaip, en fait la solution de pamaury ne sert plus à rien puisqu'il faut un algo de division euclidienne, et qu'avec l'algo de division euclidienne, j'ai le reste (qu'il s'efforce de calculer avec la division...)
J'ai essayé d'implémenter la division euclidienne, mais c'est pas si simple :/
Il faut donc entrer le dividende (string) et le diviseur (int) (qui est en fait toujours égal à 65536), et la fonction calcule le quotient (string) et le reste (uint16_t).
Le prototype serait:
¬¬
Déjà, j'avoue que ça fais un moment que je n'ai pas posé une division (bah on en a plus besoin, les prof ne jurent plus que par les fractions )
Mais là n'est pas la question: j'ai vite retrouvé, mais ça ne résout pas le problème: on ne peut rien faire sur le dividende dans son intégralité, donc comment vérifier par exemple si le reste est inférieur au diviseur ? (le reste intermédiaire, qui est stocké dans une variable string puisqu'il peut être très grand)
Je crois que ces opérateurs sont implémenté pour comparer suivant l'ordre lexicographique mais si cela suis la logique on devrait avoir "567" < "689" par exemple.
A vérifier, je n'ai pas fait de test, mais je pense qu'il y a d'autres moyens de faire.
Je crois que ces opérateurs sont implémenté pour comparer suivant l'ordre lexicographique mais si cela suis la logique on devrait avoir "567" < "689" par exemple.
A vérifier, je n'ai pas fait de test, mais je pense qu'il y a d'autres moyens de faire.
Il n'y a pas d'algorithme vraiment rapide de division. La méthode qu'on apprend petit à l'école fonctionne très bien.
Tu peux aussi utiliser une approche divide-and-conquer (diviser pour mieux régner) en découpant ton nombre au départ et en effectuant les divisions sur des petits blocs. Mais c'est beaucoup plus compliqué comme algorithme et pas forcément plus rapide surtout à ce niveau là.
Non, non il y a des moyens plus rapides de faire des divisions (grands nombres/grand nombres). O(N*log N)
Avec les chaînes, il suffit de réfléchir comme tu le fais toi, puis tu codes.
Donne le pseudo-code ici une fois que tu l'as trouvé.
Rien que la boucle principale: on continue tant que le reste est supérieur au diviseur... c'est déjà un problème, comment comparer 2 nombres entrés dans une variable string ?
J'ai pensé à comparer d'abord le nombre de chiffres puis leur ordre lexicographique... mais ça impliquerait qu'il faut enlever tous les zéros inutiles au fur et à mesure, et ça ferait énormément de réallocations
Mouaip... il faudra bien que j'implémente la division euclidienne de toute façon, c'est une classe de calcul sur des grands nombres après tout. (c'est apparemment la seule opération qui posera vraiment problème )
Rien que la boucle principale: on continue tant que le reste est supérieur au diviseur... c'est déjà un problème, comment comparer 2 nombres entrés dans une variable string ?
Donc maintenant tu arrives a comparer tes nombres non?
Ecris ici un algorithme en pseudo code tiré de ce que tu fais à la main.
Oui, c'est amusant de faire une classe de int infini
J'en avais fait une il y a quelques temps (meme si je n'avais pas encore fini de tout surcharger)
La porteuse est une string pour ma part, et apres, les opérations étaient exactement comme on avait appris a l'école primaire
Donc maintenant tu arrives a comparer tes nombres non?
Ecris ici un algorithme en pseudo code tiré de ce que tu fais à la main.
Euh... désolé, je dois avoir le cerveau un peu ramolli par la rentrée scolaire imminente, mais le problème ne change pas: que ce soit dans une variable string ou dans un vector, chaque chiffre est stocké indépendamment des autres
Bien sûr, mais encore une fois, le problème, c'est la comparaison du reste est du diviseur.
Je réadapte ce que j'ai dit:
«on continue tant que le reste est supérieur au diviseur... c'est déjà un problème, comment comparer 2 nombres entrés dans [un vector] ?
J'ai pensé à comparer d'abord le nombre de chiffres puis [chaque chiffre un à un]... mais ça impliquerait qu'il faut enlever tous les zéros inutiles au fur et à mesure, et ça ferait énormément de réallocations»
Enfin... je ne connais pas bien le type vector... il n'y a peut-être pas de réallocations nécessaires
EDIT: je crois que je suis en train de marquer pleins de bêtises... euh... plop
Je te donne un exemple formel pour refaire une addition, a partir d'un stockage sous forme de string :
A l'école, on disait :
"Tu écris les nombres un carreau par chiffre, en les alignant a droite, puis tu additionnes les chiffres, tu stockes le chiffre, et la retenue.
En exemple informatique : tu as 2 strings (qui compotent des chiffres) s1 et s2.
tu dis :
curseurs1 = s1.len()-1; // curseur s1 sur dernier chiffre de s1
curseurs2 = s2.len()-1;
int retenue = 0;
while(curseurs1>=0 && curseurs2>=0)
{
int addition = (s1[curseurs1]-'0') + (s2[curseurs2]-'0') + retenue; // l'addition des 2 chiffres + la retenue (qui au premier coup vaut 0)
// a l'école primaire, on te dit qu'on ne garde que le chiffre des unités, et le chiffre des dizaines, c'est la retenue :)
resultat.ajoute_chiffre_devant(addition%10); // a toi de faire ça : addition%10 te donne le chiffre des unités
retenue = addition/10; // la retenue;
curseurs1--;
curseurs2--;
}
resultat.ajoute_chiffre_devant(retenue);
Voila, comment on refait une addition
Je te laisse faire pour le reste, c'est plus complexe, mais ça marche
La division, ce sera bien plus dur !
Déja parce qu'il faudra d'abord faire la multiplication (en effet, quand on pose une division, on "essaie" de multiplier le/les chiffres que l'on divise par un chiffre pour atteindre ce que l'on cherche...
Et puis, ensuite, il me semble qu'on doit soustraire ce que l'on a trouvé a ce qui existe déja. (ça fait longtemps que je n'ai pas posé de divisions )
Je pense que pour implémenter la division, il faut avoir implémenté les 3 autres opérations
Tiens, au fait, si tu relis mon algo sur l'addition ce dessus, tu dois te dire "l'algo serait plus simple si on avait écrit le nombres "a l'envers" -> en effet, les curseurs iraient dans le bon sens, si j'ose dire, et surtout, pour stocker les résultats, on mettrait les chiffres apres, et non avant ceux existants, ce qui est plus simple par la suite..."
Et ceci explique pourquoi certains processeurs codent leurs nombres, en interne, a l'envers (octets/octets) -> Processeur little endian, IBM PC et compatibles
En fait, stocker le nombre en base 10000 n'est pas du tout la solution puisque ça n'a d'avantage que si on affiche les nombres en base 10... or, pour l'utilisation que je veux en faire (crypto) l'hexadécimal primera... mais sans exclusivité
Grrrr...
Et pour la division, tu parles des 3 autres opérations, mais aussi < en compagnie...
De toute façon, si j'arrive pas à stocker mon nombre, j'aurais du mal à implémenter tout ça
Edit: pourquoi a-t-il fallu qu'on compte en base 10 ?? On ne pouvait pas nous mettre en base hexa dès le primaire ?!!!
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html