매우 큰 정수 곱셈과 또한

Question

인사말,

나는 (,) 정확하게는 GMP (MPIR를 통해 수출, 그래서 그들은 어떤 자료가 될 수 있습니다) 텍스트 파일에 저장이 개 매우 긴 정수 값을 곱합니다 . 이제는 보통 mpz_inp_str() 함수를 통해 이러한 정수를 가져 와서 RAM에서 곱셈을 수행하지만이 값은 너무 길어서 실제로로드 할 수 없습니다 (각각 약 1GB의 데이터). 이 작업을 수행하는 가장 빠른 방법은 무엇입니까? 아마도 이런 종류의 일을하는 외부 라이브러리가있을 것입니다. 이 작업을 쉽게 구현할 수있는 방법이 있습니까 (이 작업은 한 두 번만 수행되므로 성능이 크게 중요하지 않습니다)?

tl; dr : 프로세스 메모리 제한 (Windows)에 맞지 않는 큰 값을 곱해야합니다.

감사합니다.

Answer 1

이 기능을 지원하는 라이브러리가 있는지 모르겠지만 각 RBN (Big Number)의 일부에서 GMP/MPIR을 사용할 수 있습니다. 즉, 각 RBN을 관리하기 쉽고 균일 한 크기의 청크 (예 : 10M 자리 청크, 가장 중요한 숫자의 경우 작은 청크가 예상 됨, 아래 참조)로 분리합니다.

 
    RBN1 --> A B C D E 
    RBN2 --> F G H I J 

청크

그래서 그냥 > 문자 각 부분의 파일에서 < chuck_size 읽기,베이스 (10)에 수행 할 수 있습니다. 그런 다음 한 번에 하나씩 숫자의 덩어리를 곱하십시오.

 
    AxF BxF CxF DxF ExF 
    + AxG BxG CxG DxG ExG 
    +  AxH BxH CxH DxH ExH 
    +   AxI BxI CxI DxI ExI 
    +    AxJ BxJ CxJ DxJ ExJ 

최종 합계의 각 열을 메모리에서 수행하십시오. 그런 다음 캐리를 메모리에 보관하고 디스크에 다음 열을 반복합니다. carry의 경우 각 열 합계 결과를 GMP를 사용하여 문자열로 변환하고 < 청크 크기 결과의 일부와 읽기 부분을 씁니다. 상단 부분은 캐리를위한 GMP int로 다시 나타납니다.

각 열 추가를 메모리에 유지하기 위해 각 곱셈에 대해 청크 크기를 동적으로 선택하는 것이 좋습니다. 숫자가 클수록 더 많은 컬럼 추가가 필요하며, 청크 크기가 더 작을 필요가 있습니다.

읽기 및 쓰기 모두에 대해 메모리 매핑 된 파일을 사용하는 것이 좋습니다. this에 대한 좋은 인터페이스가 있습니다 (전체 파일을로드하지 않으며 기본적으로 가상 메모리의 IO를 버퍼링합니다). 각 입력 RBN 번호에 대해 매핑 된 파일 하나를 열고 크기 = 크기 (RBN1) + 크기 (RBN2) +1의 출력 하나를 엽니 다. 메모리 매핑 파일을 사용하면 파일 액세스가 원시 char *로 처리되므로 gmp c-string io 메서드를 사용하여 청크를 직접 읽고 쓸 수 있습니다. 메모리 맵핑 된 파일을 일시적으로 변경하지 않으려면 GMP에 대한 NULL 종료 문자열을 얻기 위해 중간 버퍼를 읽을 필요가있을 것입니다.

이 방법은 올바르게 구현하기가 쉽지 않지만 다시 한번 이것은 특히 쉬운 문제는 아닙니다. 이 방법은 GMP가 메모리에서 수행하는 작업을 정확히 반영하므로 알고리즘이 잘 알려져 있다는 장점이 있습니다.