Реализация Bignum с эффективным добавлением маленьких целых чисел

Question

Я использовал собственные алгоритмы Python для алгоритма и решил попытаться ускорить его, преобразовав его в C ++. Когда я использовал длинные long, C ++ был примерно в 100 раз быстрее чем python, но когда я использовал привязки GMP в C ++, он был только в 10 раз быстрее чем python (для тех же случаев, которые подходят для long long).

Есть ли лучшая реализация bignum для выполнения большого количества небольших дополнений? Например, у нас есть большое число N, мы будем добавлять много маленьких +1, +21, +1 и т. Д. И время от времени добавляем еще одно большое число M?

Answer 1

Сама библиотека GMP имеет быстрое короткое целое число, добавляемое в процедуру MPZ

void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2)

Я не знаю, использует ли это gmpy, но если это так, попробуйте добавить обычный python int в mpz против добавления mpz в mpz и посмотрите, быстрее ли это.

Редактировать

Я попробовал немного сравнительного анализа и обнаружил, что это не имеет никакого значения

$ python -m timeit -c 'from gmpy import mpz
> a=mpz(10**1000)' 'a+1'
100000 loops, best of 3: 5.4 usec per loop

$ python -m timeit -c 'from gmpy import mpz
a=mpz(10**1000); b=mpz(1)' 'a+b'
100000 loops, best of 3: 5.5 usec per loop

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

Answer 2

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

GMPY v1.11 использует mpz_add_ui при добавлении небольшого числа в mpz. Новейшая версия GMPY также работает примерно на 25% быстрее, чем предыдущие версии при работе с небольшими номерами.

With GMPY 1.04
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1"
10000000 loops, best of 3: 0.18 usec per loop
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b"
10000000 loops, best of 3: 0.153 usec per loop

With GMPY 1.11
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1"
10000000 loops, best of 3: 0.127 usec per loop
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b"
10000000 loops, best of 3: 0.148 usec per loop

Поскольку конвертировать Python int в long быстрее и вызывать mpz_add_ui быстрее, чем конвертировать Python int в mpz, преимущество в производительности незначительно. Я не удивлюсь, если будет 10-кратное снижение производительности при вызове функций GMP по сравнению с нативными операциями в течение длительного времени.

Можете ли вы накопить несколько маленьких чисел в один длинный и добавить их одновременно к своему большому числу?

Answer 3

Вы делали профилирование? Из Python и C ++ целых приложений. Чтобы вы знали, что вам действительно нужна эта дополнительная скорость.

Попробуйте Python 3k, теперь в нем реализованы целые числа любой длины!