Tres longue variable
Résolu
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
-
6 oct. 2007 à 20:19
elephant13 Messages postés 23 Date d'inscription mercredi 16 mars 2005 Statut Membre Dernière intervention 7 avril 2008 - 24 oct. 2007 à 19:50
elephant13 Messages postés 23 Date d'inscription mercredi 16 mars 2005 Statut Membre Dernière intervention 7 avril 2008 - 24 oct. 2007 à 19:50
33 réponses
cs_niky
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
6 oct. 2007 à 23:01
6 oct. 2007 à 23:01
Salut,
Tu ne peux pas stocker directement des nombres aussi grands. Les types de bases sont généralement limités à 64 bits (c'est le cas de .Net avec les long), ce qui représente une vingtaine de chiffres en base décimale.
Ce que tu peux faire, c'est créer ton propre type de nombres. Le principe consiste à créer une classe qui stocke un tableau d'entiers (par exemple de taille 4) :
int[] nbre = new int[4];
A partir de là, tu disposes de 32 (taille des int) * 4 = 128 bits pour stocker un nombre :
- les 32 premiers bits sont stockés dans nbre[0]
- les bits 33 à 64 sont stockés dans nbre[1]
- etc.
Cela implique juste de recoder les opérations d'addition, de soustraction, etc. pour permettre de travailler avec ces nombres. En effet, lors des calculs, il faut gérer le report de la retenue entre deux éléments du tableau nbre. Tu peux envisager d'implémenter cela en utilisant la surcharge d'opérateurs disponible en C#.
Pour référence, tu peux voir l'implémentation de la classe BigInteger du langage Java qui réalise exactement ce type de traitement. A noter que le code de cette classe est un peu effrayant : les algorithmes utilisés sont assez costauds :-)
Tu ne peux pas stocker directement des nombres aussi grands. Les types de bases sont généralement limités à 64 bits (c'est le cas de .Net avec les long), ce qui représente une vingtaine de chiffres en base décimale.
Ce que tu peux faire, c'est créer ton propre type de nombres. Le principe consiste à créer une classe qui stocke un tableau d'entiers (par exemple de taille 4) :
int[] nbre = new int[4];
A partir de là, tu disposes de 32 (taille des int) * 4 = 128 bits pour stocker un nombre :
- les 32 premiers bits sont stockés dans nbre[0]
- les bits 33 à 64 sont stockés dans nbre[1]
- etc.
Cela implique juste de recoder les opérations d'addition, de soustraction, etc. pour permettre de travailler avec ces nombres. En effet, lors des calculs, il faut gérer le report de la retenue entre deux éléments du tableau nbre. Tu peux envisager d'implémenter cela en utilisant la surcharge d'opérateurs disponible en C#.
Pour référence, tu peux voir l'implémentation de la classe BigInteger du langage Java qui réalise exactement ce type de traitement. A noter que le code de cette classe est un peu effrayant : les algorithmes utilisés sont assez costauds :-)
cs_niky
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
7 oct. 2007 à 18:50
7 oct. 2007 à 18:50
Oki doki...
Je vois ce que tu veux faire. Pour faire 183^1079 mod 5141, il te faut écrire la puissance (donc la multiplication et l'addition) et le modulo (donc la division et la soustraction). Donc presque tout :-)
Pour t'aider à commencer, je vais te montrer comment faire une addition sur une tableau de 2 entiers de 32 bits (qui représentent donc un nombre de 64 bits)... attention, tout ça se fait sur des entiers non signés :
/*
Additionne a et b
a et b doivent être des tableaux de longueur 2 (si non, il faut adapter le code)
a[0] (respectivement b[0]) contient les bits de poids faibles de a (resp. b)
a[1] (resp. b[1]) contient les bits de poids forts de a (resp. b)
C'est à dire : a = a[0] + 2^32 * a[1]
*/
public static uint[] Addition(uint[] a, uint[] b)
{
bool carry = false; // indique s'il y a une retenue
uint[] result = new uint[2];
for (uint i = 0; i < 2; i++)
{
result[i] += a[i] + b[i];
/*
Incrémente encore le résultat de 1 s'il y a une retenu
Comme on est en base 2, la retenue est soit de zéro, soit de 1
*/
if (carry)
result[i]++;
/*
On calcul s'il y a une retenue pour le tour suivant
C'est le cas si le résultat de l'addition est plus petit que a (ou b)
En effet, cela signifie que l'addition a provoqué un dépassement de capacité
pour le processeur et qu'il a du tronqué un bit du nombre.
*/
carry= (result[i] < a[i]);
}
/*
ATTENTION ! Si à ce stage carry est à true, cela signifie que l'addition a
provoquée un dépassement de capacité (il aurait fallu faire l'addition sur au moins
65 bits parce que a et b étaient trop grand pour que a+b tiennent sur
64 bits).
*/
return result;
}
Je te laisse imaginer la généralisation de cet algo avec des entiers plus grands (=> remplacer les "2" avec la taille des tableaux).
Pour faire 270363096527615 + 68388485210612178, il suffit de pratiquer ainsi :
uint[] a = new uint[] { 0xd05432ff, 0x0000f5e4 }; // = 0x0000f5e4d05432ff (hexa)= 270363096527615 (décimal)
uint[] b = new uint[] { 0x07b4a1d2, 0x00f2f6f7 }; // = 0x00f2f6f707b4a1d2 (hexa) = 68388485210612178 (décimal)
uint[] res = Addition(a, b);
Ce qui doit te renvoyer 0xF3ECDBD808D4D1 (res[0] = D808D4D1, res[1] = F3ECDB).
Si tu veux avoir la représentation décimale à l'écran (68658848307139793 pour notre calcul), il te faut faire la conversion de la base 2 à la base 10. Pour arriver à cela, encore faut il implémenter la division et le modulo ;-)
Good luck !
Je vois ce que tu veux faire. Pour faire 183^1079 mod 5141, il te faut écrire la puissance (donc la multiplication et l'addition) et le modulo (donc la division et la soustraction). Donc presque tout :-)
Pour t'aider à commencer, je vais te montrer comment faire une addition sur une tableau de 2 entiers de 32 bits (qui représentent donc un nombre de 64 bits)... attention, tout ça se fait sur des entiers non signés :
/*
Additionne a et b
a et b doivent être des tableaux de longueur 2 (si non, il faut adapter le code)
a[0] (respectivement b[0]) contient les bits de poids faibles de a (resp. b)
a[1] (resp. b[1]) contient les bits de poids forts de a (resp. b)
C'est à dire : a = a[0] + 2^32 * a[1]
*/
public static uint[] Addition(uint[] a, uint[] b)
{
bool carry = false; // indique s'il y a une retenue
uint[] result = new uint[2];
for (uint i = 0; i < 2; i++)
{
result[i] += a[i] + b[i];
/*
Incrémente encore le résultat de 1 s'il y a une retenu
Comme on est en base 2, la retenue est soit de zéro, soit de 1
*/
if (carry)
result[i]++;
/*
On calcul s'il y a une retenue pour le tour suivant
C'est le cas si le résultat de l'addition est plus petit que a (ou b)
En effet, cela signifie que l'addition a provoqué un dépassement de capacité
pour le processeur et qu'il a du tronqué un bit du nombre.
*/
carry= (result[i] < a[i]);
}
/*
ATTENTION ! Si à ce stage carry est à true, cela signifie que l'addition a
provoquée un dépassement de capacité (il aurait fallu faire l'addition sur au moins
65 bits parce que a et b étaient trop grand pour que a+b tiennent sur
64 bits).
*/
return result;
}
Je te laisse imaginer la généralisation de cet algo avec des entiers plus grands (=> remplacer les "2" avec la taille des tableaux).
Pour faire 270363096527615 + 68388485210612178, il suffit de pratiquer ainsi :
uint[] a = new uint[] { 0xd05432ff, 0x0000f5e4 }; // = 0x0000f5e4d05432ff (hexa)= 270363096527615 (décimal)
uint[] b = new uint[] { 0x07b4a1d2, 0x00f2f6f7 }; // = 0x00f2f6f707b4a1d2 (hexa) = 68388485210612178 (décimal)
uint[] res = Addition(a, b);
Ce qui doit te renvoyer 0xF3ECDBD808D4D1 (res[0] = D808D4D1, res[1] = F3ECDB).
Si tu veux avoir la représentation décimale à l'écran (68658848307139793 pour notre calcul), il te faut faire la conversion de la base 2 à la base 10. Pour arriver à cela, encore faut il implémenter la division et le modulo ;-)
Good luck !
cs_niky
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
9 oct. 2007 à 22:54
9 oct. 2007 à 22:54
Pour commencer, dans l'algo de la multiplication que je t'ai donné, je mélange quelque peu les écritures.
Dans mon esprit, quand l'ordinateur fait des calculs, il n'y a jamais de prise en compte de la base (parfois de la base 2 mais c'est assez rare). Le problème c'est que le vocabulaire est assez trompeur. Lorsqu'on parle de chiffre, on associe généralement cela à la base 10 (les chiffres va de 0 à 9). En base 2, on parlera plutôt de bits.
Dans la base 10, on parlera d'unités, dizaines, centaines, milliers, etc. En base 2, on a moins de vocabulaire. Alors on parle de bit de poids faible, de poids fort... c'est pas toujours plus clair alors on mélange les notations.
Bref, tout ça pour dire que ça ne simplifie pas les explications :-)
Pour éclaircir l'algo que je t'ai donné, le voilà retouché pour te montrer qu'on parle toujours de "BigInteger" (toujours sur 64 bits pour simplifier les écriture) :
uint[] Multiplier(uint[] a, uint[] b)
{
if (IsZero(a) || IsZero(b))
return new uint[] { 0x0, 0x0 };
uint[] resultat = new uint[] { 0x0, 0x0 };
while (!IsZero(b))
{
resultat = Addition(resultat, a); // On reprend la méthode Addition qu'on avait écrite
b = Decrement(b);
}
return resultat;
}
// Renvoie true si le nombre passé en paramètre est égal à zéro
bool IsZero(uint[] n)
{
if (n[0] == 0 && n[1] == 0) // Vérifie que tous les éléments du tableau sont à zéro
return true;
else
return false;
// Tu peux aussi condenser tout ça en une seule ligne :
// return (n[0] == 0 && n[1] == 0);
}
uint[] Decrement(uint[] n)
{
// On fait une copie du nombre passé en paramètre
// parce qu'ici, on ne souhaite pas que n soit modifié par
// les calculs (c'est un choix, rien de plus!)
uint[] result = new uint[] { n[0], n[1] };
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] < n[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;
}
bon bah... du coup je t'ai tout programmé :-p
Je souhaite que ça t'aide à mieux comprendre.
Sache que l'algo de décrémentation que je t'ai noté dans mon précédent post était un peu tiré par les cheveux (bah vi... j'ai pas réfléchi !). Il t'obligeait à extraire chaque bit de chaque entier... C'est un peu lourd (mais possible). Si tu regardes bien, l'algo que je t'ai mis là fait exactement la même chose mais directement sur un entier (donc un paquet de 32 bits).
Enfin, pour illustrer la décrémentation, voici deux exemples (les nombres sont écrits en binaires et on imagine avoir créé un "BigInteger" de deux entiers de 4 bits) :
1.
On souhaite décrémenter le nombre 1001 0100
(Dans notre manière de stocker les "BigInteger", on aura un tableau avec 0100 dans la première case et 1001 dans la seconde.)
On commence par décrémenter 0100.
On obtient 0011.
On se pose la question : 0011 < 0100 ? Oui, la décrémentation est terminée
=> 1001 0100 - 1 = 1001 0011
2.
On souhaite décrémenter le nombre 1100 0000
On commence par décrémenter 0000.
On obtient 1111 (si tu n'en est pas convaincu, exécute à la main l'algorithme bit à bit que je t'avais indiqué).
On se pose la question : 1111 < 0000 ? Non !
On décrémente alors 1100.
On obtient 1011.
On se pose la question : 1011 < 1100 ? Oui, la décrémentation est terminé
=> 1100 000 - 1 = 1011 1111
Tu n'as plus qu'à imaginer que ces groupes de 4 bits sont des groupes de 32 bits pour retomber sur ton cas concret.
T'as plus qu'à soumettre la division sur le forum pour montrer que t'as tout compris :-D
Petite note : pour extraire les bits d'un entiers, on dispose d'opérateurs :
>> permet de décaler les bits vers la droite
<< permet de décaler les bits vers la gauche
& réalise un "et" binaire
| réalise un "ou" binaire
^ réalise un "ou exclusif"
Du coup, pour extraire le iè bit (noté b) d'un nombre entier (noté n), on procède ainsi :
b = (n >> i) & 1
Pourquoi ? On décale tous les bits de n de i rangs vers la droite. Du coup, le ième bit se retrouve en première position (pour rappel les bits sont numérotés à partir de zéro). Ensuite, on fait un "et binaire" avec 1 ce qui permet d'effacer tous les bits (càd les mettre à zéro) sauf le premier. Le résultat est qu'on a un entier qui vaut 1 si le ième bit était à 1 et 0, s'il était à zéro.
Dans mon esprit, quand l'ordinateur fait des calculs, il n'y a jamais de prise en compte de la base (parfois de la base 2 mais c'est assez rare). Le problème c'est que le vocabulaire est assez trompeur. Lorsqu'on parle de chiffre, on associe généralement cela à la base 10 (les chiffres va de 0 à 9). En base 2, on parlera plutôt de bits.
Dans la base 10, on parlera d'unités, dizaines, centaines, milliers, etc. En base 2, on a moins de vocabulaire. Alors on parle de bit de poids faible, de poids fort... c'est pas toujours plus clair alors on mélange les notations.
Bref, tout ça pour dire que ça ne simplifie pas les explications :-)
Pour éclaircir l'algo que je t'ai donné, le voilà retouché pour te montrer qu'on parle toujours de "BigInteger" (toujours sur 64 bits pour simplifier les écriture) :
uint[] Multiplier(uint[] a, uint[] b)
{
if (IsZero(a) || IsZero(b))
return new uint[] { 0x0, 0x0 };
uint[] resultat = new uint[] { 0x0, 0x0 };
while (!IsZero(b))
{
resultat = Addition(resultat, a); // On reprend la méthode Addition qu'on avait écrite
b = Decrement(b);
}
return resultat;
}
// Renvoie true si le nombre passé en paramètre est égal à zéro
bool IsZero(uint[] n)
{
if (n[0] == 0 && n[1] == 0) // Vérifie que tous les éléments du tableau sont à zéro
return true;
else
return false;
// Tu peux aussi condenser tout ça en une seule ligne :
// return (n[0] == 0 && n[1] == 0);
}
uint[] Decrement(uint[] n)
{
// On fait une copie du nombre passé en paramètre
// parce qu'ici, on ne souhaite pas que n soit modifié par
// les calculs (c'est un choix, rien de plus!)
uint[] result = new uint[] { n[0], n[1] };
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] < n[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;
}
bon bah... du coup je t'ai tout programmé :-p
Je souhaite que ça t'aide à mieux comprendre.
Sache que l'algo de décrémentation que je t'ai noté dans mon précédent post était un peu tiré par les cheveux (bah vi... j'ai pas réfléchi !). Il t'obligeait à extraire chaque bit de chaque entier... C'est un peu lourd (mais possible). Si tu regardes bien, l'algo que je t'ai mis là fait exactement la même chose mais directement sur un entier (donc un paquet de 32 bits).
Enfin, pour illustrer la décrémentation, voici deux exemples (les nombres sont écrits en binaires et on imagine avoir créé un "BigInteger" de deux entiers de 4 bits) :
1.
On souhaite décrémenter le nombre 1001 0100
(Dans notre manière de stocker les "BigInteger", on aura un tableau avec 0100 dans la première case et 1001 dans la seconde.)
On commence par décrémenter 0100.
On obtient 0011.
On se pose la question : 0011 < 0100 ? Oui, la décrémentation est terminée
=> 1001 0100 - 1 = 1001 0011
2.
On souhaite décrémenter le nombre 1100 0000
On commence par décrémenter 0000.
On obtient 1111 (si tu n'en est pas convaincu, exécute à la main l'algorithme bit à bit que je t'avais indiqué).
On se pose la question : 1111 < 0000 ? Non !
On décrémente alors 1100.
On obtient 1011.
On se pose la question : 1011 < 1100 ? Oui, la décrémentation est terminé
=> 1100 000 - 1 = 1011 1111
Tu n'as plus qu'à imaginer que ces groupes de 4 bits sont des groupes de 32 bits pour retomber sur ton cas concret.
T'as plus qu'à soumettre la division sur le forum pour montrer que t'as tout compris :-D
Petite note : pour extraire les bits d'un entiers, on dispose d'opérateurs :
>> permet de décaler les bits vers la droite
<< permet de décaler les bits vers la gauche
& réalise un "et" binaire
| réalise un "ou" binaire
^ réalise un "ou exclusif"
Du coup, pour extraire le iè bit (noté b) d'un nombre entier (noté n), on procède ainsi :
b = (n >> i) & 1
Pourquoi ? On décale tous les bits de n de i rangs vers la droite. Du coup, le ième bit se retrouve en première position (pour rappel les bits sont numérotés à partir de zéro). Ensuite, on fait un "et binaire" avec 1 ce qui permet d'effacer tous les bits (càd les mettre à zéro) sauf le premier. Le résultat est qu'on a un entier qui vaut 1 si le ième bit était à 1 et 0, s'il était à zéro.
cs_niky
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
21 oct. 2007 à 21:30
21 oct. 2007 à 21:30
Quelques remarques...
- Dans decrement :
remplace la ligne "for (int i = 0; i < 2; i++)"
par "for (int i = 0; i < longa; i++)"
- Dans sup :
J'ai peut être mal compris ce que tu fais mais il me semble que ton calcul donne n'importe quoi :-)
Prenons la boucle suivante...
for (int i = 0; i < longa; i++)
{
if (a[i] > b[i])
{
sup = true;
break;
}
}
... et imaginons que nous traitions les chiffres d'un nombre décimal (c'est plus simple à comprendre et parfaitement transposable à ton cas). Faisons sup(159, 357). Le résultat doit être faux puisque 159 < 357.
Dans la représentation des grands nombres, les chiffres de poids faibles sont en début de tableau. Donc on a à comparer [9, 5, 1] et [7, 5, 3]. Si tu utilises ta boucles, tu vas te rendre compte que quand i = 0, tu fais 9 > 7 => réponse "oui". Donc 159 > 357.
La solution est de changer le sens de la boucle.
for (int i = longa - 1; i >= 0; i--)
// le reste est identique
- Toujours dans sup :
Le fait de considérer que si longa > longb alors a > b est un sacré raccourci. Si les toutes les cases de a sont remplies de zéro, et que b est différent de zéro alors a peut être aussi long que tu veux a restera inférieur à b.
Mais cela peut rester un choix donc j'imagine que tu sais ce que tu fais.
- Dans la soustraction, pourquoi calcules-tu "trop" si tu ne t'en sers pas par la suite ?
Je n'ai pas totalement compris ton algorithme de soustraction mais je vais t'en proposer un autre très utilisé. Il se base sur le complément à 2 des nombres binaires.
Jusque là, tu as implémenté de quoi travailler avec des nombres entiers positifs. Les machines peuvent aussi traiter des nombres négatifs. Pour cela, le bit de poids le plus élevé sert à coder le signe. On met 0 pour les positifs et 1 pour les négatifs.
On parle de complément à 2 parce que pour retrouver la valeur absolue d'un nombre négatif, on inverse tous ses bits (complémentarité) et on ajoute 1.
L'opération est exactement la même pour faire passer un nombre positif en nombre négatif.
Tu te demandes peut-être pouquoi je te parles de ça. Prenons notre soustraction. Tu veux faire l'opération :
resultat = a - b
Or, resultat = a + (-b)
Je t'ai dit que (-b) = (~b) + 1.
Le ~ est utilisé pour signifier que les bits de b sont inversés. Ca se réalise comme ceci est C# :
uint[] Inverse(uint[] a)
{
uint[] res = new uint[a.Length];
for (int i = 0 ; i < a.Length; i++)
res[i] = ~a[i];
return res;
}
Tu disposes déjà de l'incrémentation (enfin je crois... sinon c'est vraiment pas dure à faire) et de l'addition. C'est ainsi que soustraction s'écrit comme ça :
uint[] Soustraction(uint[] a, uint[] b)
{
if (a.Length != b.Length)
throw new Exception("a et b doivent posséder le même nombre de bits");
uint[] bneg = Increment(Inverse(b));
uint[] res = Addition(a, b);
return res;
}
Pour afficher les zéros des nombres tu peux faire ça :
uint[] n = ...; // Nombre à afficher
string affiche = ""; // Chaîne contenant la représentation du nombre
for (int i = n.Length - 1; n >= 0; i--)
{
affiche += n[i].ToString("0000"); // Force ToString à mettre le nombre sur au moins 4 chiffres
}
Bien évidemment, tu auras une représentation décimale de chaque morceau mais leur concaténation ne donne pas la représentation décimale du nombre complet.
J'espère n'avoir rien oublié... si j'ai pas été clair sur certains points, n'hésites pas à me rappeler à l'ordre :-)
- Dans decrement :
remplace la ligne "for (int i = 0; i < 2; i++)"
par "for (int i = 0; i < longa; i++)"
- Dans sup :
J'ai peut être mal compris ce que tu fais mais il me semble que ton calcul donne n'importe quoi :-)
Prenons la boucle suivante...
for (int i = 0; i < longa; i++)
{
if (a[i] > b[i])
{
sup = true;
break;
}
}
... et imaginons que nous traitions les chiffres d'un nombre décimal (c'est plus simple à comprendre et parfaitement transposable à ton cas). Faisons sup(159, 357). Le résultat doit être faux puisque 159 < 357.
Dans la représentation des grands nombres, les chiffres de poids faibles sont en début de tableau. Donc on a à comparer [9, 5, 1] et [7, 5, 3]. Si tu utilises ta boucles, tu vas te rendre compte que quand i = 0, tu fais 9 > 7 => réponse "oui". Donc 159 > 357.
La solution est de changer le sens de la boucle.
for (int i = longa - 1; i >= 0; i--)
// le reste est identique
- Toujours dans sup :
Le fait de considérer que si longa > longb alors a > b est un sacré raccourci. Si les toutes les cases de a sont remplies de zéro, et que b est différent de zéro alors a peut être aussi long que tu veux a restera inférieur à b.
Mais cela peut rester un choix donc j'imagine que tu sais ce que tu fais.
- Dans la soustraction, pourquoi calcules-tu "trop" si tu ne t'en sers pas par la suite ?
Je n'ai pas totalement compris ton algorithme de soustraction mais je vais t'en proposer un autre très utilisé. Il se base sur le complément à 2 des nombres binaires.
Jusque là, tu as implémenté de quoi travailler avec des nombres entiers positifs. Les machines peuvent aussi traiter des nombres négatifs. Pour cela, le bit de poids le plus élevé sert à coder le signe. On met 0 pour les positifs et 1 pour les négatifs.
On parle de complément à 2 parce que pour retrouver la valeur absolue d'un nombre négatif, on inverse tous ses bits (complémentarité) et on ajoute 1.
L'opération est exactement la même pour faire passer un nombre positif en nombre négatif.
Tu te demandes peut-être pouquoi je te parles de ça. Prenons notre soustraction. Tu veux faire l'opération :
resultat = a - b
Or, resultat = a + (-b)
Je t'ai dit que (-b) = (~b) + 1.
Le ~ est utilisé pour signifier que les bits de b sont inversés. Ca se réalise comme ceci est C# :
uint[] Inverse(uint[] a)
{
uint[] res = new uint[a.Length];
for (int i = 0 ; i < a.Length; i++)
res[i] = ~a[i];
return res;
}
Tu disposes déjà de l'incrémentation (enfin je crois... sinon c'est vraiment pas dure à faire) et de l'addition. C'est ainsi que soustraction s'écrit comme ça :
uint[] Soustraction(uint[] a, uint[] b)
{
if (a.Length != b.Length)
throw new Exception("a et b doivent posséder le même nombre de bits");
uint[] bneg = Increment(Inverse(b));
uint[] res = Addition(a, b);
return res;
}
Pour afficher les zéros des nombres tu peux faire ça :
uint[] n = ...; // Nombre à afficher
string affiche = ""; // Chaîne contenant la représentation du nombre
for (int i = n.Length - 1; n >= 0; i--)
{
affiche += n[i].ToString("0000"); // Force ToString à mettre le nombre sur au moins 4 chiffres
}
Bien évidemment, tu auras une représentation décimale de chaque morceau mais leur concaténation ne donne pas la représentation décimale du nombre complet.
J'espère n'avoir rien oublié... si j'ai pas été clair sur certains points, n'hésites pas à me rappeler à l'ordre :-)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
24 oct. 2007 à 17:57
24 oct. 2007 à 17:57
Bonjour,
Alors j'ai essayer l'algo de division. Cette algo donne le quotient de la division euclidienne.
Mais tout d'abord j'ai modifié plusieurs algo et je voulais savoir ce que tu en pensais ...
Comparaison:
bool sup(uint[] a, uint[] b)
{
bool sup = false;
if (a.Length != b.Length)
throw new Exception("a et b doivent posséder le même nombre de bits");
for (int i = (a.Length-1) ; i>=0; i--)
{
if (a[i] > b[i])
{
sup = true;
}
}
return sup;
}
Addition:
uint[] Addition(uint[] a, uint[] b)
{
bool carry = false; // indique s'il y a une retenue
//On prend en compte le fait que l'addition puisse génerer un nombre
//plus important (en taille de tableau necessaire) que a ou b.
//Il faut recreer un cellule suplementaire au tableau de resultat.
//Afin de pouvoir effectuer correctement les calculs dans les boucles
//on crée les images de a et b avec une cellule supplémentaire ....
int taille; if (a.Length > b.Length) { taille a.Length + 1; } else { taille b.Length + 1; }
uint[] result = new uint[taille];
uint[] a2 = new uint[taille];
uint[] b2 = new uint[taille];
a2[taille - 1] = 0; //on initialise la cellule supplémentaire
b2[taille - 1] = 0; // de a2 et b2 à 0
// on copie a et b dans a2 et b2.
for (int j = 0; j < (taille-1); j++)
{
a2[j] = a[j];
b2[j] = b[j];
}
for (uint i = 0; i < taille; i++)
{
result[i] += a2[i] + b2[i];
/*
Incrémente encore le résultat de 1 s'il y a une retenu
Comme on est en base 2, la retenue est soit de zéro, soit de 1
*/
if (carry)
result[i]++;
/*
On calcul s'il y a une retenue pour le tour suivant
C'est le cas si le résultat de l'addition est plus petit que a (ou b)
En effet, cela signifie que l'addition a provoqué un dépassement de capacité
pour le processeur et qu'il a du tronqué un bit du nombre.
*/
carry = (result[i] < a2[i]);
}
/*
ATTENTION ! Si à ce stage carry est à true, cela signifie que l'addition a
provoquée un dépassement de capacité (il aurait fallu faire l'addition sur au moins
65 bits parce que a et b étaient trop grand pour que a+b tiennent sur
64 bits).
*/
//on teste si la cellule supplémentaire est égale à 0, dans ce cas on revient à
//un tableau avec la taille de a (pour simplifier les caluls par
//la suite car souvent on met en condition que les tableaux soit de même taille)
//Et on renvoi le tableau correspondant au resultat.
if (result[a.Length] == 0)
{
uint[] res = new uint[a.Length];
for (int j = 0; j < a.Length; j++)
{
res[j] = result[j];
}
return res;
}
else
{
return result;
}
}
Soustraction
uint[] Soustraction(uint[] a, uint[] b)
{
if (a.Length != b.Length)
throw new Exception("a et b doivent posséder le même nombre de bits");
uint[] bneg = Increment(Inverse(b));
uint[] res = Addition(a, bneg); // je n'ai modifié que cette ligne car dans ton code c'était uint[] res = Addition(a, b);
return res;
}
Incrémente:
uint[] Increment(uint[] a)
{
// On fait une copie du nombre passé en paramètre
// parce qu'ici il est possible que la taille du
// tableau de résultat soit plus grande que celle
// de a (si a est au max de ces capacités).
uint[] result = new uint[a.Length+1];
for (int j = 0; j < a.Length; j++)
{
result[j] = a[j];
}
for (int i = 0; i < a.Length+1; i++)
{
result[i]++;
/* Si la décrémentation a généré un nombre plus petit que
l'original, alors c'est bon...
ou alors si la taille du tableau de resultat est plus grande
que i cela veut dire que a était au max de ces capacité et
* qu'il a fallut increment jusque dans une nouvelle cellule.
*/
if (i == a.Length+1 || result[i] > a[i])
break;
/* Sinon, cela signifie qu'on a fait max + 1, ce qui (sur des entiers positifs)
provoque un dépassement de capacité et nous renvoie quelque chose comme
????? dans ce cas, on continue de faire la décrémentation sur les
bits de poids plus forts
*/
}
//on teste si la cellule supplémentaire est égale à 0, dans ce cas on revient à
//un tableau avec la taille de a (pour simplifier les caluls par
//la suite car souvent on met en condition que les tableaux soit de même taille)
//Et on renvoi le tableau correspondant au resultat.
if (result[a.Length] == 0)
{
uint[] res = new uint[a.Length];
for (int j = 0; j < a.Length; j++)
{
res[j] = result[j];
}
return res;
}
else
{
return result;
}
}
Iszero:
bool IsZero(uint[] a)
{
bool zero = true;
for (int i = 0; i < a.Length; i++)
{
if (a[i] != 0)
{
zero = false;
break;
}
}
return zero;
}
Et voici la division:
uint[] Diviser(uint[] a, uint[] b)
{
// On créer un compteur.
uint[] count = new uint[a.Length];
// On initialise count à 0.
for (int j = 0; j < a.Length; j++)
{
count[j] = 0;
}
if (!IsZero(b))
{
// On fait une copie du nombre passé en paramètre
// parce qu'ici, on ne souhaite pas que n soit modifié par
// les calculs.
uint[] resultat = new uint[a.Length];
for (int j = 0; j < a.Length; j++)
{
resultat[j] = a[j];
}
//On creer une boucle sans fin où l'on soustrait b à a
//autant de fois que possible avant que le resultat
//soit inférieur à b (principe de la division euclidienne
//[ici de a par b] avec le reste [ici resultat]).
//A chaque fois on increment count
for (; ; )
{
if ( sup(b,resultat))
break;
Increment(count);
resultat = Soustraction(resultat, b);
}
//on returne count, quotient de cette division.
return count;
}
else
{
return count;
}
}
Alors je voulais avoir ton avis sur ces fonctions.
Les modifs:
- pour comparaison: je l'ais refaite.
- pour addition: juste le fait de prendre en compte que le resultat peut necessité un tableau de taille supérieur.
- pour incrémentation: je l'ais créer mais bon c'etait pas trop dificile ...
- pour soustraction: j'ai écrit à coté.
- pour Iszero: je l'ai généralisée.
- pour Diviser; je l'ait créer.
Autrement, je me demandais si plutot que de tester si les tailles des tableaux sont égales et d'afficher une exceptions si ce n'est pas le cas, ca ne serait pas mieux de faire une fonction qui le test et si la taille est différente, ajuste les tableaux en ajoutant des cellules égale à zero pour que les tableaux deviennent de taille identique.
Cordialement,
elephant13.
Alors j'ai essayer l'algo de division. Cette algo donne le quotient de la division euclidienne.
Mais tout d'abord j'ai modifié plusieurs algo et je voulais savoir ce que tu en pensais ...
Comparaison:
bool sup(uint[] a, uint[] b)
{
bool sup = false;
if (a.Length != b.Length)
throw new Exception("a et b doivent posséder le même nombre de bits");
for (int i = (a.Length-1) ; i>=0; i--)
{
if (a[i] > b[i])
{
sup = true;
}
}
return sup;
}
Addition:
uint[] Addition(uint[] a, uint[] b)
{
bool carry = false; // indique s'il y a une retenue
//On prend en compte le fait que l'addition puisse génerer un nombre
//plus important (en taille de tableau necessaire) que a ou b.
//Il faut recreer un cellule suplementaire au tableau de resultat.
//Afin de pouvoir effectuer correctement les calculs dans les boucles
//on crée les images de a et b avec une cellule supplémentaire ....
int taille; if (a.Length > b.Length) { taille a.Length + 1; } else { taille b.Length + 1; }
uint[] result = new uint[taille];
uint[] a2 = new uint[taille];
uint[] b2 = new uint[taille];
a2[taille - 1] = 0; //on initialise la cellule supplémentaire
b2[taille - 1] = 0; // de a2 et b2 à 0
// on copie a et b dans a2 et b2.
for (int j = 0; j < (taille-1); j++)
{
a2[j] = a[j];
b2[j] = b[j];
}
for (uint i = 0; i < taille; i++)
{
result[i] += a2[i] + b2[i];
/*
Incrémente encore le résultat de 1 s'il y a une retenu
Comme on est en base 2, la retenue est soit de zéro, soit de 1
*/
if (carry)
result[i]++;
/*
On calcul s'il y a une retenue pour le tour suivant
C'est le cas si le résultat de l'addition est plus petit que a (ou b)
En effet, cela signifie que l'addition a provoqué un dépassement de capacité
pour le processeur et qu'il a du tronqué un bit du nombre.
*/
carry = (result[i] < a2[i]);
}
/*
ATTENTION ! Si à ce stage carry est à true, cela signifie que l'addition a
provoquée un dépassement de capacité (il aurait fallu faire l'addition sur au moins
65 bits parce que a et b étaient trop grand pour que a+b tiennent sur
64 bits).
*/
//on teste si la cellule supplémentaire est égale à 0, dans ce cas on revient à
//un tableau avec la taille de a (pour simplifier les caluls par
//la suite car souvent on met en condition que les tableaux soit de même taille)
//Et on renvoi le tableau correspondant au resultat.
if (result[a.Length] == 0)
{
uint[] res = new uint[a.Length];
for (int j = 0; j < a.Length; j++)
{
res[j] = result[j];
}
return res;
}
else
{
return result;
}
}
Soustraction
uint[] Soustraction(uint[] a, uint[] b)
{
if (a.Length != b.Length)
throw new Exception("a et b doivent posséder le même nombre de bits");
uint[] bneg = Increment(Inverse(b));
uint[] res = Addition(a, bneg); // je n'ai modifié que cette ligne car dans ton code c'était uint[] res = Addition(a, b);
return res;
}
Incrémente:
uint[] Increment(uint[] a)
{
// On fait une copie du nombre passé en paramètre
// parce qu'ici il est possible que la taille du
// tableau de résultat soit plus grande que celle
// de a (si a est au max de ces capacités).
uint[] result = new uint[a.Length+1];
for (int j = 0; j < a.Length; j++)
{
result[j] = a[j];
}
for (int i = 0; i < a.Length+1; i++)
{
result[i]++;
/* Si la décrémentation a généré un nombre plus petit que
l'original, alors c'est bon...
ou alors si la taille du tableau de resultat est plus grande
que i cela veut dire que a était au max de ces capacité et
* qu'il a fallut increment jusque dans une nouvelle cellule.
*/
if (i == a.Length+1 || result[i] > a[i])
break;
/* Sinon, cela signifie qu'on a fait max + 1, ce qui (sur des entiers positifs)
provoque un dépassement de capacité et nous renvoie quelque chose comme
????? dans ce cas, on continue de faire la décrémentation sur les
bits de poids plus forts
*/
}
//on teste si la cellule supplémentaire est égale à 0, dans ce cas on revient à
//un tableau avec la taille de a (pour simplifier les caluls par
//la suite car souvent on met en condition que les tableaux soit de même taille)
//Et on renvoi le tableau correspondant au resultat.
if (result[a.Length] == 0)
{
uint[] res = new uint[a.Length];
for (int j = 0; j < a.Length; j++)
{
res[j] = result[j];
}
return res;
}
else
{
return result;
}
}
Iszero:
bool IsZero(uint[] a)
{
bool zero = true;
for (int i = 0; i < a.Length; i++)
{
if (a[i] != 0)
{
zero = false;
break;
}
}
return zero;
}
Et voici la division:
uint[] Diviser(uint[] a, uint[] b)
{
// On créer un compteur.
uint[] count = new uint[a.Length];
// On initialise count à 0.
for (int j = 0; j < a.Length; j++)
{
count[j] = 0;
}
if (!IsZero(b))
{
// On fait une copie du nombre passé en paramètre
// parce qu'ici, on ne souhaite pas que n soit modifié par
// les calculs.
uint[] resultat = new uint[a.Length];
for (int j = 0; j < a.Length; j++)
{
resultat[j] = a[j];
}
//On creer une boucle sans fin où l'on soustrait b à a
//autant de fois que possible avant que le resultat
//soit inférieur à b (principe de la division euclidienne
//[ici de a par b] avec le reste [ici resultat]).
//A chaque fois on increment count
for (; ; )
{
if ( sup(b,resultat))
break;
Increment(count);
resultat = Soustraction(resultat, b);
}
//on returne count, quotient de cette division.
return count;
}
else
{
return count;
}
}
Alors je voulais avoir ton avis sur ces fonctions.
Les modifs:
- pour comparaison: je l'ais refaite.
- pour addition: juste le fait de prendre en compte que le resultat peut necessité un tableau de taille supérieur.
- pour incrémentation: je l'ais créer mais bon c'etait pas trop dificile ...
- pour soustraction: j'ai écrit à coté.
- pour Iszero: je l'ai généralisée.
- pour Diviser; je l'ait créer.
Autrement, je me demandais si plutot que de tester si les tailles des tableaux sont égales et d'afficher une exceptions si ce n'est pas le cas, ca ne serait pas mieux de faire une fonction qui le test et si la taille est différente, ajuste les tableaux en ajoutant des cellules égale à zero pour que les tableaux deviennent de taille identique.
Cordialement,
elephant13.
cs_niky
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
24 oct. 2007 à 19:20
24 oct. 2007 à 19:20
Hop, c'est parti :-)
Pour la comparaison, c'est mieux mais tu peux faire encore mieux:
1) Tu supprimes la variable sup.
2) A la place de "sup = true", tu mets "return true" comme ça, tu arrêtes la boucle immédiatement (puisque sup ne pouvait de toute façon pas revenir à false)
3) A la place de "return sup", tu mets "return false".
Tu gagneras quelques précieux instants si tu en viens à traiter des grands nombres.
Pour l'addition, l'idée est très bonne. Toutefois, je ne l'aurai pas écrit comme ça. En effet, tu commences par prévoir un tableau plus grand pour éventuellement le réduire à la fin.
Tu peux faire plus simple :
1) Reprend la version précédente de l'addition.
2) Avant de faire "return ..." du résultat, tu vérifies si carry vaut true. Si tel est le cas, tu créés une copie du tableau résultat avec une case de plus. Dans la dernière case, tu y place la valeur 1 (<= la retenue).
Pour la soustraction, tout à fait d'accord... mea culpa :-)
Pour l'incrémentation, même commentaire que pour l'addition.
Pour IsZero, même commentaire que pour la fonction sup. Néanmoins, t'as pensé à mettre un break après "zero = false" donc ma remarque n'est pas vraiment justifiée ici.
Pour la division, je n'ai pas grand chose à dire : j'aurai fait pareil.
Ton algo se base sur la soustraction successive de b... et y'a pas vraiment mieux :-D. Tu peux toutefois jeter un oeil sur http://www2.ift.ulaval.ca/~marchand/ift17583/Support/Arithm.html. Il est proposé une adaptation de la division euclidienne aux particularités de la base 2.
Ton choix de renvoyer zéro quand on fait une division par zéro est un peu atypique :-) Généralement, on renvoie soit l'infini (applicable uniquement aux nombres flottants), soit une exception.
Sinon, l'instruction "for (;;)" n'est pas très chouette. A titre personnel, je préfère "while (true)"... mais là, ce sont des considérations purement esthétiques :-p
Enfin pour ta dernière remarque sur l'ajustement des tableaux par une fonction, elle est très judicieuse et c'est effectivement ce que tu devrais faire.
Cordialement.
Pour la comparaison, c'est mieux mais tu peux faire encore mieux:
1) Tu supprimes la variable sup.
2) A la place de "sup = true", tu mets "return true" comme ça, tu arrêtes la boucle immédiatement (puisque sup ne pouvait de toute façon pas revenir à false)
3) A la place de "return sup", tu mets "return false".
Tu gagneras quelques précieux instants si tu en viens à traiter des grands nombres.
Pour l'addition, l'idée est très bonne. Toutefois, je ne l'aurai pas écrit comme ça. En effet, tu commences par prévoir un tableau plus grand pour éventuellement le réduire à la fin.
Tu peux faire plus simple :
1) Reprend la version précédente de l'addition.
2) Avant de faire "return ..." du résultat, tu vérifies si carry vaut true. Si tel est le cas, tu créés une copie du tableau résultat avec une case de plus. Dans la dernière case, tu y place la valeur 1 (<= la retenue).
Pour la soustraction, tout à fait d'accord... mea culpa :-)
Pour l'incrémentation, même commentaire que pour l'addition.
Pour IsZero, même commentaire que pour la fonction sup. Néanmoins, t'as pensé à mettre un break après "zero = false" donc ma remarque n'est pas vraiment justifiée ici.
Pour la division, je n'ai pas grand chose à dire : j'aurai fait pareil.
Ton algo se base sur la soustraction successive de b... et y'a pas vraiment mieux :-D. Tu peux toutefois jeter un oeil sur http://www2.ift.ulaval.ca/~marchand/ift17583/Support/Arithm.html. Il est proposé une adaptation de la division euclidienne aux particularités de la base 2.
Ton choix de renvoyer zéro quand on fait une division par zéro est un peu atypique :-) Généralement, on renvoie soit l'infini (applicable uniquement aux nombres flottants), soit une exception.
Sinon, l'instruction "for (;;)" n'est pas très chouette. A titre personnel, je préfère "while (true)"... mais là, ce sont des considérations purement esthétiques :-p
Enfin pour ta dernière remarque sur l'ajustement des tableaux par une fonction, elle est très judicieuse et c'est effectivement ce que tu devrais faire.
Cordialement.
cs_coq
Messages postés
6349
Date d'inscription
samedi 1 juin 2002
Statut
Membre
Dernière intervention
2 août 2014
101
6 oct. 2007 à 23:32
6 oct. 2007 à 23:32
Salut,
Au passage, juste pour info, .NET 3.5 bénificiera d'un type BigInteger : http://blogs.msdn.com/bclteam/archive/2007/01/16/introducing-system-numeric-biginteger-inbar-gazit.aspx
/*
coq
MVP Visual C#
CoqBlog
*/
Au passage, juste pour info, .NET 3.5 bénificiera d'un type BigInteger : http://blogs.msdn.com/bclteam/archive/2007/01/16/introducing-system-numeric-biginteger-inbar-gazit.aspx
/*
coq
MVP Visual C#
CoqBlog
*/
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
7 oct. 2007 à 10:50
7 oct. 2007 à 10:50
Oki merci
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Membre
Dernière intervention
20 juin 2013
61
7 oct. 2007 à 10:55
7 oct. 2007 à 10:55
Merci pour l'info coq, c'est vrai que ça pouvait manquer dans certains cas
<hr />
-My Blog-
<hr />
-My Blog-
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
7 oct. 2007 à 15:50
7 oct. 2007 à 15:50
L'idée qui serait de stocker ces nombre par "paquet" dans un tableau me plait plutot bien.
Mais je sais pas trop comment on les "découpe en paquet" (de 10 chifres par ex)...
Mais je sais pas trop comment on les "découpe en paquet" (de 10 chifres par ex)...
cs_niky
Messages postés
168
Date d'inscription
jeudi 28 juin 2001
Statut
Membre
Dernière intervention
18 octobre 2008
7
7 oct. 2007 à 17:05
7 oct. 2007 à 17:05
Tu ne pourras pas faire tes calculs en base 10 puisque ce n'est pas comme cela qu'un ordinateur fonctionne.
Pour commencer, ne voit plus tes nombres comme une succession de chiffres (terme couramment employé pour la base décimale) mais comme une suite de bits (spécifiques à la base 2).
Un entier (int) en C# est codé sur 32 bits, c'est à dire un peu plus de 9 chiffres (= (32 * ln 2) / ln 10) en base 10. Sa plage de valeurs s'étend jusqu'à -2^31 dans les négatifs, et jusqu'à 2^31-1 dans les positifs. Si tu oublies la notion de signe (uint), tu peux coder de 0 à 2^32-1 avec un entier de 32 bits.
Maintenant, si tu veux manipuler des nombres de 64 bits, tu divises ces nombres en deux paquets de 32 bits. Pour des nombres de 128 bits, tu feras 4 paquets de 32 bits. Cela implique d'implémenter les opérations mathématiques sur les règles du calcul binaire. Pour cela, les opérateurs binaires de C# te seront utiles : &, |, ^, <<, >>, ~
J'ai moi-même réalisé une version basique de cela il y a quelques
années en C++ :
http://tuxy2885.free.fr/index.php?cat=labo&id=integer
Une fois que tout cela est fait, tu pourras écrire une fonction qui va te transformer ton nombre binaire en une chaîne de caractères qui représentera ton nombre dans la base de ton choix (binaire, octale, décimale, hexadécimale, etc.).
J'ignore ton niveau en maths mais pour calculer sur des nombres aussi grands, il te faut de bonnes connaissances en conversion de bases, logique/algèbre de Boole et calcul sur des nombres binaires.
En espérant t'avoir aidé.
Pour commencer, ne voit plus tes nombres comme une succession de chiffres (terme couramment employé pour la base décimale) mais comme une suite de bits (spécifiques à la base 2).
Un entier (int) en C# est codé sur 32 bits, c'est à dire un peu plus de 9 chiffres (= (32 * ln 2) / ln 10) en base 10. Sa plage de valeurs s'étend jusqu'à -2^31 dans les négatifs, et jusqu'à 2^31-1 dans les positifs. Si tu oublies la notion de signe (uint), tu peux coder de 0 à 2^32-1 avec un entier de 32 bits.
Maintenant, si tu veux manipuler des nombres de 64 bits, tu divises ces nombres en deux paquets de 32 bits. Pour des nombres de 128 bits, tu feras 4 paquets de 32 bits. Cela implique d'implémenter les opérations mathématiques sur les règles du calcul binaire. Pour cela, les opérateurs binaires de C# te seront utiles : &, |, ^, <<, >>, ~
J'ai moi-même réalisé une version basique de cela il y a quelques
années en C++ :
http://tuxy2885.free.fr/index.php?cat=labo&id=integer
Une fois que tout cela est fait, tu pourras écrire une fonction qui va te transformer ton nombre binaire en une chaîne de caractères qui représentera ton nombre dans la base de ton choix (binaire, octale, décimale, hexadécimale, etc.).
J'ignore ton niveau en maths mais pour calculer sur des nombres aussi grands, il te faut de bonnes connaissances en conversion de bases, logique/algèbre de Boole et calcul sur des nombres binaires.
En espérant t'avoir aidé.
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
7 oct. 2007 à 17:59
7 oct. 2007 à 17:59
Oulalalalalala.........
Alors mon niveau en math: bon niveau (19 de moyenne) mais je ne suis qu'en debut de TS (specialité maths).
J'ai oublier de preciser que pour les operations je compte me tenir au modulo pour l'instant du genre 183^1079 mod 5141. Peur-être que ca pourra plus t'eclaircir....
Donc je comptais faire des "paquets" elevé à une puissance de 10 par var du tableau puis faire les operation modulo variable par variable donc faire des operation sur des uint64.
Donc je croit que ca va pas vraiment avec ce que tu me dis auparavant ce qui me perd un peu dans mes idées.
De plus mon niveau en programmation est de debutant, c'est mon premier vrai programme. Donc pour les convertions en suite de bits je suis aussi un peu perdu.
Conclusion: Je suis un peu perdu mais je tiens à preciser que je comprend ce que tu me dis, c'est juste que je ne vois pas vraiment comment l'appliquer à mon problème.
Alors mon niveau en math: bon niveau (19 de moyenne) mais je ne suis qu'en debut de TS (specialité maths).
J'ai oublier de preciser que pour les operations je compte me tenir au modulo pour l'instant du genre 183^1079 mod 5141. Peur-être que ca pourra plus t'eclaircir....
Donc je comptais faire des "paquets" elevé à une puissance de 10 par var du tableau puis faire les operation modulo variable par variable donc faire des operation sur des uint64.
Donc je croit que ca va pas vraiment avec ce que tu me dis auparavant ce qui me perd un peu dans mes idées.
De plus mon niveau en programmation est de debutant, c'est mon premier vrai programme. Donc pour les convertions en suite de bits je suis aussi un peu perdu.
Conclusion: Je suis un peu perdu mais je tiens à preciser que je comprend ce que tu me dis, c'est juste que je ne vois pas vraiment comment l'appliquer à mon problème.
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
7 oct. 2007 à 21:13
7 oct. 2007 à 21:13
Ok merci beaucoup,
Je ferais des test demain, et j'essaierais de faire un autre algorythm que je posterais.
Mais tout de même quelque "questions":
- "ATTENTION ! Si à ce stage carry est à true, cela signifie que l'addition a
provoquée un dépassement de capacité (il aurait fallu faire l'addition sur au moins
65 bits parce que a et b étaient trop grand pour que a+b tiennent sur
64 bits)."
Ce que je comprend: Si carry est true, cela eut dire qu'il y a une retenue (65ème bit) et donc cela l'incrementera le tour suivant. Vrai?
- Mais imaginons que ca fasse une retenue à la derniere boucle, cela ne pourra pas implementer la suivante ou alors il faut le prevoir et toujours laisser un bit en plus dans le tableau...
- pour l'ecriture en base 16, je les "0x"... c'est spour indiquer que c'est en base16, non?
Et autrement en binaire ca donnerais pour le meme exmple:
uint[] a = new uint[] { 011010000010101000011001011111111, 0000000000000000111101011110010};
La flemme de faire le b... mais si j'ai pas perdu la main et bien compris ce que tu as dit ca doit être ca, non?
Je ferais des test demain, et j'essaierais de faire un autre algorythm que je posterais.
Mais tout de même quelque "questions":
- "ATTENTION ! Si à ce stage carry est à true, cela signifie que l'addition a
provoquée un dépassement de capacité (il aurait fallu faire l'addition sur au moins
65 bits parce que a et b étaient trop grand pour que a+b tiennent sur
64 bits)."
Ce que je comprend: Si carry est true, cela eut dire qu'il y a une retenue (65ème bit) et donc cela l'incrementera le tour suivant. Vrai?
- Mais imaginons que ca fasse une retenue à la derniere boucle, cela ne pourra pas implementer la suivante ou alors il faut le prevoir et toujours laisser un bit en plus dans le tableau...
- pour l'ecriture en base 16, je les "0x"... c'est spour indiquer que c'est en base16, non?
Et autrement en binaire ca donnerais pour le meme exmple:
uint[] a = new uint[] { 011010000010101000011001011111111, 0000000000000000111101011110010};
La flemme de faire le b... mais si j'ai pas perdu la main et bien compris ce que tu as dit ca doit être ca, non?
ShareVB
Messages postés
2676
Date d'inscription
vendredi 28 juin 2002
Statut
Membre
Dernière intervention
13 janvier 2016
26
8 oct. 2007 à 00:20
8 oct. 2007 à 00:20
salut,
voilà une classe qui pourrait t'intéresser : http://www.codeproject.com/csharp/biginteger.asp
pour ce qui est de l'algo d'exponentiation modulo N, tu peux appliquer une règle simple (algo square and multiply) pour accélérer le traitement : a^ b mod c
r = 1 //résultat
tant que b != 1
si b mod 2 = 1 alors
r = r * a mod c
b = b - 1
sinon
r = r * r mod c
b = b / 2
fin si
fin tant que
ShareVB
voilà une classe qui pourrait t'intéresser : http://www.codeproject.com/csharp/biginteger.asp
pour ce qui est de l'algo d'exponentiation modulo N, tu peux appliquer une règle simple (algo square and multiply) pour accélérer le traitement : a^ b mod c
r = 1 //résultat
tant que b != 1
si b mod 2 = 1 alors
r = r * a mod c
b = b - 1
sinon
r = r * r mod c
b = b / 2
fin si
fin tant que
ShareVB
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
8 oct. 2007 à 12:49
8 oct. 2007 à 12:49
Bonjour tout le monde,
Merci de l'info Share VB, je regarderais ton lien quand je serais chez moi.
Autrement les question posées sur la page précedente sont en faites résolues.
Merci de l'info Share VB, je regarderais ton lien quand je serais chez moi.
Autrement les question posées sur la page précedente sont en faites résolues.
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
8 oct. 2007 à 17:09
8 oct. 2007 à 17:09
voilà une classe qui pourrait t'intéresser : http://www.codeproject.com/csharp/biginteger.asp
Oui ca à l'air de ressembler fortement!!!!!!
Alors je vais essayer en utilisant la classe BigInteger mais ca ne m'empechera pas d'essayer de coder les autres algo comme entendu precedement. Je les posterais sur ce sujet.
Merci à tous
Oui ca à l'air de ressembler fortement!!!!!!
Alors je vais essayer en utilisant la classe BigInteger mais ca ne m'empechera pas d'essayer de coder les autres algo comme entendu precedement. Je les posterais sur ce sujet.
Merci à tous
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
8 oct. 2007 à 19:48
8 oct. 2007 à 19:48
Comprend pas 12^1079 je suis en overflow avec la classe BigInteger... Peut être je sais pas l'utiliser ce qui est fort probable mais je vais continuer dans ma lancer et faire les code "moi-même" en binaire en esperant pouvoir tout de même compter sur vous afin de resoudre des problèmes éventuels à venir.
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
9 oct. 2007 à 16:05
9 oct. 2007 à 16:05
Bon alors, je reflechi a la multiplication.
A la main c'est facil.... il suffit de multiplier bit par bit et d'additionner avec un decalage de puissance de 2... mais la quand on multiplie les "cellules" des tableaux, on multiplie des series de bits entre elles.... Et donc je vois pas bien encore comment on fait pour reperer les retenues......
A bientot.
A la main c'est facil.... il suffit de multiplier bit par bit et d'additionner avec un decalage de puissance de 2... mais la quand on multiplie les "cellules" des tableaux, on multiplie des series de bits entre elles.... Et donc je vois pas bien encore comment on fait pour reperer les retenues......
A bientot.
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
9 oct. 2007 à 18:57
9 oct. 2007 à 18:57
Désolé pour le double post .......
Autrement, j'ai posté le message precedent depuis le lycée à une récréation c'est pour ca que c'est un peu rapide...
Alors pour le moment je vois comme solution juste celle qui consisterais à sotcker que 16 bit par int[] et donc lorsqu'on les multiplierais, ca ferai 32bit au maximum (2^16*2^16=2^32), non?
Autrement si jamais vous passez sur le poste, une petite piste peut-être......
Autrement, j'ai posté le message precedent depuis le lycée à une récréation c'est pour ca que c'est un peu rapide...
Alors pour le moment je vois comme solution juste celle qui consisterais à sotcker que 16 bit par int[] et donc lorsqu'on les multiplierais, ca ferai 32bit au maximum (2^16*2^16=2^32), non?
Autrement si jamais vous passez sur le poste, une petite piste peut-être......
elephant13
Messages postés
23
Date d'inscription
mercredi 16 mars 2005
Statut
Membre
Dernière intervention
7 avril 2008
9 oct. 2007 à 19:21
9 oct. 2007 à 19:21
Pour le message precedent, je pensais aux int16 et int32 ....
Autrement une autre idée: si on decompose un des deux nombres en forme binaire dans un tableau, on doit pouvoir multiplier l'autre nombre bit par bit facilement et aditionner les resultats (bien sur avec un declage de puissance de 2), non?
Si quelqu'un pourrais me donner son avis sur mes idées, où en proposant de plus convaincantes, ca serait simpa de sa part.
PS: j'ai conscience de faire un peu la discussion à moi tout seul, mais des que je pense a un truc et que sur la papier ca à l'air de pouvoir être pas mal, je post ..... (c'est pour ca que des fois je met des trucs qu servent à rien mais bon..... notament le message de 16h.....)
Merci à tous et à bientot,
elephant13
Autrement une autre idée: si on decompose un des deux nombres en forme binaire dans un tableau, on doit pouvoir multiplier l'autre nombre bit par bit facilement et aditionner les resultats (bien sur avec un declage de puissance de 2), non?
Si quelqu'un pourrais me donner son avis sur mes idées, où en proposant de plus convaincantes, ca serait simpa de sa part.
PS: j'ai conscience de faire un peu la discussion à moi tout seul, mais des que je pense a un truc et que sur la papier ca à l'air de pouvoir être pas mal, je post ..... (c'est pour ca que des fois je met des trucs qu servent à rien mais bon..... notament le message de 16h.....)
Merci à tous et à bientot,
elephant13