Как найти num в данном случае, чтобы в конце она имела тип int?

Question

Как найти num в данном случае, чтобы в конце она имела тип int?

import java.math.BigInteger;

public class Decode {
    public static void main(String[] args) {
        int n = 143;
        BigInteger num = BigInteger.valueOf((long)Math.pow(42, 103));
        num = num % n;
        num = (int)num;
    }
}

пробовал с long, но он не подошел к таким большим числам:

int n = 143;
long num = (long)Math.pow(42, 103);
System.out.println(num); // 9223372036854775807 long не достаточно
num = num % n;
num = (int)num;

Answer 1

Math.pow возвращает double. Числа с плавающей запятой могут представить гораздо большее значение, чем целочисленное. Получить из double int без усечения не получится. Зато получится сразу получить BigInteger:

BigInteger base = new BigInteger("42");
BigInteger result = base.pow(103);

System.out.println(result);

После уточнения вопроса:

BigInteger n = new BigInteger("143");
BigInteger num = new BigInteger("42");
BigInteger pow = num.pow(103);
BigInteger mod = pow.mod(n);

System.out.println(mod); // Можно mod.intValue()

Answer 2

int intNum = new BigInteger("42").pow(103).remainder(new BigInteger("143")).intValue();

Answer 3

Почему 42^103 не помещается в long? long может представлять числа до 2^63, а наша степень требует log2(42^103) = log2(42) * 103 > 555 бит.

В double 42^103 помещается. Но double точно представляет только 53 старших бита числа. Остальные 502 бит отброшены. А когда спрашивают про остаток от деления, то спрашивают в каком-то смысле про младшие биты. А они-то и отброшены.

Вариант с BigInteger решает задачу точно. Но задачу можно решить быстрее и без BigInteger.

Последнее действие в решении - взятие остатка по модулю. Правило умножения по модулю позволяет умножать не сами числа а их остатки:

(a * b) mod m = ((a mod m) * (b mod m)) mod m

Тогда цикл возведения в степень из

int pow = 1;
for (int i = 0; i < p; ++i) {
    pow *= b;
}

превращается в

int pow = 1;
for (int i = 0; i < p; ++i) {
    pow = (pow * b) % m;
}

Кажется что всё только усложнилось, но теперь нам не грозит переполнение. А так как мы умножаем "короткие" целые (int) а не "длинные" ('BigInteger`), то все работает намного быстрее.

Вариант с BigInteger:

import java.math.BigInteger;

public class Decode1 {
    public static void main(String[] args) {
        BigInteger m = new BigInteger(args[0]);
        BigInteger b = new BigInteger(args[1]);
        int p = Integer.parseInt(args[2]);

        System.out.println(b.pow(p).mod(m));
    }
}

Вариант с int и умножением по модулю:

public class Decode2 {
    public static int pow(int m, int b, int p) {
        int pow = 1;
        for (int i = 0; i < p; ++i) {
            pow = (pow * b) % m;
        }
        return pow;
    }

    public static void main(String[] args) {
        int m = Integer.parseInt(args[0]);
        int b = Integer.parseInt(args[1]);
        int p = Integer.parseInt(args[2]);

        System.out.println(pow(m, b, p));
    }
}

Сравним времена вычислений. Decode1 замедляется сильнее всего. Decode2 работает за время пропорциональное степени.

     power  Decode1  Decode2  Decode3
       103   0.054    0.050    0.059
      1000   0.055    0.053    0.052
     10000   0.070    0.051    0.048
    100000   0.124    0.063    0.050
   1000000   0.679    0.060    0.058
  10000000  12.160    0.138    0.049
 100000000   ?        0.914    0.052
1000000000   ?        8.795    0.050

Decode3 реализует быстрое возведение в степень по модулю. Эта программа работает так быстро, что время в таблице - это время загрузки программы, а исполняется она за время, которое трудно измерить:

public class Decode3 {
    public static int pow(int m, int b, int p) {
        int pow = 1;
        for (; p > 0; p /= 2) {
            if (p % 2 == 1) {
                pow = (pow * b) % m;
            }
            b = (b * b) % m;
        }
        return pow;
    }

    public static void main(String[] args) {
        int m = Integer.parseInt(args[0]);
        int b = Integer.parseInt(args[1]);
        int p = Integer.parseInt(args[2]);

        System.out.println(pow(m, b, p));
    }
}

БЛОГ НА HUSL

Как найти num в данном случае, чтобы в конце она имела тип int?

Ответы (3 шт):