Comment puis-je gérer des nombres énormes en Java?

Question

J'écris un programme pour les devoirs de ma classe de programmation compétitive et je ne peux pas surmonter un problème. Ce problème vous oblige à calculer toutes les permutations d'une certaine chaîne en fonction de certaines conditions et mon programme le fait. Cependant, le problème est quand l'entrée est une chaîne vraiment grande, elle peut aller jusqu'à 10^6.

La solution au problème est 2^résultat, où le résultat dépend de la longueur de la chaîne d'entrée, donc pour 10^6 il peut être jusqu'à 5 * 10^5. La solution doit être donnée sous forme de: résultat% (10^9 + 7).

J'ai essayé de mettre la solution dans un BigInteger, il manque d'espace de tas. J'ai essayé de travailler avec des doubles, ça déborde. Y a-t-il quelque chose qui me manque ou y a-t-il un moyen de régler le problème? Je vous remercie.

Voici quelques tentatives:

System.out.println((int) (Math.pow(2, counter) % (1e9 + 7))); 
//it prints out 0, probably due to overflow? 

DecimalFormat df = new DecimalFormat("#"); 
System.out.println(df.format(Math.pow(2, counter) % (1e9 + 7))); 
//prints out � 

Answer 1

Vous n'avez pas besoin de gérer un nombre extrêmement grand pour le faire.

L'affectation vous propose de mettre en œuvre modular exponentiation. BigInteger l'implémente déjà en tant que modPow. Il vous permet de calculer (b^e) % c sans avoir à traiter avec des nombres significativement plus grands que c.

est ici pseudo-code de Wikipedia pour le reste après exponentiation par élévation au carré répété:

function modular_pow(base, exponent, modulus) 
    if modulus = 1 then return 0 
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base 
    result := 1 
    base := base mod modulus 
    while exponent > 0 
     if (exponent mod 2 == 1): 
      result := (result * base) mod modulus 
     exponent := exponent >> 1 
     base := (base * base) mod modulus 
    return result