Что лучше умножить на 2 или добавить число к себе?BIGnums - PullRequest
Новая
       53

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

3 голосов
/ 11 августа 2009

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

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

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

Спасибо.

Ответы [ 7 ]

9 голосов
/ 11 августа 2009

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

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

5 голосов
/ 11 августа 2009

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

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

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

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

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

1 голос
/ 11 августа 2009

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

int A = 10; //...01010 = 10
int B = A<<1; //..010100 = 20
1 голос
/ 11 августа 2009

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

0 голосов
/ 11 августа 2009

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

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

0 голосов
/ 11 августа 2009

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

Если все ваши вычисления сводятся к удвоению числа, почему бы вам просто не сохранить отдельное (базовое-2) поле шкалы? Затем просто добавьте единицу в масштаб, который может быть просто старым 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 число бит в двоичном числе). Это может быть связано с особым случаем наличия 1, за которым следует миллион (или два) нуля; GNU MP документы говорят, что это должно быть медленнее (но все же лучше, чем O (N ^ 2).

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

0 голосов
/ 11 августа 2009

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

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

...