Exponentiation binaire sur Biginterger [Résolu]

Messages postés
5
Date d'inscription
mardi 14 décembre 2010
Statut
Membre
Dernière intervention
22 avril 2012
- - Dernière réponse : maitrejediyass
Messages postés
5
Date d'inscription
mardi 14 décembre 2010
Statut
Membre
Dernière intervention
22 avril 2012
- 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 

7 réponses

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

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 198 internautes nous ont dit merci ce mois-ci

Commenter la réponse de cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
21
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

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 198 internautes nous ont dit merci ce mois-ci

Commenter la réponse de cs_jojolemariole
Messages postés
6413
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
17 mai 2018
244
0
Merci
Salut,

Pourquoi ta fonction ne marche pas ? Exception ? Résultat inattendu ?
Commenter la réponse de cs_Julien39
Messages postés
6413
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
17 mai 2018
244
0
Merci
Sinon, tu as la fonction modPow de la classe BigInteger...
Commenter la réponse de cs_Julien39
Messages postés
5
Date d'inscription
mardi 14 décembre 2010
Statut
Membre
Dernière intervention
22 avril 2012
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
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
21
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
Messages postés
5
Date d'inscription
mardi 14 décembre 2010
Statut
Membre
Dernière intervention
22 avril 2012
0
Merci
Merci pour ton aide mon programme marche a merveille
Commenter la réponse de maitrejediyass