가장 빠른 128 비트 정수 라이브러리

Question

나는 CPU가 많은 수치 계산 응용 프로그램을 만들고 있습니다. 많은 세부 사항에 빠지지 않고, 큰 정수 x에 대해 특정 함수 f (x)를 계산하는 계산 수학 연구 프로젝트입니다.

현재 모든 것이 64 비트 int를 사용하여 x64 모드에서 C++로 구현됩니다. 그건 나를2^64 ~ 1.8 * 10^19로 제한합니다. 더 멀리 가고 싶습니다. 128 비트 산술을하는 라이브러리가 필요합니다. 그리고 그것은 매우 빨라야합니다. 특히, 정수 나누기가 빠릅니다. 그렇지 않으면 나는 추수 감사절까지 결과를 기다리고 여기 앉아있을 것이다. 그리고 나는 바퀴를 재발 명하지 않을 것입니다.

위키 피 디아에서 ~ 20 개의 큰 정수 라이브러리 목록을 찾았지만 그 중 대부분은 임의의 정밀도 숫자를 대상으로 한 것 같습니다. 이는 과도한 작업으로 인해 부담 스럽지만 추가 비용은 들지 않습니다.

128 비트 정수에서 가장 빠르게 작동 할 수있는 라이브러리를 아는 사람이 있습니까?

Answer 1

플랫폼/이식성 요구 사항을 언급하지 않았습니다. gcc 또는 clang을 기꺼이 사용하려는 경우 64 비트 플랫폼에서 무료로 제공되는 128 비트 유형이 내장되어 있습니다 (__uint128_t 및 __int128_t). 어쩌면 다른 플랫폼은 비슷한 유형 확장을 가질 수 있습니다.

어쨌든 폭 N의 두 정수를 조합하여 2N의 정수 하나를 합성하는 gcc 소스에서 해당하는 일반 코드를 찾을 수 있어야합니다. 이러한 목적을 위해 독립형 라이브러리를 만드는 것이 좋은 출발점이 될 것입니다.

Answer 2

이것은 모두에게 도움이되지는 않지만 소스 코드와 함께 가장 적합한 성능의 임의의 정수 라이브러리를 선택하고 작업에 적합하며 고정 된 정수 크기로 해킹하는 것입니다. 일부 변수 "nbits"를 128 개의 하드 코드로 변경하십시오. 그때까지는 바이트 수를 모르는 상태로 런타임에 메모리를 할당합니다. 데이터를 읽을 때마다 역 참조하는 포인터를 저장하여 내부에서 데이터와 함께 struct를 사용하도록 변경합니다. 수작업으로 특정 치명적 루프를 실행하십시오. 위험 할 수있는 다른 것을 하드 코딩하십시오. 그렇다면 컴파일러는 일을 최적화하는 데 더 쉬운 시간을 가질 것입니다. 물론이 중 많은 부분이 이번 주에 어떤 기술이 사용되던간에 멋진 SIMD를 사용하여 어셈블리 될 것입니다.

재미있을 것입니다! 그러나 프로그래머로서 나는 기계 코드와 매우 낮은 수준의 것들로 시작했다.

하지만 내가 사용하는 라이브러리 중 하나는 템플릿을 사용하거나 특정 크기의 코드를 생성하는 몇 가지 방법이 있습니다. 그리고 일부 컴파일러는 "long long"정수형을 사용하기도합니다.

Answer 3

ttmath 라이브러리는 원하는대로 처리합니다.