Как вычислить ((целое число)^(double))% (целое число) в java?

Question

Я пытаюсь вычислить значение (10^5.102103)% 24, которое 10 приподнято до мощности 5.102103 модуля 24 в Java?

Какой самый лучший и точный метод, чтобы сделать, потому что

int a; 
double b; 
int m; 

Вычислить (a^b)%m

Где может быть очень большим, как ДО 10^9

б может быть любой двойной или поплавок значение которые могут быть большими

и m любое Целое число

Пример --- Как вы можете вычислить значение

(10^10002.3443)%10000007 

Я знаю Math.pow (а, б) функция работает при малых а и б только

В то время как функция BigInteger Использует только modPow (а , b) где a и b должны быть только целыми (исправить меня, если я ошибаюсь)

Answer 1

К сожалению, для получения правильного ответа на это невозможно использовать обычные типы данных Java. Если вы используете double для хранения экспоненты, вы вводите ошибку, потому что double не будет хранить большинство десятичных чисел точно. Когда вы пишете double b = 10002.3443;, номер, который хранится в b, фактически равен 10002.34430000000065774656832218170166015625. Несмотря на то что он выглядит как 10002.3443, когда вы его печатаете, это трюк с тем, как Java печатает числа - в основном он выбирает десятичное число с наименьшим числом десятичных знаков, которое будет представлено этим двойником.

Теперь эта разница выглядит незначительной. Но разница между 10^10002.3443 и 10^10002.34430000000065774656832218170166015625 составляет приблизительно 3.346 x 10^9990, что составляет 9991-значное число. Теперь, какова будет эта разница, когда мы применим оператор модуля?

(10^10002.34430000000065774656832218170166015625 % 10000007) - (10^10002.3443 % 10000007) 
= (10^10002.34430000000065774656832218170166015625 - 10^10002.3443) % 10000007 
= (3.346 x 10^9990) % 10000007 (approximately) 

Теперь все догадываются, что на самом деле происходит. Но у вас больше шансов получить удар молнией, чем получить правильный ответ, если вы используете double в любой точке расчета.

Другой вариант может быть BigDecimal. Но проблема в том, что 10^10002.3443 является иррациональным - это не конечный десятичный знак, поэтому он не может быть правильно представлен в BigDecimal.

Таким образом, у Java нет типа данных, который позволит выполнять вычисления, которые вы хотите выполнить.

Вам придется изобретать свой собственный тип данных, а затем выяснить, как сделать все бит-хруст, чтобы реализовать возведение в степень и модуль. Это огромный проект, и я предлагаю вам начать работу, получив степень кандидата математики.

(Примечание: Очевидно, что я использую ^ указать и возведения в степень x указать умножение в выше, несмотря на то, что это не обычный Java конвенции)

Answer 2

Давайте вернемся к дискретной математике!

Учитывая у = а ^б (тойт), мы знаем, что

y = ((a mod m)^b) mod m 

Например, если мы имеем

a = 2, b = 6, m = 5 

поднятый к власти Ь 64. 64 mod m is 64 % 5 == 4. Давайте проверим наш алгоритм:

4 == ((a mod m)^b) mod m 
4 == ((2 mod 5)^6) mod 5 
... 
4 == 64 % 5 
4 == 4 

Это на самом деле не поможет нам слишком много (в его нынешнем виде), так что давайте использовать модульную арифметику на каждом шагу, чтобы сохранить день.

int a = 10; 
int m = 10000007; 
double b = 10002.3443; 
int holder = (int) b; 
double delta = b - holder; // as close as we're going to get 

int total = 1; 

for (int i = 0; i < holder; i++) { 
    total *= (a % m); // multiply by the modulus 
    total %= m;  // take the modulus again 
} 

total *= (Math.round(Math.pow(a, delta)) % m); 
total %= m;