Manipuler de grands nombres
Résoluyg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
J'ai un exercice très long dans lequel on me demande de manipuler de grands entiers. Je n'arrive pas à faire le début de l'exercice et donc il est m'est impossible de faire le reste.
Je veux juste comprendre le début pour bien démarrer et ensuite je pourrais faire la suite (du moins j'espère).Votre aide me sera précieuse
On m'a donné ceci et il faut que je le complète :
tall_integer *ge_cree(void) { return NULL; } void free(tall_integer *e) { } tall_integer *set_bit(tall_integer *e, uint32_t x) { return NULL; } tall_integer *clr_bit(tall_integer *e, uint32_t x) { return NULL; } char get_bit(tall_integer *e, uint32_t x) { return 0; } int nb_bits(tall_integer *e) { return 0; } tall_integer *add(tall_integer *b, tall_integer *a) { return NULL; } tall_integer *shift(tall_integer *a, int nb_bits) { return NULL; } tall_integer *mul(tall_integer *b, tall_integer *a) { return NULL; }
La question 1 concerne les fontions creer et liberer .
Pour creer, on me demande de créer dans le tas un grand entier de 32 bits débutant à la valeur 0 et de renvoyer un pointeur sur ce dernier. La fonction renvoie NULL si l'entier n'a pas pu être créé.
Pour liberer, c'est pour juste libérer l'entier créé.
Mon problème surtout est qu'on me demande de définir moi même le type tall_integer et c'est ça mon problème et qui m'empêche d'avancer et comment créer un entier
Pour libérer je suppose que je dois juste mettre free(...)
...=entier à libéré
Moi je pensais en C il fallait juste écrire int entier et hop on a créé un entier mais vu les questions de mon exercice je me dis que ça doit pas être ça qu'on me demande...
- Manipuler de grands nombres
- Code binaire des nombres - Guide
- Nombre de jours entre deux dates excel - Guide
- Nombres faciles - Télécharger - Outils professionnels
- Formule excel écart entre deux nombres - Forum Excel
- Alexia organise un appel vidéo avec ses grand-parents qui ne veulent pas installer de logiciel ou d’application, ni créer un compte. - Forum Windows
27 réponses
Bonjour,
Le tas correspond à toutes les allocations dynamiques, donc faites par malloc (comme le souligne [Dal] dans #5) ou calloc. Tu as dû en entendre parler puisque tu connais la fonction free (celle-ci ne peut et ne doit s'utiliser que conjointement qu'avec une allocation dynamique réussie, c'est à dire telle que malloc (ou calloc) ait renvoyé un pointeur non NULL).
Le tas est à mettre en opposition avec la pile, qui mémorise (notamment) toutes les variables locales et paramètres des fonctions en cours d'appel ainsi que la variable.
Pour ton exercice, un type se déclare avec typedef. Cela permet de créer un alias sur un type arbitraire (y compris s'il s'agit d'un type de pointeur). Si tu veux définir un type plus compliqué, tu peux définir un typedef sur une structure de donnée (struct) ou une union.
Sous sa forme actuelle, l'exercice est un peu étrange car il suffit en effet d'écrire :
typedef uint32_t tall_int;
... pour pouvoir poursuivre tout l'exercice. Et du coup, il n'y a pas vraiment de raison que mul, add (etc) retourne un tall_int * au lieu d'un tall_int.
Si on veut rendre l'exercice plus pimenté, on peut imaginer définir une structure de donnée qui créer un buffer de taille arbitraire. Par contre ça rend l'exercice subitement beaucoup plus compliqué car typiquement tu ne peux plus vraiment utiliser directement les opérateurs natifs du C. La signature de ge_cree ne prévoit d'ailleurs pas de donner la taille dudit buffer. Mais en admettant que ce soit ce qu'on attende de toi, ça pourrait ressembler à :
#include <stdint.h> // uint*_t #include <stdlib.h> // malloc, free #include <string.h> // calloc typedef struct tall_int { uint8_t * data; size_t size; } tall_int; tall_int * ge_alloc() { tall_int * ge = malloc(sizeof(tall_int)); if (!ge) return NULL; ge->size = 10; // entier sur 10 octets ge->data = (uint8_t *) calloc(sizeof(uint8_t), ge->size); if (!ge->data) { free(ge); return NULL; } return ge; } void ge_free(tall_int * ge) { if (ge) { if (ge->data) free(ge->data); free(ge); } } int main() { tall_int * pge = ge_alloc(); // ... ge_free(pge); return 0; }
On pourrait également regretter que dans le squelette de ton exercice, la fonction free entre directement en collision avec la fonction de la librairie standard, et devrait donc probablement être renommée ge_free() ou ge_libere().
Bonne chance
bonjour,
l'exercice fait suite à un cours sur quel sujet?
C'est suite a un cours mais tres tres court sur la manipulationde bits
En fait ils disent les grands entiers ,ils son tcodés sur plus de bits que ne peuvent en contenir les entiers disponibles dans le langage.Parfois on en a besoin par exemple dans certaines domaines où il faut utiliser de grands chiffres
Non j'ai pas de cours la dessus mais l'enonce a dit on veut créer de grands entiers dynamiquement dans le tas .Meme si, au debut, ils n'ont que 32 bits, il faudra écrire des fonctions d'allocation et de liberation.En effet,dans l'exo ils ont supposé au debut que que les entiers ont une taille fixe de 32 bits et ils ont dit que pour les autres parti de l'exo on augmentera cette taille
mais moi je sais meme pas ce que ça veut dire créer dans le tas,cette phrase elle n'a pas pour moi beaucoup d'importance.!
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre questionMerci pour ces quelques éclaircissements. Je dois revoir un peu mon cours sur la mémoire en C avant d'attaquer cet exercice.
J'ai fini de réviser tout mon cours et je comprends maintenant les types uint8_t et les histoires de tas et de pile et autres et ce que vous avez fait.Je vias essayer de faire le reste et je vous en tiendrais au courant
Parfait, bon courage ! La question initiale étant réglée, je bascule le sujet en résolu. Si tu as d'autres questions par rapport à ton exercice, merci d'ouvrir un nouveau fil de discussion afin de garder le forum propre (un problème par discussion).
Bonne continuation
d'accord merci la reponse a mes codes je le metterais dans un autre fil de discussion
Merci, mais ça n'est pas nécessaire, à moins que tu sois particulièrement fier de ton code :-).
Je m'explique : le but d'un forum est de poser dans chaque discussion un petit problème, clair et réutilisable. Pour cela il doit mettre en jeu une notion minimale et clairement identifiée. Dans les sous-forums liés aux systèmes, ce serait typiquement installer un logiciel particulier, résoudre un message d'erreur particulier, réaliser une tâche d'administration système ou réseau particulière, etc. Dans les sous-forums liés à la programmation, ce serait comment réaliser une tâche minimale particulière, comment utiliser une fonction, comment résoudre une erreur de programmation ou un bug ; mais pas comment réaliser un exercice ou un projet de A à Z.
En effet, le but est que les gens puisse facilement trouver sur le forum avec un minimum de lecture la réponse précise à leur question (qui a peu de chance d'être exactement ton exercice, en tout cas pas dans sa globalité).
C'est d'ailleurs pour ça qu'à moins que l'exercice soit extrêmement court, on est souvent un peu récalcitrants à répondre à un exercice, car outre les aspects négatifs sur le plan pédagogique, un exercice met souvent en jeu plusieurs notions.
Dans le cas présent, le but de ce fil de discussion discussion était de définir un type personnalisé, discuter comment l'allouer et le désallouer. Comme je pense que pour ce problème initial, tout a été dit, j'ai proposé de basculer le sujet en résolu. Si cependant tu fais face à d'autres difficultés, je t'invite à ouvrir un nouveau fil de discussion dans lequel tu proposeras un exemple minimal mettant ton problème en évidence, on ce fil de discussion se limitera spécifiquement à ce problème.
Bonne chance
Ok je comprends merci
Juste une question,avec votre exemple si je veux par exemple manipuler des entiers de 32bits à la place de uint8_t on met uint32_t?
D’après ce qu’elle j’ai compris du code de mamiemando, il a alloué de l’espace pour 10 entier de type uint8_t et donc de taille 1 octet = 8 bits et donc la taille sera 10 x 8 = 80 octets
Car si on écrivait par exemple calloc(4, sizeof(int)) on allouerait l’espace pour 4 entiers, or comme un entier fait 4 octets, la taille du bloc alloué de 4 x 4=16 octets
N’est-ce pas?
Donc si je veux alloue de l’espace pour 1 entier de 32 bits soit 1 octet, donc de taille 1 x 1 = 1 octet, et donc je dois faire:
#include <stdint.h> // uint*_t #include <stdlib.h> // malloc, free #include <string.h> // calloc typedef struct tall_int { uint32_t * data; size_t size; } tall_int; tall_int * ge_alloc() { tall_int * ge = malloc(sizeof(tall_int)); if (!ge) return NULL; ge->size = 1; ge->data = (uint32_t *) calloc(sizeof(uint32_t), ge->size); if (!ge->data) { free(ge); return NULL; } return ge; }
Et si je veux par exemple augmenter la capacité par exemple 1056 bits (132 octets)soit 33 fois la taille de uint32_t (donc 33 incrémentation de 32 bits)je dois faire
#include <stdint.h> // uint*_t #include <stdlib.h> // malloc, free #include <string.h> // calloc typedef struct tall_int { uint32_t * data; size_t size; } tall_int; tall_int * ge_alloc() { tall_int * ge = malloc(sizeof(tall_int)); if (!ge) return NULL; ge->size = 1; ge->data = (uint32_t *) calloc(sizeof(uint32_t)*33, ge->size); if (!ge->data) { free(ge); return NULL; } return ge; }
Et enfin, si par exemple je veux me débrouiller pour que la quantité de mémoire que j’alloue correspond aux besoins de stockage de mon entier.
De plus, si je suppose que mon entier a une taille par défaut (par exemple, 64 bits), mais que cette taille n’est pas suffisante, pour que je puisse mettre un ou plusieurs bits de supplémentaires (par exemple mettre un bit à 1). De base pour mettre l’entier a un bit à 1 on fait: a | 1 << position
Autre question, mieux vaut augmenter ma taille de 1 lors du realloc, ou bien doubler la taille du bloc ?
Je veux juste comprendre ces subtilités et je pense que ça sera bon.
Vos impressions sont exactes ,je dois faire des additions et soustraction de bit .Et meme jusqu'a hier je reflechissais comment faire ma fonction addition pour qu'il gere le cas de la derniere retenue(sans cette derniere retenue le nombre binaire resultat de l'addition des bits de 2 nombres binaires sera fausse
On m'a dit c'est pas tres intelligent de faire des if ex:0+1=1
1+1=10
etc
Idem pour la soustraction
Mais bon pour ne pas trop me disperser j'ai prefere comprendre d'abord le type grand entier comment il fonction set bit et clr bit
...mon message d'aujourd'hui a 5h du mat
j'ai pas encore eu d'ailleurs de reponse
Je viens tout juste de voir que il m’a répondu à 9:38 bizarre je l’avais même pas vu
j’ai vu hier que celui à 18h .Bref oubliez ce que j’ai dit alors.Je vais analyser sa réponse du coup
Merci
bonjour j'ai essayé de faire la soustraction et l'addition si j'ai des int .Pour l'addition ça marche mais pas la soustraction et pourtant A-B=A+(-B)=1+(inversion des bits de B+1)
#include <stdio.h> int add(int x, int y) { int keep = (x & y) << 1; int res=x^y; return keep^res; } int convertir_binaire(int x){ int i; for(i=7;i>=0;i--){ printf("%d",(x>>i)&1); } } int soustraction(int x, int y) { int a=add(~y,1); return add(x,a); } int main(){ printf("5 en binaire:");convertir_binaire(5); printf("\n"); printf("4 en binaire:"); convertir_binaire(4); printf("\n"); int a=add(5,4); printf("Le résultat de l'addition binaire de 5 et 4:");convertir_binaire(a); printf("\n"); int b=soustraction(5,4); printf("Le résultat de la soustraction binaire de 5 et 4:");convertir_binaire(b); return 0; }
Le résultat de l'addition binaire de 5 et 4:00001001
Le résultat de la soustraction binaire de 5 et 4:11111101 ce qui est faux
Bon ensuite comment j'adapte mon code au tall_integer scahnt que je ne manipule pas des int ici
Je viens de voir que ça me donne que des 0,donc ça marche pas .je suis dit comme ça marche pour 1 ça veut dire c’est bon mais bon c’était donc qu’un coup de chance que ça a marché pour 5 et 4.Bon je vais essayer de trouver le soucis
J'ai réfléchi toute la journée mais j'arrive pas a faire l'adition.Un petit coup de main me sera trés utile
Si pour de simple entier je n'arrive pas il me sera impossibl de le faire pour tall integer
Mon autre code il marchait pas car a un moment j'ai:
(0000 0010 ) xor ( 0000 0100)=0000 0000 ne tient pas compte de la retenue et donc on n'obtient pas 0000 00100
Oui moi je l'ai fait .Sans exemple sur papier je n'aurais pu rien faire
Moi je sais juste que pour connaitre la retenue faut faire un ET LOGIQUE et j'ai fait ça dans mon code mais ça marche pas
Les 4 opérations pour une addition binaire c'est XOR qui me permet de le faire
Addition de décimaux je vois pas en quoi ça peut m'aider
Exemple:8+2=10
Bon par exemple addition binaire de 1 et 3
1=0 0 0 0 0 0 0 1
3=0 0 0 0 0 0 1 1
-------------------------------
= 0 0 0 0 0 1 0 0
Pour faire une additioon il faut que j'utilse xor car 0 xor 0=°
0 xor 1=1
1 xor 0 =1
1 xor 1=0
Donc l'opération parfaite pour faire une addition
Pour gérer les retenues,j'utilse & car :
0 &0=0
0 &1=0
1 &0=0
1&1=1
a &b je dois décaler à droite d'1 position le résultat pour pouvoir isolé le bit de poids faibe
EX:(1&3)=1= 0000 0001
décalage a droite= 0 0000 0010
Ce nombre est donc le résultat de (1&3)<<1
Ensuite si je fait (1 xor 3) on a 2=0000 0010
ET donc si j'additione (1 xor 3) avec (1&3)<<1 j'obtient le résultat voulu a savoir 4 carù
(1&3)<<1= 0 0000 0010
1 xor 3= 0000 0010
------------------------------
= 0 0000 0100
Mais bon cette derniere etape je peux pas utiliser xor car il ne me permet pas d'ajouter les retenues
Je sais comment ajouter cette retenue a la 3 colonne
J'ai pensé que peut etre une fonction pourrait le faire mais bon j'ai pas pu implenter cette fonction secondaire pour ajouter une retenue a la colonne suivante
Si par exemple
10,5
+ 2,9
----------
= 13, 4
oui je sais faire
En addition décimal des qu'une addition de nombre est >=10 on a une retenue et cette retenue on l'ajoute a la colonne suivante,c'est comme çà qu'on gére les reports
Esceque vous voulez que j'ecris une fonction qui additionne en décimal et puis je converti ce nombre en binaire?
Si c'est le cas,je veux le faire aussi en raisonnant sur les bits