Int в BigInteger, в чем разница?

Я передаю функцию modExp из int в BigInteger, но результат другой, чем отличаются эти две функции?

Спасибо!!!

Функция с BigInteger, результат всегда 1:

public static BigInteger modExp(BigInteger a, BigInteger b, BigInteger n) {
    BigInteger two = new BigInteger("2");       
    if (b == BigInteger.ZERO)
        return BigInteger.ONE;
    BigInteger t = modExp (a, b.divide(two), n);
    BigInteger c = (t.pow(2)).mod(n);
    if (b.mod(two) == BigInteger.ONE)
        c = (c.multiply(a)).mod(n);
    return c;       
}

Функция с int:

public static int modexp(int a, int b, int n) {
    if (b == 0) return 1;
    long t = modexp(a, b/2, n);  // use long for intermediate computations to eliminate overflow
    long c = (t * t) % n;
    if (b % 2 == 1)
       c = (c * a) % n;
    return (int) c;
}

Функция предназначена для вычисления a^b mod p, например:

a=4 b=6 p=11  result1 = 1  result2 = 4
a=9 b=2 p=11  result1 = 1  result2 = 4
a=5 b=6 p=23  result1 = 1  result2 = 8 ...

java math biginteger
person Stephen    schedule 21.08.2015    source источник
comment
Какая разница в результатах? В какой момент в вычислениях они расходятся?   -  person Scott Hunter    schedule 21.08.2015
comment
Возвращает ли он 1 из-за оператора b == 0 if?   -  person Jose Martinez    schedule 21.08.2015
comment
Используйте compareTo вместо ==.   -  person Bubletan    schedule 21.08.2015
comment
у вас есть инструмент отладки, такой как Xdebug?   -  person SaggingRufus    schedule 21.08.2015
comment
Я тестировал b.compareTo(BigInteger.ZERO) == 0, но результат тот же, поэтому я использую ==, чтобы упростить   -  person Stephen    schedule 21.08.2015
comment
Вместо целочисленного деления на 2 используйте .shiftRight(1) (но не забывайте об отрицательных числах), и проверка нуля может быть выполнена с помощью .signum() == 0.   -  person Joop Eggen    schedule 21.08.2015
comment
Ой, я забываю изменить ==1, когда я его меняю, это правильно. Спасибо   -  person Stephen    schedule 21.08.2015
comment
== определенно неверно, это равенство объектов. Иногда это срабатывает при сравнении таких констант, как ZERO.   -  person Joop Eggen    schedule 21.08.2015

Ответы (2)


arrow_upward
8
arrow_downward

Очевидная разница - это разница между int и BigInteger.

Одно отличие состоит в том, что int - это примитивный тип, а BigInteger - ссылочный тип. Таким образом, при сравнении BigIntegers лучше использовать equals (). Итак, b == BigInteger.ZERO должно быть BigInteger.ZERO.equals(b).

BigInteger больше подходит для работы с большими числами и предотвратит возникновение проблем с переполнением максимального значения int, поддерживаемого Java.

Переполнение может быть причиной того, что вы получаете другой результат от двух функций. Когда это происходит, это не вызывает никакого исключения, но значения ints перепутываются.

person Danail Alexiev    schedule 21.08.2015
comment
Я использовал его, но он все равно ошибался. Я тоже пробую b.compareTo(BigInteger.ZERO) == 0, но результат все равно 1. - person Stephen; 21.08.2015
comment
Да, вы правы, мне нужно изменить b == BigInteger.ZERO и b.mod(two) == BigInteger.ONE для compareTo, результат правильный, спасибо! - person Stephen; 21.08.2015
comment
Вы также меняли это b.mod(two) == BigInteger.ONE сравнение? Предлагаю пошагово отладить оба метода и проследить, как меняется результат. Самый простой способ найти ошибки - person Danail Alexiev; 21.08.2015

arrow_upward
0
arrow_downward

В java int может рассчитывать от -2 ^ 31 до 2 ^ 31-1, потому что int кодируется более 4 байтов, но long может рассчитывать от -2 ^ 63 до 2 ^ 63-1, потому что long кодируются более 8 байтов.

Во втором способе с этим:

return (int) c;

вы можете потерять данные (4 первых байта)

Это могло бы объяснить, почему ваши результаты отличаются, потому что BigInteger закодированы намного больше байтов, чем длинные

person Jib'z    schedule 21.08.2015