Вычисление чрезвычайно больших мощностей 2

Question

Я сделал программу на Java, которая вычисляет мощности двух, но кажется очень неэффективной. Для меньших степеней (например, 2^4000) он делает это менее чем за секунду. Тем не менее, я рассматриваю вычисление 2^43112609, что на один больше, чем наибольшее из известных простых чисел. Имея более 12 миллионов цифр, это займет очень много времени. Вот мой код:

import java.io.*; 

public class Power 
{ 
private static byte x = 2; 
private static int y = 43112609; 
private static byte[] a = {x}; 
private static byte[] b = {1}; 
private static byte[] product; 
private static int size = 2; 
private static int prev = 1; 
private static int count = 0; 
private static int delay = 0; 
public static void main(String[] args) throws IOException 
{ 
    File f = new File("number.txt"); 
    FileOutputStream output = new FileOutputStream(f); 
    for (int z = 0; z < y; z++) 
    { 
    product = new byte[size]; 
    for (int i = 0; i < a.length; i++) 
    { 
    for (int j = 0; j < b.length; j++) 
    { 
    product[i+j] += (byte) (a[i] * b[j]); 
    checkPlaceValue(i + j); 
    } 
    } 
    b = product; 
    for (int i = product.length - 1; i > product.length - 2; i--) 
    { 
    if (product[i] != 0) 
    { 
    size++; 
    if (delay >= 500) 
    { 
     delay = 0; 
     System.out.print("."); 
    } 
    delay++; 
    } 
    } 
    } 
    String str = ""; 
    for (int i = (product[product.length-1] == 0) ? 
    product.length - 2 : product.length - 1; i >= 0; i--) 
    { 
    System.out.print(product[i]); 
    str += product[i]; 
    } 
    output.write(str.getBytes()); 
    output.flush(); 
    output.close(); 
    System.out.println(); 
} 

public static void checkPlaceValue(int placeValue) 
{ 
    if (product[placeValue] > 9) 
    { 
    byte remainder = (byte) (product[placeValue]/10); 
    product[placeValue] -= 10 * remainder; 
    product[placeValue + 1] += remainder; 
    checkPlaceValue(placeValue + 1); 
    } 
} 
} 

Это не школьный проект или что-то еще; просто для удовольствия. Любая помощь в том, как сделать это более эффективным, будет оценена по достоинству! Благодаря!

Kyle

P.S. Я не упомянул, что выход должен быть в base-10, а не двоичном.

Answer 1

Ключ здесь заметить, что:

2^2 = 4 
2^4 = (2^2)*(2^2) 
2^8 = (2^4)*(2^4) 
2^16 = (2^8)*(2^8) 
2^32 = (2^16)*(2^16) 
2^64 = (2^32)*(2^32) 
2^128 = (2^64)*(2^64) 
... and in total of 25 steps ... 
2^33554432 = (2^16777216)*(16777216) 

Тогда так:

2^43112609 = (2^33554432) * (2^9558177) 

вы можете найти оставшиеся (2^9558177), используя тот же метод, и так (2^9558177 = 2^8388608 * 2^1169569), вы можете найти 2^1169569 с помощью тот же метод, и с (2^1169569 = 2^1048576 * 2^120993) вы можете найти 2^120993, используя тот же метод, и так далее ...

EDIT: ранее была допущена ошибка в этом разделе, теперь это исправлено:

Кроме того, дальнейшее упрощение и оптимизация, заметив, что:

2^43112609 = 2^(0b10100100011101100010100001) 
2^43112609 = 
     (2^(1*33554432)) 
    * (2^(0*16777216)) 
    * (2^(1*8388608)) 
    * (2^(0*4194304)) 
    * (2^(0*2097152)) 
    * (2^(1*1048576)) 
    * (2^(0*524288)) 
    * (2^(0*262144)) 
    * (2^(0*131072)) 
    * (2^(1*65536)) 
    * (2^(1*32768)) 
    * (2^(1*16384)) 
    * (2^(0*8192)) 
    * (2^(1*4096)) 
    * (2^(1*2048)) 
    * (2^(0*1024)) 
    * (2^(0*512)) 
    * (2^(0*256)) 
    * (2^(1*128)) 
    * (2^(0*64)) 
    * (2^(1*32)) 
    * (2^(0*16)) 
    * (2^(0*8)) 
    * (2^(0*4)) 
    * (2^(0*2)) 
    * (2^(1*1)) 

Также обратите внимание, что 2^(0*n) = 2^0 = 1

Использование этот алгоритм, вы можете рассчитать таблицу 2^1, 2^2, 2^4, 2^8, 2^16 ... 2^33554432 в 25 умножениях. Затем вы можете преобразовать 43112609 в свое двоичное представление и легко найти 2^43112609, используя менее 25 умножений. В общем, вам нужно использовать менее 50 умножений, чтобы найти 2^n, где n находится в диапазоне от 0 до 67108864.

Answer 2

Отображать его в двоичном формате легко и быстро - так же быстро, как вы можете записать на диск! 100000 ......: D

Answer 3

Как упомянуто, полномочия двух соответствуют двоичным цифрам. Binary - это база 2, поэтому каждая цифра удваивает значение предыдущего.

Например:

1 = 2^0 = b1 
    2 = 2^1 = b10 
    4 = 2^2 = b100 
    8 = 2^3 = b1000 
    ... 

Binary является базой 2 (именно поэтому его называют «базой 2», 2 является базой показателей), поэтому каждая цифра вдвое превышает значение предыдущего. Оператор сдвига ('< <' в большинстве языков) используется для сдвига каждой двоичной цифры влево, причем каждая смена эквивалентна умножению на два.

Например:

1 << 6 = 2^6 = 64 

Будучи такой простой бинарной операцией, большинство процессоров могут сделать это очень быстро для чисел, которые могут поместиться в регистре (8 - 64 бит, в зависимости от процессора). Для этого с большим количеством требуется некоторый тип абстракции (например, Bignum), но он все равно должен быть чрезвычайно быстрым. Тем не менее, делать это до 43112609 бит займет немного работы.

Чтобы дать вам небольшой контекст, 2 < < 4311260 (отсутствует последняя цифра) составляет 1297181 цифр. Удостоверьтесь, что у вас достаточно ОЗУ для обработки выходного номера, если вы не переходите на свой компьютер на диск, что может привести к калечению скорости выполнения.

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

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

Answer 4

Как @John SMith предлагает, вы можете попробовать. 2^4000

System.out.println(new BigInteger("1").shiftLeft(4000)); 

EDIT: превращение двоичного кода в десятичное число является проблемой O (n^2). Когда вы удваиваете количество бит, вы удваиваете длину каждой операции и удваиваете количество произведенных цифр.

2^100,000 takes 0.166 s 
2^1000,000 takes 11.7 s 
2^10,000,000 should take 1200 seconds. 

Примечание: Время, затраченное является entriely в ToString(), а не shiftLeft, который принимает < 1 мс, даже за 10 миллионов.

Answer 5

Другой ключ, который следует заметить, заключается в том, что ваш процессор намного быстрее при умножении ints и longs, чем вы, умножение в Java. Получите это число, разбитое на длинные (64-байтные) куски, и умножьте и несете куски вместо отдельных цифр. В сочетании с предыдущим ответом (используя квадрат вместо последовательного умножения 2), вероятно, ускорится его в 100 раз или более.

Редактировать

Я попытался написать отрывов и ФОРМАТНО метод, и он работает немного медленнее, чем BigInteger (13,5 секунды против 11,5 секунд, чтобы вычислить 2^524288). После того, как делают некоторые моменты времени и экспериментов, самый быстрый метод, кажется, повторяется квадратуре с классом BigInteger:

public static String pow3(int n) { 
    BigInteger bigint = new BigInteger("2"); 
    while (n > 1) { 
     bigint = bigint.pow(2); 
     n /= 2; 
    } 
    return bigint.toString(); 
} 

• Некоторые результаты синхронизации для мощности 2 показателей (2^(2^п) для некоторого п)
• 131 072 - 0,83 секунды
• 262144 - 3,02 секунды
• 524288 - 11,75 секунды
• 1048576 - 49,66 секунды

При таком темпе роста потребуется приблизительно 77 часов, чтобы вычислить 2^33554432, не говоря уже о времени хранения и суммировании всех мощностей, чтобы сделать окончательный результат 2^43112609.

Edit 2

На самом деле, для очень больших показателей, метод BigInteger.ShiftLeft является самым быстрым.Я считаю, что для 2^33554432 с ShiftLeft это займет приблизительно 28-30 часов. Интересно, как быстро C или версия Ассамблея примет ...

Answer 6

Пусть п = 43112609.

Предположение: Вы хотите напечатать 2^п в десятичного.

При заполнении битового вектора, отличного от 2^n в двоичном, тривиально, преобразование этого числа в десятичное обозначение займет некоторое время. Например, реализация java.math.BigInteger.toString принимает операции O (n^2). И это, вероятно, почему

BigInteger.ONE.shiftLeft(43112609).toString() 

до сих пор не прекращается через час времени выполнения ...

Давайте начнем с асимптотическим анализом вашего алгоритма. Ваш внешний цикл будет выполняться n раз. Для каждой итерации вы выполните другие операции O (n^2). То есть ваш алгоритм O (n^3), поэтому ожидается слабая масштабируемость.

Вы можете уменьшить это O (N^2 журнала п) путем использования

х^64 = х^(2 * 2 * 2 * 2 * 2 * 2) = ((((((х^2)^2)^2)^2)^2)^2

(который требует только 8 умножений), а не 64 умножений

х^64 = х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * x * x * x * x * x * x * x

(Обозначение произвольных показателей остается для вас упражнением. Подсказка: Wr это показатель как двоичное число, или посмотрите на ответ Ли Райана).

Для ускорения умножения вы можете использовать Karatsuba Algorithm, уменьшая общее время выполнения до O (n^((log 3)/(log 2)) log n).

Answer 7

Потому что на самом деле нужны все цифры результата (в отличие, например, RSA, где интересует только остаточная модификация числа, которое намного меньше, чем числа, которые у нас есть здесь). Я считаю, что наилучшим подходом, вероятно, является извлечение девять десятичных цифр сразу с использованием длинного разделения, реализованного с использованием умножения. Начнем с остатком, равным нулю, и применить следующее каждые 32 бит, в свою очередь (MSB первый)

 
    residue = (residue SHL 32)+data 
    result = 0 

    temp = (residue >> 30) 
    temp += (temp*316718722) >> 32 
    result += temp; 
    residue -= temp * 1000000000; 

    while (residue >= 1000000000) /* I don't think this loop ever runs more than twice */ 
    { 
    result ++; 
    residue -= 1000000000; 
    } 

Затем сохранить результат в 32 бита просто читать, и цикл через каждого нижнего слова. Остаток после последнего шага будет девять нижних десятичных цифр результата. Поскольку вычисление мощности двух в двоичном формате будет быстрым и легким, я думаю, что деление на преобразование в десятичный может быть лучшим подходом.

BTW, это вычисляет 2^640000 примерно через 15 секунд в vb.net, поэтому 2^43112609 должно составлять около пяти часов для вычисления всех 12,978,188 цифр.