문제

저는 빠른 정수 연산 기능을 갖춘 마이크로프로세서용 코드를 작성하고 있습니다. 그렇게 빠르지는 않아 부동 연산.정수를 1부터 9까지의 숫자로 나누고 결과를 다시 정수로 변환해야 합니다.

0, 1, 0.5, 0.3333 등과 같은 멤버로 부동 소수점 배열을 만들었습니다.하지만 (1/3)을 제외한 숫자에 대한 MAGIC 상수(예: 0x55555556)가 있다고 생각합니다.

이 숫자는 무엇입니까?

도움이 되었습니까?

해결책

마이크로 컨트롤러의 디비전 명령이 충분히 빠르면 사용하십시오. 결과의 분수 부분이 필요한 경우 나머지를 사용할 수 있습니다. 대부분의 아키텍처에서, 디비전 명령어는 몫을 한 레지스터에, 나머지는 다른 레지스터에 넣습니다.

디비전 명령이 빠르지 않지만 곱셈 명령이 있다면 다음 기술을 사용할 수 있습니다 (그리고 이것이 당신이 따르는 기술인 것처럼 들립니다). 대부분의 아키텍처에서 32 비트 수를 다른 32 비트 수를 곱하면 64 비트 결과가 발생합니다. 더 중요한 절반은 한 레지스터에 저장되고 절반은 다른 절반에 저장됩니다. 숫자 n으로 분할이 (2^32)/n을 곱한 다음 더 중요한 32 비트의 결과를 얻는 것과 동일하다는 사실을 실현하여이를 악용 할 수 있습니다. 다시 말해, 3으로 나누려면 대신 0x1000000/3 = 0x55555555를 곱한 다음 32 비트의 결과를 얻을 수 있습니다.

당신이 여기서하고있는 일은 실제로 고정 점 산술의 형태입니다. 살펴보십시오 위키 백과 기사 자세한 내용은.

다른 팁

정수 상수에 의한 정수의 분할은 시프트와 곱셈의 조합으로 대체 될 수 있습니다. 보다 이 최적화 안내서 자세한 내용은. 코스의 이것은 관심있는 칩에서 더 빠른 경우에 유용합니다.

마이크로 컨트롤러 태그를 기반으로 빠른 정수 나누기가 없다고 가정합니다.내 대답은 부호 없는 값에도 적용됩니다. 부호 있는 값에도 작동합니다. 아래의 까다로운 비트에 사용되는 숫자를 제한하면 됩니다.

좋은 시작은 2, 4, 8로 나누는 것입니다.CPU에 논리적 오른쪽 시프트 명령이 있다고 가정하면 각각 1, 2, 3비트의 오른쪽 시프트로 이러한 작업을 수행할 수 있습니다.

둘째, 1로 나누는 것은 숫자를 그대로 유지하는 것입니다.그러면 3, 5, 6, 7, 9가 남습니다.

까다로운 비트는 여기서 시작됩니다.

다른 숫자의 경우 나누기가 곱셈 및 이동으로 대체될 수 있다는 사실을 이용할 수 있습니다.

16비트 프로세서가 있다고 가정해 보겠습니다.N으로 나누려면 256/N을 곱하고 오른쪽으로 8비트 이동합니다.

N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28

72/5의 임의의 예를 들어보겠습니다.72에 51을 곱하면 3672가 되고 오른쪽으로 8비트 이동하면 14가 됩니다.

이것이 작동하려면 사용 중인 숫자가 16비트를 초과해서는 안 됩니다.최악의 경우는 85를 곱하는 것이므로 최대 771까지 숫자를 처리할 수 있습니다.

이것이 작동하는 이유는 8비트의 오른쪽 시프트가 256으로 나누는 것과 동일하기 때문입니다.

  m * (256 /  n) / 256
= m / (n /  256) / 256
= m /  n *  256  / 256
= m /  n * (256  / 256)
= m /  n

32비트 프로세서를 사용하는 경우 65536/N이므로 값과 범위가 다소 변경됩니다.

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by  9,363.
N = 9, multiply by  7,282.

이번에도 무작위로 20,000 / 7을 선택해 보겠습니다.20,000에 9,363을 곱하면 187,260,000이고, 16비트를 오른쪽으로 이동하면 2,857이 됩니다. 실제 결과는 2,857입니다.

다음 C 테스트 프로그램은 주어진 값에 대한 정확도 수치를 보여줍니다.부호 있는 값을 사용하므로 최대 약 98,000까지만 유효하지만 가장 큰 오류는 1이고 가장 낮은 지점인 13,110(단지 0.008% 오류)에서 발생한다는 것을 알 수 있습니다.

#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
    int n, i;
    for (n = 0; n < 98000; n++) {
        for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
            int r1 = n / da[i];
            int r2 = (n * ma[i])>>16;
            int dif = abs (r1-r2);
            if (dif >= 5) {
                printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
                return 1;
            }
            res[dif]++;
            if (low[dif] == -1) {
                low[dif] = n;
            }
        }
    }
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
        printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
    }
    return 0;
}

이는 다음을 출력합니다:

Difference of 0: 335874, lowest value was      0
Difference of 1: 154126, lowest value was  13110
Difference of 2:      0, lowest value was     -1
Difference of 3:      0, lowest value was     -1
Difference of 4:      0, lowest value was     -1
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top