작은 정수를 효율적으로 추가하는 Bignum 구현

Question

파이썬의 네이티브 bignum을 알고리즘으로 사용하여 C++로 변환하여 속도를 높이기로 결정했습니다. long long을 사용했을 때 C++은 파이썬보다 약 100 배 빠르지 만 C++에서 GMP 바인딩을 사용했을 때 파이썬보다 10 배 빠릅니다 (long long에 맞춰 같은 경우).

다수의 작은 추가를 수행하는 데 더 나은 bignum 구현이 있습니까? 예를 들어, 우리는 큰 숫자 N을 가지고 있습니다. 우리는 많은 작은 +1, +21, +1 등을 추가 할 것입니다. 그리고 매번 또 다른 큰 숫자 M을 추가합니까?

Answer 1

GMP의 라이브러리 자체가 내가 gmpy이 것을 사용하는지 여부를 모르는 fast short integer add to MPZ routine

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

가지고 있지만 MPZ에 MPZ를 추가 대 MPZ에 일반 파이썬 INT를 추가하려고하고 있는지 않는 경우 그것은 더 빠릅니다.

편집

나는 벤치마킹의 약간을 시도하고 그래서 내가 정말이 될 것으로 기대하는 것처럼 gmpy이 mpz_add_ui를 사용하지 않는 것 같아요 어떤 차이

$ 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 

가되지 않습니다 발견 훨씬 빨라.

Answer 2

프로파일을 작성 했습니까? Python 및 C++ 전체 응용 프로그램. 그래서 당신은 그 추가 속도가 정말로 필요하다는 것을 알고 있습니다.

파이썬 3k를 사용해보십시오. 이제 길이가 설정된 정수가 구현되었습니다!

Answer 3

(참고 :. 내가 GMPY을 유지하는 데 도움이 내가 가장 최근의 릴리스에서 꽤 많은 최적화를 구현했습니다)을 MPZ에 소수를 추가 할 때

GMPY의 V1.11가 mpz_add_ui를 사용 않습니다. GMPY의 최신 버전은 작은 숫자로 작업 할 때 이전 버전보다 약 25 % 빠릅니다. 그것은 긴에 파이썬 INT로 변환하고 MPZ에 파이썬 INT로 변환하는 것보다 mpz_add_ui 전화를 빨리하기 때문에

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 

, 적당한 성능 이점이있다. 긴 시간 동안 GMP 함수를 네이티브 연산과 비교하여 호출했을 때 10 배의 성능 저하가 있다면 놀랄 일이 아닙니다.

몇 개의 작은 숫자를 하나의 긴 길이로 누적하여 한 번에 큰 번호에 추가 할 수 있습니까?