정수 나누기를 가장 빨리하는 방법은 무엇입니까?

Question

구성표를 사용하여 다음 기능을 사용할 필요가 있습니다.

(define safe-div 
    (lambda (num denom safe) 
    (if (zero? denom) 
     safe 
     (div num denom)))) 

그러나,이 기능이 매우 자주 호출되고) 지혜로운 충분히 (속도를 수행하지 않음) (모든 인수는 자연수 [0, inf를하다). 원하는 동작 (num과 denom의 정수 나누기, denom이 0 인 경우 안전 값 반환)을 구현하는보다 효율적인 방법이 있습니까?

주 Chez Scheme을 사용하고 있습니다 만, 이것은 Chez가 아닌 rnrs 만 가져 오는 라이브러리에서 사용되고 있습니다.

Answer 1

최대 성능을 얻으려면 가능한 한 실리콘에 가깝게해야합니다. 이런 안전 점검을 추가하는 것은 계획 시스템에 의해 매우 효율적인 기계 코드로 적시에 컴파일되지 않는 한 그렇게하지 않을 것입니다.

두 가지 옵션이 있습니다. 하나는 C (또는 어셈블리)에서 기본 (즉, foreign) 구현을 생성하고이를 호출하는 것입니다. 그것은 람다로 패키징하는 것과 호환되지 않을 수도 있지만, 다시 한번 람다의 동적 특성은 표기법의 효율성으로 이어지지 만 반드시 런타임 효율성으로 이어지지는 않습니다. (함수 포인터를 제외하고, 람다 표현식이 C로 존재하지 않는 이유는 여러 해가 더 오래 되었음에도 불구하고 그렇습니다.)이 경로를 사용한다면 한 걸음 뒤로 물러나고 더 큰 처리가 안전 div인지 확인하는 것이 가장 좋습니다. 부분은 원시로 가져와야합니다. 주변의 모든 것이 여전히 느린 경우 루프의 중심에있는 분할 속도를 높이는 데는 거의 요점이 없습니다.

0으로 나누는 것이 거의 없다고 가정하면 다른 방법은 div을 사용하고 구현이 빠름을 기대하는 것입니다. 네, 이것은 제로로 나눌 수 있지만 속도가 올 때, 용서를 구하는 것이 허락을 구하는 것보다 때로는 더 좋습니다. 즉, 부서 앞의 검사를 건너 뛰고 그냥하십시오. 실패하면 계획 런타임이 0 오류로 나누기를 catch하고 exception handler을 설치할 수 있습니다. 예외적 인 경우 코드가 느리고 일반 경우는 빠릅니다. 바라건대이 트레이드 오프는 성과를 내기 위해 노력합니다.

마지막으로, 나누는 대상에 따라 실제 분배를 수행하는 것보다 역수를 곱하는 것이 더 빠를 수도 있습니다. 이를 위해서는 빠른 상호 계산이 필요하거나 이전 계산을 수정하여 직접 역수를 산출해야합니다. 정수를 다루기 때문에, 역수는 본질적으로 2^32 * 1/denom 인 고정 소수점에 저장됩니다. 이 값에 num을 곱하고 오른쪽으로 32 비트 씩 이동하여 몫을 얻습니다. 요즘은 프로세서가 단일 사이클 곱하기 명령어를 사용하지만 칩에서 루프가 실행되므로 프로세서가 훨씬 느려지므로이 방법이 유리합니다. 이것은 당신의 필요에 과잉 될 수 있지만, 어느 시점에서 유용 할 수 있습니다.