Как вычислить остаток для чрезвычайно больших экспоненциальных чисел с помощью java?

Question

Как вычислить остаток для чрезвычайно больших экспоненциальных чисел с помощью java? например. (48^26)/2401

Я попытался использовать BIGINTEGER, однако он дал тот же результат для больших делителей. Я не уверен, что BIG INTEGER может это сделать. Я пробовал все другие типы PRIMITIVE. Они, похоже, быть недостаточным.

FYI он попытался следующий код:

BigInteger a = new BigInteger("48"); 
a = a.pow(26); 
BigInteger b = new BigInteger("2401");//49*49 
a = a.mod(b); 
System.out.println(a); 

Я не знаю, почему я получил тот же выходной каждый раз, это странно, что он сейчас работает нормально. Ответ получен 1128

Answer 1

Вы можете использовать повторяющийся модуль меньших чисел.

у вас есть

(a * b) % n 
((A * n + AA) * (B * n + BB)) % n      | AA = a %n & BB = b % n 
(A * B * n^2 + A * N * BB + AA * B * n + AA * BB) % n 
AA * BB % n           since x * n % n == 0 
(a % n) * (b % n) % n 

В вашем случае, вы можете написать

48^26 % 2401 
(48^2)^13 % 2401 

как

int n = 48; 
for (int i = 1; i < 26; i++) 
    n = (n * 48) % 2401; 
System.out.println(n); 

int n2 = 48 * 48; 
for (int i = 1; i < 13; i++) 
    n2 = (n2 * 48 * 48) % 2401; 
System.out.println(n2); 

System.out.println(BigInteger.valueOf(48).pow(26).mod(BigInteger.valueOf(2401))); 

отпечатки

1128 
1128 
1128 

Как указывает @Ruchina, ваш пример достаточно мал, чтобы рассчитать, используя простое двойное выражение.

for (int i = 1; i < 100; i++) { 
    BigInteger mod = BigInteger.valueOf(48).pow(i).mod(BigInteger.valueOf(2401)); 
    double x = Math.pow(48, i) % 2401; 
    if (mod.intValue() != x) { 
     System.out.println(i + ": " + mod + " vs " + x); 
     break; 
    } 
} 

печатает

34: 736 vs 839.0 

Другими словами, любая сила 48 прекрасно до 33.

Answer 2

Попробуйте использовать BigDecimal для больших десятичных чисел. Он не подвержен ошибкам, например, double и float из-за того, как хранятся данные. Кроме того, он имеет (потенциально) бесконечное количество десятичных знаков.

Answer 3

BigDecimal b= BigDecimal.valueOf(Math.pow(48,26) %2401); 

output b = 1128.0 

Answer 4

Это работал для меня.

import java.math.BigInteger; 


public class BigMod{ 
     public static void main (String[] args){ 
       BigInteger b1 = new BigInteger ("48"); 
       BigInteger b2 = new BigInteger ("2401"); 
       BigInteger b3 = b1.pow(26); 
       BigInteger result = b3.mod(b2); 
       System.out.println(result); 
     } 
} 

Не знаете, в чем проблема с BigInteger. Можете ли вы объяснить, что не сработало?

Answer 5

Использование BigInteger.modPow().

BigInteger a = new BigInteger("48"); 
BigInteger b = new BigInteger("26"); 
BigInteger c = new BigInteger("2401"); 

BigInteger answer = a.modPow(b, c); 

Ответ будет 1128. Обратите внимание, что BigInteger неизменна так и объекты а, Ь и с не может быть изменен.

Answer 6

Вам даже не нужно BigInteger для этого, вы можете вычислить это значение, используя BigMod разделяй и властвуй алгоритм, воспользовавшись следующим свойством mod операции

(A * B) mod n = ((A mod n) * (B mod n)) mod n 

Тогда (B^c) mod n можно рассматривать как частный случай собственности:

(B^c) mod n = ((B mod n) * (B mod n) ... c times) mod n 

следующий код делает расчет:

public class BigModExample { 
    public static long bigMod(long b, long c, int n) { 
     if (c == 0) { 
      return 1; 
     } 

     // Returns: (b^c/2) mod n 
     long b2 = bigMod(b, c/2, n);   

     // Even exponent 
     if ((c & 1) == 0) { 
      // [((b^c/2) mod n) * ((b^c/2) mod n)] mod n 
      return (b2 * b2) % n; 
     } else { 
      // Odd exponent 
      // [(b mod n) * ((b^c/2) mod n) * ((b^c/2) mod n)] mod n 
      return ((b % n) * (b2 * b2)) % n; 
     } 
    } 

    public static void main(String... args) { 
     System.out.println(bigMod(48, 26, 2401)); 
    } 
} 

Печать

1128 

Answer 7

Далее пояснение по решению Питера Lawrey в.

(a*b)%n 
= ((A*n + AA) * (B*n + BB))%n where a=A*n+AA, AA=a%n & b=B*n+BB, BB=b%n 
= (A*B*n^2 + A*n*BB + AA*B*n + AA*BB)%n 
= (AA*BB)%n 
= (a%n * b%n)%n 

(a^c)%n 
= (a^(c-1) * a)%n 
= ((a^(c-1))%n * a%n)%n 
= ((a^(c-2)*a)%n * a%n)%n 
= ((a^(c-2)%n * a%n)%n * a%n)%n 

Пример1: когда с 3

(a^3)%n 
= ((a^2)*a)%n 
= ((a^2)%n * a%n)%n 
= ((a*a)%n * a%n)%n 
= ((a%n * a%n)%n * a%n)%n 

Пример2: когда с 4

(a^4)%n 
= ((a^3)*a)%n 
= ((a^3)%n * a%n)%n 
= ((a^2 * a)%n * a%n)%n 
= (((a^2)%n * a%n)%n * a%n)%n 
= (((a*a)%n * a%n)%n * a%n)%n 
= ((a%n * a%n)%n * a%n)%n * a%n)%n 

Java код:

int a = 48; 
int c = 26; 
int n = 2401; 
int a_mod_n = a%n; 
int result = a_mod_n; 
for (int i = 1; i < c; i++) { 
    result = (result * a_mod_n) % n; 
} 
System.out.println("result: " + result); 

48 неоднозначно, поскольку оба a d a%n: 48. Вышеупомянутый код Java строго следует уравнению ((a^(c-2)%n * a%n)%n * a%n)%n, так что его легче понять.