Что лучше умножить на 2 или добавить номер к себе? BIGnums

Question

Мне нужна помощь, чтобы решить, что лучше performance wise. Я работаю с bigints (более 5 миллионов цифр), и большинство вычислений (если не все) находится в части удвоения текущего bigint. Так что я хотел знать, лучше ли умножить каждую ячейку (часть bigint) на 2, затем поменять ее, и вы знаете все остальное. Или лучше всего добавить bigint к себе.

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

Дополнительная информация: Я закодирую его в C++, я довольно хорошо знаком с bigints (просто так и не натолкнулся на эту проблему). Мне не нужен какой-либо исходный код или аналогичный мне просто нужно хорошее мнение и объяснение/доказательство этого, так как мне нужно принять правильное решение, чтобы начать, поскольку проект будет довольно большим и в основном построен вокруг этого часть зависит от того, что я выбрал сейчас.

Спасибо.

Answer 1

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

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

Answer 2

Вы пытались переложить бит?
< < умножает на 2
> > делится на 2

Answer 3

левых бит сдвиг на один такой же, как умножение на два!
Этот link объясняет меканизм и дает примеры.

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

Answer 4

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

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

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

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

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

Answer 5

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

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

Answer 6

большую часть вычислений (если не все) в части удвоения текущего BigInt

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

IOW, используйте большой плащ.

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

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; 
} 

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

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

Answer 7

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

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