특수 소수의 부동 소수점 모듈러스를 취하는 Fast, Vectorizable 메서드?

Question

부동 소수점의 모듈러스를 취하는 빠른 방법이 있습니까?

정수에는 메르 센 소수의 트릭이 있으므로 나눗셈없이 y = x MOD 2^31-1을 계산할 수 있습니다. integer trick

부동 소수점 숫자에 유사한 트릭을 적용 할 수 있습니까?

벡터/SIMD 연산으로 변환하거나 GPGPU 코드로 옮길 수있는 방식으로하는 것이 바람직합니다. 이는 부동 소수점 데이터에 대한 정수 계산을 사용하지 않습니다.

관심있는 소수는 2^7-1 및 2^31-1이 될 수 있습니다. 그러나 부동 소수점 숫자가 더 효율적인 경우 그 값은 환영받을 수 있습니다.

이 알고리즘의 한 가지 용도는 입력 부동 소수점 숫자가 알고리즘으로 읽혀질 때 실행중인 "체크섬"을 계산하는 것입니다. 너무 많은 계산 기능을 사용하지 않으려면이 가벼운 것을 유지하고 싶습니다.

큰 숫자, 특히 2^127-1에 대해서는 비슷한 기술이 사용됩니다. 불행히도 종이의 수학은 나를 넘어서서 더 작은 소수로 변환하는 방법을 찾을 수 없었습니다. Example of floating point MOD 2^127 - 1 - HASH127

Answer 1

나는 DJB의 논문에서보고, 31 비트는 53 비트 정밀도 이중 유효 숫자에 편안하게 맞는 때문에 당신은 그것을 쉽게 있습니다. 체크섬이 Z/(2 ** 31-1)에 대한 링 연산으로 구성된다고 가정하면 x mod Z/(2 ** 31 - 1)의 작은 대표 연산을 풀 때의 편안한 문제를 해결하는 것이 더 쉽고 빠릅니다. 1); 결국 정수 연산을 사용하여 속도가 느리지 만 너무 자주 발생하지 않는 표준 캐시를 찾을 수 있습니다.

기본 감소 단계는 정수 x = y + 2 ** 31 * z를 y + z로 바꾸는 것입니다. DJ가 사용하는 트릭은 w = (x + L) - L을 계산하는 것입니다. 여기서 L은 z = 2 ** - 31 * w와 같은 방식으로 라운드 오프를 유도하기 위해주의 깊게 선택된 큰 정수입니다. 그런 다음 y = x - w 및 y + z를 출력하십시오. 크기는 최대 2 ** 32입니다. (이 작업이 충분하지 않은 경우 사과 드리며, 그렇다면 체크섬 알고리즘을 게시하십시오.)

L의 선택에는 유효 숫자의 정확성에 대한 정보가 포함됩니다. 모듈러스 2 ** 31 - 1에 대해 우리는 최소 정밀도 (ulp)가 2 ** 31 인 단위를 원합니다. 범위 [1.0, 2.0]의 복식의 경우 ulp는 2 ** - 52이므로 L은 2 ** 52 * 2 ** 31이어야합니다. 계수 2 ** 7 - 1로 이것을 수행한다면 L = 2 ** 52 * 2 ** 7이됩니다. djb 메모로,이 트릭은 중급 결과에 결정적인 영향을받습니다. 은 더 높은 정밀도로 계산됩니다.