하드웨어가 모듈러스 또는 나눗셈 연산을 지원하지 않으면 소프트웨어에 의한 모듈러스 / 나눗셈을 시뮬레이션하기 위해 더 많은 CPU 사이클이 필요합니다. 피연산자가 10 인 경우 나누기와 계수를 계산하는 더 빠른 방법이 있습니까?
내 프로젝트에서 종종 정수 계수 10을 계산해야합니다. 특히 PIC16F에서 작업하고 있으며 LCD에 숫자를 표시해야합니다. 지원할 4 자리 숫자가 있으므로 모듈러스와 나누기 함수 (소프트웨어 구현)에 대한 4 개의 호출이 있습니다. 즉 다음과 같습니다.
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
유사한 코드를 사용하는 다른 영역이 있습니다.
답변
여기 몇 년 전에 사용 된 이진 대 BCD 알고리즘이 있습니다 . 외부 BCD에서 7 세그먼트 디스플레이 드라이버를 사용하여 결과를 출력을 위해 압축 BCD로 직접 적절한 포트에 쓸 수있었습니다.
PIC에 하드웨어 멀티 플라이어가 있으면 PIC18F97J60을 사용하고 있다면 상당히 빠릅니다. PIC에 하드웨어 멀티 플라이어가 없으면 곱셈에 shift + add를 사용하십시오.
이것은 부호없는 16 비트 int를 취하고 5 자릿수의 압축 된 BCD를 반환하며 4 자릿수보다 빠르게 수정할 수 있습니다. 시프트 + 덧셈을 사용하여 약 10으로 나눈 값이지만 제한된 입력 범위가 주어지면이 용도에 정확합니다. 결과 사용 방식에 맞춰 결과를 다르게 포장 할 수도 있습니다.
void intToPackedBCD( uint16_t n, uint8_t *digits ) {
uint8_t d4, d3, d2, d1, d0, q; //d4 MSD, d0 LSD
d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;
d0 = 6*(d3 + d2 + d1) + (n & 0xF);
q = (d0 * 0xCD) >> 11;
d0 = d0 - 10*q;
d1 = q + 9*d3 + 5*d2 + d1;
q = (d1 * 0xCD) >> 11;
d1 = d1 - 10*q;
d2 = q + 2*d2;
q = (d2 * 0x1A) >> 8;
d2 = d2 - 10*q;
d3 = q + 4*d3;
d4 = (d3 * 0x1A) >> 8;
d3 = d3 - 10*d4;
digits[0] = (d4<<4) | (d3);
digits[1] = (d2<<4) | (d1);
digits[2] = (d0<<4);
}
답변
부호없는 정수를 가정하면 나누기와 곱셈은 비트 시프트에서 형성 될 수 있습니다. 그리고 (정수) 나눗셈과 곱셈에서 모듈로가 도출 될 수 있습니다.
10을 곱하려면 :
y = (x << 3) + (x << 1);
10으로 나누는 것이 더 어렵습니다. 여러 분할 알고리즘을 알고 있습니다. 올바르게 기억한다면 비트 시프트와 빼기를 사용하여 빠르게 10으로 나눌 수있는 방법이 있지만 정확한 방법을 기억할 수는 없습니다. 이것이 사실이 아닌 경우, 이것은 <130 cycles를 관리하는 나누기 알고리즘입니다 . 사용중인 마이크로가 확실하지 않지만 이식 해야하는 경우에도 어떤 식 으로든 사용할 수 있습니다.
편집 : 누군가 가 스택 오버 플로우 에서 약간의 오류를 허용하고 큰 임시 레지스터를 가질 수 있다고 말하면 다음 과 같이 작동합니다.
temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10
나누기와 곱셈이 있다고 가정하면 모듈로는 간단합니다.
mod = x - ((x / z) * z)
답변
double dabble 알고리즘을 사용하여 나누지 않고 바이너리에서 압축 된 BCD로 변환 할 수 있습니다 . shift 와 add 3 만 사용합니다 .
예를 들어 243 10 = 11110011 2 를 이진수 로 변환
0000 0000 0000 11110011 Initialization
0000 0000 0001 11100110 Shift
0000 0000 0011 11001100 Shift
0000 0000 0111 10011000 Shift
0000 0000 1010 10011000 Add 3 to ONES, since it was 7
0000 0001 0101 00110000 Shift
0000 0001 1000 00110000 Add 3 to ONES, since it was 5
0000 0011 0000 01100000 Shift
0000 0110 0000 11000000 Shift
0000 1001 0000 11000000 Add 3 to TENS, since it was 6
0001 0010 0001 10000000 Shift
0010 0100 0011 00000000 Shift
2 4 3
BCD
이 알고리즘은 사용 가능한 하드웨어 제수가없는 경우 매우 효율적입니다. 왼쪽 시프트 만 1 이상 사용하므로 배럴 시프터를 사용할 수없는 경우에도 빠릅니다.
답변
필요한 자릿수에 따라 무차별 대입 방법 ( d-입력 번호 t–출력 ASCII 문자열) 을 사용할 수 있습니다 .
t--;
if (d >= 1000) t++; *t = '0'; while (d >= 1000) { d -= 1000; *t += 1; }
if (d >= 100) t++; *t = '0'; while (d >= 100) { d -= 100; *t += 1;}
if (d >= 10) t++; *t = '0'; while (d >= 10) { d -= 10; *t += 1;}
t++; *t = '0' + d;
곱셈이나 룩업 테이블에서 얻은 10의 거듭 제곱으로 여러 if를 루프로 변경할 수도 있습니다.
답변
이 애플리케이션 노트 는 바이너리에서 BCD로 또는 그 반대로의 변환을 포함하여 BCD 산술 알고리즘을 설명합니다. Appnote는 AVR 인 Atmel의 설명이지만, 설명 된 알고리즘은 프로세서에 독립적입니다.
답변
나는 정답이 없지만 자매 사이트 스택 오버플로에 대해 정확히 동일한 나눗셈 및 모듈로 최적화 주제에 대해 큰 토론이 있습니다.
조회 테이블을 구현하기에 충분한 메모리가 있습니까?
해커 딜라이트는 최적의 분할 알고리즘에 관한 논문 을 가지고 있습니다.
답변
이진 값으로 해당 값을 보유하고 필요에 따라 BCD로 변환하는 대신, 단순 특수 “BCD 증가”및 “BCD 추가”서브 루틴을 사용하여 항상 해당 값을 BCD로 유지하는 것을 고려 했습니까? 바이너리에서 BCD로 “서브 루틴)?
한 번에 모든 컴퓨터는 모든 데이터를 10 진수 (10 개 위치 기어, 5 개 중 2 개 코드 진공 튜브, BCD 등)로 저장했으며 오늘날에도 여전히 레거시가 남아 있습니다. ( 실시간 클록 칩이 BCD를 사용하는 이유 참조 ).