Exponentiation binaire sur Biginterger [Résolu]

maitrejediyass 5 Messages postés mardi 14 décembre 2010Date d'inscription 22 avril 2012 Dernière intervention - 19 avril 2012 à 15:30 - Dernière réponse : maitrejediyass 5 Messages postés mardi 14 décembre 2010Date d'inscription 22 avril 2012 Dernière intervention
- 19 avril 2012 à 18:08
Bonjour,
je souhaite réaliser l'équivalent de la fonction modPow de la class Biginteger

voici la fonction d'exponentiation binaire que je cherche à reproduire mais pour des BigInteger

public static long modpow(long x, long exp, long mod) {

        {
            long result = 1;

            while (exp > 0) {
                if ((exp&1)>0) result = (result * x) % mod;
                exp >>= 1;
                x = (x * x) % mod;
            }

            return result;
        }
    }



et voici mon ébauche de fonction qui ne marche pas

    public static BigInteger modpower(BigInteger x, BigInteger exp, BigInteger mod) {

        {
            BigInteger result = new BigInteger("1");

            
            while (exp.compareTo(BigInteger.ZERO) > 0) {

                int i=0;   

                if (exp.testBit(i)== true) {
                    result = (result.multiply(x)).mod(mod) ;  
                    i++;
                }
                exp.shiftRight(1);

                x = (x.multiply(x)).mod(mod);
            }

            return result;
        }
    } 



Merci d'avance pour votre aide
Afficher la suite 

Votre réponse

7 réponses

Meilleure réponse
cs_jojolemariole 519 Messages postés mercredi 21 mars 2007Date d'inscription 19 décembre 2016 Dernière intervention - 19 avril 2012 à 17:43
3
Merci
J'oubliais
tu dois écrire
exp = exp.shiftRight(1)
car une instance BigInteger n'est pas modifiable (un peu comme les String)

Merci cs_jojolemariole 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 93 internautes ce mois-ci

Commenter la réponse de cs_jojolemariole
Meilleure réponse
cs_jojolemariole 519 Messages postés mercredi 21 mars 2007Date d'inscription 19 décembre 2016 Dernière intervention - 19 avril 2012 à 17:45
3
Merci
En fait, tu test pour la parité est bon. Je n'avais pas vu que tu l'initialisais dans la boucle.
Du coup je ne vois vraiment pas pourquoi tu le fais comme ça.
testBit(0) suffit

Merci cs_jojolemariole 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 93 internautes ce mois-ci

Commenter la réponse de cs_jojolemariole
cs_Julien39 6450 Messages postés mardi 8 mars 2005Date d'inscription 17 mai 2018 Dernière intervention - 19 avril 2012 à 17:05
0
Merci
Salut,

Pourquoi ta fonction ne marche pas ? Exception ? Résultat inattendu ?
Commenter la réponse de cs_Julien39
cs_Julien39 6450 Messages postés mardi 8 mars 2005Date d'inscription 17 mai 2018 Dernière intervention - 19 avril 2012 à 17:06
0
Merci
Sinon, tu as la fonction modPow de la classe BigInteger...
Commenter la réponse de cs_Julien39
maitrejediyass 5 Messages postés mardi 14 décembre 2010Date d'inscription 22 avril 2012 Dernière intervention - 19 avril 2012 à 17:33
0
Merci
Le but de l'exercice est de ne pas utilisé la fonction modPow.

en fait
exp.compareTo(BigInteger.ZERO)
est toujours égale à 1, bien que je fasse un décalage de bit avec la ligne
exp.shiftRight(1);
Commenter la réponse de maitrejediyass
cs_jojolemariole 519 Messages postés mercredi 21 mars 2007Date d'inscription 19 décembre 2016 Dernière intervention - 19 avril 2012 à 17:40
0
Merci
D'une part, la fonction modPow existe, optimisée (avec les restes chinois et tout le tintouin)
D'autre part, tu t'es fourvoyé sur la transcription de :
(exp&1)>0
qui n'est rien d'autre qu'un test de parité de l'exposant. Tu dois plutôt écrire :
testBit(0)

--> "== true" est inutile dans ton code
Commenter la réponse de cs_jojolemariole
maitrejediyass 5 Messages postés mardi 14 décembre 2010Date d'inscription 22 avril 2012 Dernière intervention - 19 avril 2012 à 18:08
0
Merci
Merci pour ton aide mon programme marche a merveille
Commenter la réponse de maitrejediyass

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.