elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008
-
6 oct. 2007 à 20:19
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008
-
24 oct. 2007 à 19:50
Bonjour,
Alors en faite je n'arrive pas à stocker dans des variables des nombres depassant la vingtaine de chiffres. Mais je souhaiterais effectuer des calculs avec des nombres beaucoup plus grands (aux environ de 1000 chiffres).
En effet, je suis sur un projet de cryptographie (afin d'appliquer les connaissance vu en cours) ce qui implique des calculs avec de tres grands nombres premiers .....
D'où ma question, est-il possible de stocker des nombres de cette importance dans une variable? si oui comment?
cs_niky
Messages postés168Date d'inscriptionjeudi 28 juin 2001StatutMembreDernière intervention18 octobre 20087 9 oct. 2007 à 19:55
Bon... pour faire la multiplication voilà quelques pistes qui pourraient t'aider.
Déjà, pour stocker la multiplication de deux nombre de n bits, il te faut (au maximum) 2n bits (souviens toi qu'avec l'addition, il fallait au maximum n+1 bits). Mais pour implémenter la multiplication, ce n'est nécessairement ton soucis. Il te suffit de bien dimensionner tes nombres (par exemple tous sur 512 bits) même si la plupart n'utilisent pas toute cette place.
Maintenant, pour réaliser la multiplication de a * b, la méthode la plus simple (mais la moins efficace) est la suivante :
multiplier(a, b) si (a 0 ou b 0)
renvoyer 0
resultat = 0
tant que b > 0 faire
resultat = resultat + a
b = b - 1
fin tant que
renvoyer resultat
Il ne reste plus qu'à l'implémenter en C# !
Pour cela, tu as besoin :
- de la comparaison avec zéro. C'est pas bien dur : il faut que tous les bits soient à zéro pour que ce soit égal à zéro ;
- d'affecter initialement zéro à résultat : tout aussi trivial
- additionner resultat et a : tu as déjà ce code puisque qu'il s'agit de celui que je t'avais donné
- soustraire 1 à b
Pour soustraire 1 à un nombre binaire, c'est très simple :
1. Tu pars du bit de poids le plus faible (les "unités" quand on est en base décimale).
2.
2.1 Si le bit est à 1, tu le mets à zéro et tu sautes à l'étape 4
2.2 Si le bit est à 0, tu le mets à 1 et tu continues avec le bit suivant (les "dizaines", "centaines", etc.)
3.
3.1 Si le dernier bit n'est pas atteint, revenir à l'étape 2
3.2 Sinon, passer à l'étape 4 (si tu arrives ici, cela veut dire que tu as soustrait 1 au nombre zéro)
4. Opération terminée
Maintenant, tu as des tas d'optimisation envisageables. Par exemple, tu te verras qu'en faisanta 5 et b 7564423
la multiplication se révèlera plus intéressante si tu fais la soustraction sur a (le plus petit de a et b) et l'addition avec b (le plus grand de a et b).
En tapant "algorithme de multiplication" dans un moteur de recherche, tu trouveras d'autres façon bien plus performantes pour arriver au même résultat.
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 9 oct. 2007 à 21:33
oki,
Tout d'abord je suis tout à fait d'accord avec toi sur le principe (heureusment pour moi...).
Mais toujours une incompréhension...
- Je comprend pas tout a fait un point: J'ai l'impression que des fois on fait les operations sur les binaires et des fois sur les bases dix.... Là quand tu me decrit la facon de soustraire 1 on est dans le binaire. Mais dans ce cas l'addition: "result[i] += a[i] + b[i];" ou encore "result[i]++;" ce serait donc des operation sur les bases dix...... car pour l'incrementation en binaire il faudrait faire pareil que pour la soustraction en changeant les 1 en 0 dans ton explication , non?
Car autrement ca reviendrait à ecrire b-- (parallelement à "result[i]++;")
Et une question:
- Dans ton explication de la soustraction tu parle des bits (0 ou 1) mis dans le tableau ce sont des suites de bits que l'on a comment tu fais pour les avoir un par un?
Et puis si on les a un par un, la méthode que j'avais songeais auparavant n'est-elle pas legerement plus performante?
Ma méthode: "si on decompose un des deux nombres en forme binaire dans un tableau [pour obtenir les bit un par un et non une suite de bits], on doit pouvoir multiplier l'autre nombre bit par bit facilement et aditionner les resultats (bien sur avec un declage de puissance de 2)"?
Exemple:
a * 1001 = a + 0*a*2^1 + 0*a*2^2+ a*2^3 = a + a*2^3
Encore merci pour toute ton aide et le temp que tu passe pour repondre à mes questions,
elephant13
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 10 oct. 2007 à 17:14
Oki,
Normalement cette fois j'ai tout compris, je suis pret à essayer la dision.... je le ferais en fin d'aprem car la priorité aux devoirs ....
Encore merci
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 20 oct. 2007 à 19:08
Bonjour à tous,
Me revoila :) .....
Alors ca fais un moment que je n'ais pas eu le tempde programmer faute de temps mais là je vais pouvoir m'y remettre. Alors j'ai des idées d'algo mais j'ai un problème pour les tester : Sur un brouillon j'ai converti deux nombres binaire en decimale pour pouvoir verifier le resultat, jusque là c'est bon .... mais c'est après, quand je souhaite rentrer les nombres en binaire dans visual c# express que ca se complique car lui il comprend que c'est un decimale est donc le nombre est trop grand pour la variable... alors comment indiquer a visual que je lui rentre un nombre en binaire et non en decimal ????
En vous remerciant d'avance.
Vous n’avez pas trouvé la réponse que vous recherchez ?
cs_niky
Messages postés168Date d'inscriptionjeudi 28 juin 2001StatutMembreDernière intervention18 octobre 20087 21 oct. 2007 à 16:45
Tu auras du mal à lui dire qu'un nombre est binaire vu que c'est impossible.
Par contre, tu peux prendre la calculatrice Windows et, dans le mode scientifique, tu tapes le nombre en binaire (en cochant la case Binaire). Ensuite, tu coches la case Hexadécimal (ou Décimal). L'ordinateur te fait la conversion du nombre binaire automatiquement. Tu n'as plus qu'à entrer ce nombre dans ton code (en le faisant précédent d'un 0x s'il s'agit d'héxadécimal).
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 21 oct. 2007 à 20:51
Oki,
de toute facon c'est ce que j'ai fais en atendant une reponse ......
Alors j'ai fais le code de la soustraction:
- j'ai surchargé ton algo de desincrementation ainsi:
uint[] Decrement(uint[] a, int longa)
{
// longa est en fait la longueur du tableau a.
// On fait une copie du nombre passé en paramètre
// parce qu'ici, on ne souhaite pas que a soit modifié par
// les calculs (c'est un choix, rien de plus!)
uint[] result = new uint[longa];
for (int j=0; j<longa;j++)
{
result[j] = a[j];
}
for (int i = 0; i < 2; i++)
{
result[i]--;
/* Si la décrémentation a généré un nombre plus petit que
l'original, alors c'est bon...
*/
if (result[i] < a[i])
break;
/* Sinon, cela signifie qu'on a fait 0 - 1, ce qui (sur des entiers positifs)
provoque un dépassement de capacité et nous renvoie quelque chose comme
2^32-1... dans ce cas, on continue de faire la décrémentation sur les
bits de poids plus forts
*/
}
return result;
}
- puis créer cette methode de comparaison (on test si a est superieur à b):
bool sup(uint[] a, int longa, uint[] b, int longb)
{ //longa longeur de a et longb longueur de b
bool sup = false;
if (longa >= longb)
{
// on verifie si le tableau de a est plus grand que celui de b, sinon on considere que b est plus grand que a.
if (longa > longb)
{
// on teste si a est plus long que b, si c'est le cas, on considere que a est superieur à b.
sup = true;
}
else
{
// sinon, sa veut dire que a et b ont la même longuer, on va donc comparer chacune de leur cellule jusqu'à en trouver une de a supérieur à b, si tel est le cas on passe la valuer sup à true et on ne test pas les autres valeurs.
for (int i = 0; i < longa; i++)
{
if (a[i] > b[i])
{
sup = true;
break;
}
}
}
}
// on returne une valeur bool, true si a>b et false si a= b[i])
{
result[i] = a[i] - b[i];
}
else
{
uint trop;
trop = b[i] - a[i];
result[i] = 0;
for (int j = 0; j < longa; j++)
{
Decrement(result, longa);
}
}
}
}
//et on retourne sous forme de tableau le resultat de la soustraction.
return result;
}
Bon alors je viens tout juste de mettre les commentaire, j'espère que tu comprenderas ce que j'ai voulu dire...
Autrement mon seul problème et pout l'affichage car quand j'affiche les tableaux, si par exemple la cellule avec les bits de poids faible est égale à 0012 et celle avec les bits de poids forts est de 2352, cela m'affiche 235212, ca n'affiche pas les zeros... alors j'ai essayer de decaler de 2^64 mais on ne peut pas multiplier des les objets de type string il me semble... Alors je sais pas trop comment m'y prendre.
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 21 oct. 2007 à 20:57
Alors je voulais juste dire qu'en regardant mon message, j'ai remarquer que du moins pour les deux premiers commentaires de la comparaisons, ces commentaires s'appliquent au "if" qui les precedent, contrairement aux suivants ....
désolé pour ce petit inconvenient ainsi que les problèmes de mise en page ...
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 22 oct. 2007 à 21:37
PourPrenons dans l'ordre:- for (int i 0; i < longa; i++) -> for (int i longa - 1; i >= 0; i--)
evidement, j'avais deja fais la modification pour l'affichage et j'ai oublier de modifier les fonction .......
-Le fait de considérer que si longa > longb alors a > b est un sacré raccourci.
Oui c'est pour cela que dans les commentaires j'ai mis "on considere que"... puisque j'ai conscience de la lmite de ce calcul mais bon effectivement si on peu s'en passer c'est mieux ..
-Dans la soustraction, pourquoi calcules-tu "trop" si tu ne t'en sers pas par la suite ?
Alors ca c'est l'erreude frappe a la con , pardon de l'expression mais bon, ... c'est en fait dans la methode for suivante:
for (int j = 0; j <trop; j++)
{
// on decrement ce qui etait en trop pour la premier cellule
Decrement(result, longa);
}
- Merci pour l'algo de soustraction. Effectivement c'est beaucoup plus simple...
Mais tout de même des interrogation, le fait d'utiliser un uint dans la méthode inverse ne posera pas de problème si on inverse un nombre positif en négatif?
-Autrement pour l'affichage des "0", je souheterais juste une précision. Imaginons que ce sont des entiers de 12 bit donc jusque 4095 en decimal je crois, pour un affichage complet de toutes les valeurs il faut l'obbliger à mettre au moins quatres chiffres. Mais un exemple:
imaginons le nombre 4095001, 5001 est trop pour etre stocker dans une variable donc on stocke 001 dans la premiere est 4095 dans la seconde. Mais si on obblige l'affichage de 4 chiffres cela va m'afficher 40950001, non? Où est l'erreur ???
Encore merci pour le temps que tu me consacre,
Cordialement,
elephant13
cs_niky
Messages postés168Date d'inscriptionjeudi 28 juin 2001StatutMembreDernière intervention18 octobre 20087 22 oct. 2007 à 23:10
En ce qui concerne l'utilisation des uint pour des négatifs, ça ne pose pas de problème au contraire. Le fait d'utiliser des entiers non signés te permet de gérer et d'interpréter toi même les résultats. Je n'ai pas étudié si les calculs fonctionnent aussi bien avec des entiers signés. Il est très probable que ça ne change pas grand chose.
Pour ton nombre 4095001, je pense que ton erreur vient du mélange entre les bases. Considérons effectivement le nombre 4095001 (écrit ici en base 10). En binaire, on obtient :
1111100111110000011001
Le premier paquet de 12 bits (en partant de la droite) : 110000011001
Le second paquet de 12 bits (en complétant avec des zéros à gauche) : 001111100111
Le premier paquet (bits de poids faible) fait en décimal : 3097 (et non pas 1, ni 5001)
Le second paquet fait : 999 (et pas 409, ni 4095).
Ca vient tout simplement du fait que 4095001 = 3097 + (2^12) * 999
Ce que je cherche à raconter avec tout ce charabia, c'est que 4095001 5001 + 409 * 10 ^ 4/= 5001 + 409 * 2 ^ 12
(=/= signifie "différent de").
Garde toujours en tête que les règles opératoires sont toujours les mêmes quelque soit la base utilisées :1) Si x op y z dans la base b alors x op y z dans la base b' (où x et y sont des nombres quelconques et op une opération arithmétique).
2) En revanche, DEF op GHI JKL écrit dans la base b (où D, E, F, G, H, I, J, K, L sont des chiffres de la base b) alors DEF op GHI/= JKL écrit dans la base b' (si b =/= b')
(=/= signifie "différent de")
Le 1) est démontrable mais relève surtout du bon sens. Car quelque soit la base qu'on utilise 2 + 2 font toujours 4 (ça marche en décimal, pour additionner des minutes (base 60), additionner des heures (base 24), etc.).
Le 2) est facile à démontrer en décomposant les nombres :
DEF = D * b ^ 2 + E * b + F
GHI = G * b ^ 2 + H * b + I
JKL = J * b ^ 2 + K * b + L
Il faut montrer que (preuve par l'absurde)
(D * b ^ 2 + E * b + F) op (G * b ^ 2 + H * b + I) = (D * b' ^ 2 + E * b' + F) op (G * b' ^ 2 + H * b' + I)
et J * b ^ 2 + K * b + L = J * b' ^ 2 + K * b' + L
Tout ceci est vrai si et seulement si b = b'.
En conclusion, ne confond pas la valeur d'un nombre et sa notation. La valeur est absolue, la notation n'est que pure représentation...
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 23 oct. 2007 à 19:19
Effectivement, pour mon nombre 4095001, mon erreur vient du mélange entre les bases...
A chaque fois c'est la même chose... problème de mélange de base.
La prochaine fois je fairais encore plus atention avant de poster...
elephant13
Messages postés23Date d'inscriptionmercredi 16 mars 2005StatutMembreDernière intervention 7 avril 2008 24 oct. 2007 à 19:47
Ok,
Merci beaucoup,
Je vais faire les petites modifactions que tu m'asuggérées.
Et puis je reviendrais posté ici si j'ai des problèmes dans la suite du devellopement.