Вычисление чрезвычайно больших мощностей 2
Я создал программу на 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);
}
}
}
Это не школьный проект или что-то еще; просто для удовольствия. Любая помощь в том, как сделать это более эффективным, будет оценена по достоинству! Спасибо!
Кайл
P.S. Я не упомянул, что вывод должен быть в base-10, а не в двоичном формате.
Ответы
Ответ 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.
Ответ 2
Отображение его в двоичном формате выполняется легко и быстро - так же быстро, как вы можете записать на диск! 100000......: D
Ответ 3
Пусть n = 43112609.
Предположение: Вы хотите напечатать 2 ^ n в десятичной форме.
При заполнении битового вектора, отличного от 2 ^ n в двоичном, тривиально, преобразование этого числа в десятичную нотацию займет некоторое время. Например, реализация java.math.BigInteger.toString принимает операции O (n ^ 2). И, вероятно, почему
BigInteger.ONE.shiftLeft(43112609).toString()
по-прежнему не завершается через час времени выполнения...
Начнем с асимптотического анализа вашего алгоритма. Ваш внешний цикл будет выполняться n раз. Для каждой итерации вы выполните другие операции O (n ^ 2). То есть ваш алгоритм O (n ^ 3), поэтому ожидается слабая масштабируемость.
Вы можете уменьшить это до O (n ^ 2 log n), используя
x ^ 64 = x ^ (2 * 2 * 2 * 2 * 2 * 2) = (((((x ^ 2) ^ 2) ^ 2) ^ 2) ^ 2) ^ 2
(который требует только 8 умножений), а не 64 умножения
x ^ 64 = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x
(Обобщение произвольных показателей остается для вас упражнением. Подсказка: напишите экспоненту как двоичное число - или посмотрите на ответ Ли Райана).
Для ускорения умножения вы можете использовать алгоритм Карацубы, сокращая общее время выполнения до O (n ^ ((log 3)/( log 2)) log n).
Ответ 4
Как уже упоминалось, степени два соответствуют двоичным цифрам. Binary - это база 2, поэтому каждая цифра удваивает значение предыдущего.
Например:
1 = 2^0 = b1
2 = 2^1 = b10
4 = 2^2 = b100
8 = 2^3 = b1000
...
Двоичная база 2 (поэтому она называется "базой 2", 2 является базой показателей), поэтому каждая цифра удваивает значение предыдущей. Оператор сдвига ('<' в большинстве языков используется для сдвига каждой двоичной цифры влево, причем каждый сдвиг эквивалентен умножению на два.
Например:
1 << 6 = 2^6 = 64
Будучи такой простой двоичной операцией, большинство процессоров могут сделать это очень быстро для чисел, которые могут вписываться в регистр (8 - 64 бит, в зависимости от процессора). Для этого с большим количеством требуется некоторый тип абстракции (например, Bignum), но он все равно должен быть чрезвычайно быстрым. Тем не менее, сделать это до 43112609 бит займет немного работы.
Чтобы дать вам небольшой контекст, 2 < 4311260 (отсутствует последняя цифра) длиной 1297181. Удостоверьтесь, что у вас достаточно ОЗУ для обработки выходного номера, если вы не переустановите свой компьютер на диск, что приведет к повреждению скорости выполнения.
Так как программа настолько проста, также рассмотрите возможность переключения на язык, который компилируется непосредственно в сборку, например C.
По правде говоря, генерирование значения тривиально (мы уже знаем ответ, за которым следуют 43112609 нулей). Это займет немного больше времени, чтобы преобразовать его в десятичную.
Ответ 5
Как подсказывает @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 миллионов.
Ответ 6
Другим ключевым моментом является то, что ваш процессор намного быстрее при умножении ints и longs, чем вы, делая длительное умножение в Java. Получите это число, разбитое на длинные (64-байтные) куски, и умножьте и несете куски вместо отдельных цифр. В сочетании с предыдущим ответом (используя квадрат вместо последовательного умножения на 2), вероятно, ускорится его в 100 раз или более.
Edit
Я попытался написать метод chunking и squaring, и он работает немного медленнее, чем 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 ^ n) для некоторого n)
- 131072 - 0,83 секунды
- 262144 - 3.02 секунд
- 524288 - 11,75 секунд
- 1048576 - 49,66 секунд
При такой скорости роста потребуется приблизительно 77 часов, чтобы вычислить 2 ^ 33554432, не говоря уже о времени хранения и суммировании всех мощностей, чтобы сделать окончательный результат 2 ^ 43112609.
Изменить 2
На самом деле, для действительно больших показателей метод BigInteger.ShiftLeft является самым быстрым. Я считаю, что для 2 ^ 33554432 с ShiftLeft это займет приблизительно 28-30 часов. Подумайте, как быстро будет выполняться версия C или Assembly...
Ответ 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 цифр.
