C에서 다중 단어 추가

Question

저는 gcc의 __uint128_t을 사용하는 C 프로그램을 가지고 있습니다. 그러나 이제는 내 요구가 그 이상으로 커졌습니다. 196 또는 256 비트의 고속 산술에 대한 내 옵션은 무엇입니까? 내가 필요한 유일한 연산은 덧셈입니다 (그리고 캐리 비트가 필요 없습니다. 즉 mod 2^192 또는 2^256을 사용할 것입니다).

속도가 중요하므로 가능하면 일반적인 다중 정밀도로 이동하고 싶지 않습니다. (실제로 내 코드는 일부 장소에서 다중 정밀도를 사용하지만 중요한 루프에 있으며 수십억 번 실행됩니다. 지금까지 다중 정밀도는 수만 번 실행해야합니다.

어쩌면 여기에 있습니다. 코드를 직접 작성하기에 충분히 간단하거나 어쩌면 적절한 라이브러리를 찾아야합니다. 당신의 조언은 무엇입니까, 위대한 StackOverflow?

설명 : GMP가 내 요구에 비해 너무 느립니다. 내 코드에서 실제로 다중 정밀도를 사용하지만 내부 루프가 아니며 10 ~ 5 배 미만으로 실행됩니다. 핫 루프는 10^12 번과 비슷합니다. 다중 코드 부분이 단 정밀도보다 자주 실행되도록 코드를 변경 (크기 매개 변수 증가)했을 때 100 배의 속도 저하가있었습니다 (주로 여분의 μops가 아닌 메모리 관리 문제로 인해). 나는 그것을 4 배의 감속 또는 그 이상으로 낮추고 싶다.

Answer 1

256 비트 루프에서 그것을 여러 번 사용하는 경우 버전

__uint128_t a[2], b[2], c[2]; // c = a + b 
c[0] = a[0] + b[0]; 
c[1] = a[1] + b[1] + (c[0] < a[0]); 

당신이 SIMD에 의해 평행하고

편집 멀티 스레딩 고려해야한다 : 192 비트 버전. 이 방법은 같은 128 비트 비교를 제거 할 수있는 @ 해롤드의 진술 :

struct __uint192_t { 
    __uint128_t H; 
    __uint64_t L; 
} a, b, c; // c = a + b 
c.L = a.L + b.L; 
c.H = a.H + b.H + (c.L < a.L); 

Answer 2

this answer에서 -technique "캐리을 시뮬레이션 (low < oldlow)을 추가"경우 테스트 할 수는 빠른 충분하다. low이 여기에 __uint128_t 인 코드 생성을 해칠 수 있으므로 약간 복잡합니다. 당신도 4 uint64_t의 그것으로 시도 할 수 있습니다, 나는 그것이 더 좋든 나쁘 든간에 나는 모른다.

충분하지 않다면 인라인 어셈블리로 내려 가서 직접 캐리 플래그를 사용하십시오. 그보다 더 좋아지지는 않지만 인라인 어셈블리를 사용할 때의 단점이 있습니다.