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

На самом деле это не имеет большого значения. Современные 64-битные компьютеры могут складывать два целых числа за одно и то же время, необходимое для их сдвига (1 тактовый цикл), поэтому это займет столько же времени. Я предлагаю вам попробовать разные методы, а затем сообщить, если есть какие-либо существенные различия во времени. Все три метода должны быть простыми в реализации, и создание числа размером 5 МБ также должно быть простым с использованием генератора случайных чисел.

Чтобы сохранить целое число из 5 миллионов цифр, вам понадобится довольно много бит - 5 миллионов, если вы имели в виду двоичные цифры, или ~ 17 миллионов бит, если это были десятичные цифры. Предположим, что числа хранятся в двоичном представлении, а арифметические операции выполняются кусками определенного размера, например 32 бита или 64 бита.

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

• Если умножение на два с помощью сдвига влево, это одна операция сдвига влево для умножения и одна операция сдвига вправо + и с 1 для получения переноса. Вести бухгалтерский учет немного проще.

Внешне сдвижная версия выглядит немного быстрее. Однако общая стоимость удвоения числа во многом зависит от его размера. Число в 17 миллионов бит превышает кэш L1 ЦП, и время обработки, вероятно, перегружено операциями выборки из памяти. На современном оборудовании ПК выборка из памяти на несколько порядков медленнее, чем сложение и смещение.

При этом вы можете выбрать тот, который вам проще реализовать. Я склоняюсь к версии с левым переключением.

ты пробовал сдвигать биты?
‹---------------- умножается на 2
›› делится на 2

Сдвиг левого бита на единицу аналогичен умножению на два!
Эта ссылка Разъясняет механизм и приводит примеры.

int A = 10; //...01010 = 10
int B = A<<1; //..010100 = 20

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

Извините за ответ «Сделай сам», но это действительно лучший способ. Никто не заботится об этом результате больше, чем вы, поэтому вы лучше всех его поймете.

Хорошо реализованное умножение BigNums составляет O (N log (N) log (log (N )). Сложение - O (n). Следовательно, сложение самого себя должно быть быстрее, чем умножение на два. Однако это верно только в том случае, если вы умножаете два произвольных больших числа; если ваша библиотека знает, что вы умножаете большое число на небольшое целое он может быть оптимизирован до O (n).

Как отмечали другие, битовый сдвиг также возможен. Это также должно быть O (n), но более быстрое постоянное время. Но это будет работать только в том случае, если ваша библиотека bignum поддерживает битовый сдвиг.

большая часть вычислений (если не все) приходится на удвоение текущего bigint

Если все ваши вычисления заключаются в удвоении числа, почему бы вам просто не сохранить отдельное поле шкалы (с основанием 2)? Затем просто добавьте один к scale, который может быть просто старым int. Это наверняка будет быстрее, чем любые манипуляции с каким-то нечетным миллионом бит.

IOW, используйте bigfloat.

случайный тест

use Math::GMP;
use Time::HiRes qw(clock_gettime CLOCK_REALTIME CLOCK_PROCESS_CPUTIME_ID);

my $n = Math::GMP->new(2);
$n = $n ** 1_000_000;

my $m = Math::GMP->new(2);
$m = $m ** 10_000;

my $str;
for ($bits = 1_000_000; $bits <= 2_000_000; $bits += 10_000) {
    my $start = clock_gettime(CLOCK_PROCESS_CPUTIME_ID);
    $str = "$n" for (1..3);
    my $stop = clock_gettime(CLOCK_PROCESS_CPUTIME_ID);
    print "$bits,@{[($stop-$start)/3]}\n";
    $n = $n * $m;
}

Кажется, это показывает, что каким-то образом GMP выполняет преобразование за время O (n) (где n - количество бит в двоичном числе). Это может быть связано с особым случаем наличия единицы, за которой следует миллион (или два) нулей; в документах GNU MP говорится, что он должен быть медленнее ( но все же лучше, чем O (N ^ 2).

http://img197.imageshack.us/img197/6527/chartp.png