Вычислить мощность с помощью многопотоков

Question

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

public BigInteger generate(long Power, long Base){ 

    BigInteger result = BigInteger.valueOf(Base), 
    a = BigInteger.valueOf(Base); 
    int j=0; 

    while(j!=Power-1){ 
     result = result.multiply(a); 
     j++; 
    } 

    return result; 
} 

Я хотел бы знать, есть ли какой-либо математический способ разделить этот тип вычисления в несколько потоков, так что моя программа будет вычислять такие вещи, как 987654321^987654321 гораздо быстрее. Мой процессор имеет 6 ядер, поэтому, если есть способ использовать их все сразу для этого, это было бы здорово.

Answer 1

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

Base = a_1 * ... * a_n 

, а затем вычислить a_i^b в отдельных потоках, и умножают результаты. Вам нужно какое-то вычислительное усилие для поиска факторизации, но я бы сначала проверил, достаточно ли числа «достаточно», чтобы беспокоиться о нескольких ядрах, и если они есть, начните с некоторых стандартных проверок, если возможна факторизация. Или просто разделите на первые 100 простых чисел, это не займет много времени.

Особенно, если число дофакторизовывается несколько раз от того же фактора, вы просто должны вычислить мощность один раз, т.е.

(24)^5 = (3*2*2*2)^5 = 3^5 * 2^5 * 2^5 * 2^5 

и поэтому вы вычислить r_1 = 3^5 и r_2 = 2^5, а затем умножить результат r = r_1 * r_2 * r_2 * r_2.

Вы также можете разложить экспоненты, но тогда алгоритм будет немного сложнее.