Расчет чрезвычайно больших полномочий 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);
  }
 }  
}

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

Кайл

PS Я не упомянул, что вывод должен быть в формате 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, используя тот же метод, и так далее ...

РЕДАКТИРОВАТЬ: ранее былоошибка в этом разделе, теперь она исправлена:

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

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

Пусть 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 * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х * х

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

Для ускорения умножения вы можете использовать Алгоритм Карацубы , сокращающий общее время выполнения до O (n ^ ((log 3) / (log 2)) log n).

Answer 4

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

Например:

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

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

Например:

1 << 6 = 2^6 = 64

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

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

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

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

Answer 5

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

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

РЕДАКТИРОВАТЬ: Превращение двоичного в десятичное является проблемой 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.

ПРИМЕЧАНИЕ. Время, затраченное на ввод данных, находится в toString (), а не в shiftLeft, который занимает <1 мс даже для 10 миллионов. </p>

Answer 6

Поскольку каждый действительно хочет получить все цифры результата (в отличие, например, от 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-битных кодах и переберите каждое нижнее слово. Остаток после последнего шага будет девятью нижними десятичными цифрами результата. Поскольку вычисление степени двоичного числа в двоичном коде будет быстрым и простым, я думаю, что наилучшим подходом может быть деление для преобразования в десятичное число.

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

Answer 7

Еще один ключевой момент, на который следует обратить внимание, это то, что ваш процессор намного быстрее умножает целые и длинные числа, чем вы, делая длинное умножение в 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 ^ 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 версия ...