Discussion :

[ahmed doua]

bonjour,

je suis debutant et je suis en train de faire un algo qui calcule l'exponatiation rapide mais je me bloque sur la conversion bin-déc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
a (e) mod n
[/list]

mais l'exposent e est en base 2 et je dois le convertir en base 10



merci en avance à tous

[j.p.mignot]

e est une serie de valeurs ai=0 ou 1 i=0..n
alors en base 10 e = Somme(i=0..n) ai * 2^i = Somme { ai <> 0 } 2^i

exemple
e=10010 => a0=a2=a3=0, a1=a4=1 => e = 2^1 + 2^4 = 2+16=18

[ahmed doua]

merci mais tu peut m'écrire cet algorithme en pseedo code stp :

[j.p.mignot]

string s = e // s est defini de 1 à n s[1] bit de poids fort s[n] bit de poids faible

value = 0
pour i= 1 à longueur(s) faire
{
value=value * 2
si s[i] ='1' alors value=value+1
}
sortir value

[ahmed doua]

merci encore mais je dois le faire sans utiliser le tableau

[j.p.mignot]

précisez!!!
pour le conversion base2->base10 il faut bien avoir quelquepart l'écriture en base 2 pour générer celle en base 10!

[Jedai]

Le tableau ? De quoi parles-tu ? Il est bien évident que si ta valeur est sous forme de string, tu ne peux pas la traduire en entier sans lire la string, c'est donc que ton problème n'est pas celui auquel nous pensons, ou que tu te trompes de tableau.

--
Jedaï

[ahmed doua]

salut
exponetiation rapide

je veux faire un prog en C qui calcule a^e mod n = (a mod n)^e mod n
mais e est en binaire et je dois le convertir en décimal et apres faire le reste d'operation mais je me bloque sur la conversion de e en décimal
et en classe on a pas encore vue le tableau pouvez vous faire cette conversion sans utiliser le tableau pour tout nombre binaire avec les boucles( tant que(condition) faire ou faire tant que (condition) ou repeter (nfois ) ...etc)


j'espère que comprenez l'expliquation

merci

[Jedai]

"e est en binaire" n'a pas de signification en soi... Le binaire est une représentation, un nombre est absolu, le fait qu'en interne l'ordinateur le représente en binaire en ternaire ou en base 60 n'a pas d'importance tant que tu fais des opérations classiques avec (multiplication, addition, division...). Maintenant on peut avoir une variable qui contient une représentation d'un nombre, dans ce cas cette variable est forcément un tableau (une string ou une séquence d'entier). Donc que veux tu dire par "e est en binaire" ?

--
Jedaï

[j.p.mignot]

cela ne répond pas à notre interrogation
>>> OU EST E ??? <<<
Doit-on le lire dans un fichier? Est-il entré bit à bit par le clavier? Est-ce 1 string qui provient d'ailleurs? Est-ce résultat d’une fonction ? …
Il n’est pas possible de transcoder e si on n’a pas le droit de le lire - acquérir d’une façon ou d’une autre !!!
le petit code proposé ci-dessu fait bien vos boucles et tests. Mais il faut bien tester sur l'entrée de E

[ahmed doua]

le prototype de la fonction est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int expoRapide (int a , int e , int n)

je crois que vous allez comprendre

[Hephaistos007]

C'est un peu bizarre, ta fonction reçoit en entrée un entier base 10 dont tu interprètes la valeur comme du binaire. Bon bref.

int e = 1101;

Si tu veux éviter d'utiliser un tableau, tu peux diviser successivement ce nombre par 10 jusqu'à ce que le quotient soit égale à 0. Tu prends tous les restes de haut en bas et tu obtiens chaque chiffre du nombre de départ mais en ordre inverse.

1101 | 10
--------------
1 | 110
0 | 11
1 | 1
1 | 0


Et là on a bien :
1*2^0 + 0*2^1 + 1*2^2 + 1*2^3 = 1 + 0 + 4 + 8 = 13 gagné !

[j.p.mignot]

Côté incertain de la fonction proposé tout à fait sur...

l'algorithme proposé est Vrai mais je ne conseille pas cela pour la raison suivante:
pout atteindre 13 ( cas de l'exemple ci-dessus ) on a du passer par 1101 en base 10! c'est à dire que dès que l'on interprète comme de la base 10 un chiffre en base 2 on diverge TRES vite .
Un integer 32 bits non signé est limité à 2^32 -1 = 4294967295. C'est à dire cette technique limite le nombre e à 1111111111 soit 1023 !!
avec un integer 64 bit on relaxe un peu le problème mais quelle perte de potenitel !!!

[Betatesteur]

bon, j'ai concocté ceci algo en utilisant la récursivité pour la méthode d'exponentiation rapide

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
fonction puissance(x,n: entier long) retourne entier long
 
    Si n=1 alors
        puissance <- x
    sinon
        si n mod 2=0 alors    //Si x est pair
            puissance <- puissance(x,n div 2) * puissance(x,n div 2)
        sinon
            puissance <- puissance(x,n div 2) * puissance(x,n div 2)* x
fin puissance