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 

7 réponses

Répondre au sujet
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
Utile
J'oubliais
tu dois écrire
exp = exp.shiftRight(1)
car une instance BigInteger n'est pas modifiable (un peu comme les String)
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_jojolemariole
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
Utile
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
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de cs_jojolemariole
cs_Julien39 6449 Messages postés mardi 8 mars 2005Date d'inscription 15 mars 2018 Dernière intervention - 19 avril 2012 à 17:05
0
Utile
Salut,

Pourquoi ta fonction ne marche pas ? Exception ? Résultat inattendu ?
Commenter la réponse de cs_Julien39
cs_Julien39 6449 Messages postés mardi 8 mars 2005Date d'inscription 15 mars 2018 Dernière intervention - 19 avril 2012 à 17:06
0
Utile
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
Utile
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
Utile
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
Utile
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.