빠른 분할 테스트(2,3,4,5,...,16)?
가장 빠른 분할 테스트는 무엇입니까?예를 들어, 리틀 엔디언 아키텍처와 32비트 부호 정수를 고려할 때, 어떻게 숫자를 2,3,4,5,... 16까지 나눌 수 있는지 매우 빠르게 계산할 수 있을까요?
경고: 지정된 코드는 예제일 뿐입니다.모든 라인이 독립적입니다!모듈로 작동을 사용하는 명백한 솔루션은 많은 ARM과 마찬가지로 DIV 하드웨어가 없는 많은 프로세서에서 느립니다.일부 컴파일러는 또한 이러한 최적화를 수행할 수 없습니다(예: 제수가 함수의 인수이거나 어떤 것에 의존하는 경우).
Divisible_by_1 = do();
Divisible_by_2 = if (!(number & 1)) do();
Divisible_by_3 = ?
Divisible_by_4 = ?
Divisible_by_5 = ?
Divisible_by_6 = ?
Divisible_by_7 = ?
Divisible_by_8 = ?
Divisible_by_9 = ?
Divisible_by_10 = ?
Divisible_by_11 = ?
Divisible_by_12 = ?
Divisible_by_13 = ?
Divisible_by_14 = ?
Divisible_by_15 = ?
Divisible_by_16 = if(!number & 0x0000000F) do();
및 특수한 경우:
Divisible_by_2k = if(number & (tk-1)) do(); //tk=2**k=(2*2*2*...) k times
모든 경우(2로 나눗셈 포함):
if (number % n == 0) do();
그리고 하위 비트의 마스크를 사용하는 것은 난독화일 뿐이며, 현대 컴파일러를 사용하는 것은 읽을 수 있는 방식으로 코드를 작성하는 것보다 더 빠르지는 않을 것입니다.
이 모든 경우를 , 여러분은 를 모든사례하경일우사다부추음례다수있성니습향킬상시능가을여하에를를는테스야트해▁▁putting▁some▁performance▁by▁if▁improve▁in다▁of▁you▁cases▁all니있습▁the▁might,수▁of▁cases▁you모▁the든에 넣음으로써 성능을 향상시킬 수도 있습니다.if다른 예를 들어, 2에 의한 분할이 이미 실패한 경우 4에 의한 분할을 테스트하는 것은 의미가 없습니다.
분할 명령(x86/x64의 모듈로 포함)에 대한 대안을 찾는 것은 매우 느리기 때문에 전혀 나쁘지 않습니다.대부분의 사람들이 인식하는 것보다 느림(또는 훨씬 더 느림).n이 변수인 %n을 제안하는 사람들은 항상 나눗셈 명령을 사용하게 되므로 어리석은 조언을 하고 있습니다.반면에 %c(여기서 c는 상수)는 컴파일러가 레퍼토리에서 사용할 수 있는 최상의 알고리즘을 결정할 수 있도록 합니다.때때로 그것은 분할 명령이 될 것이지만 많은 경우 그렇지 않을 것입니다.
이 문서에서 Torbjörn Granlund는 서명되지 않은 32비트 mults:divs에 필요한 클럭 주기의 비율이 Sandybridge의 경우 4:26(6.5x)이고 K10의 경우 3:45(15x)이며 64비트의 경우 각각 4:92(23x)와 5:77(14.4x)입니다.
"L" 열은 지연 시간을 나타냅니다."T" 열은 처리량을 나타냅니다.이는 프로세서가 여러 명령을 병렬로 처리할 수 있는 능력과 관련이 있습니다.Sandybridge는 매 주기마다 하나의 32비트 곱셈을 실행하거나 매 주기마다 하나의 64비트 곱셈을 실행할 수 있습니다.K10의 경우 해당 처리량은 반대입니다.분할의 경우, K10은 다른 시퀀스를 시작하기 전에 전체 시퀀스를 완료해야 합니다.나는 샌디브릿지도 마찬가지라고 생각합니다.
K10을 예로 들어보면 32비트 분할(45)에 필요한 주기 동안 동일한 수의 곱셈(45)이 실행될 수 있으며 분할이 완료된 후 마지막과 마지막 중 하나가 클럭 주기 1과 2를 완료합니다.많은 작업을 45배로 수행할 수 있습니다.
또한 32비트 및 64비트의 경우 K8-K9에서 K10으로 진화하면서 div의 효율성이 39에서 45로, 71에서 77로 감소했다는 점도 흥미롭습니다.
gmplib.org 과 스톡홀름 왕립 공과대학교의 Granlund 페이지에는 더 많은 맛있는 것들이 포함되어 있으며, 그 중 일부는 gcc 컴파일러에 통합되었습니다.
@James가 언급했듯이, 컴파일러가 당신을 위해 그것을 단순화하도록 하라. 만약에n는 상수이며, 어떤 괜찮은 컴파일러도 패턴을 인식하고 더 효율적인 동등한 패턴으로 변경할 수 있습니다.
예를 들어, 코드는
#include <stdio.h>
int main() {
size_t x;
scanf("%u\n", &x);
__asm__ volatile ("nop;nop;nop;nop;nop;");
const char* volatile foo = (x%3 == 0) ? "yes" : "no";
__asm__ volatile ("nop;nop;nop;nop;nop;");
printf("%s\n", foo);
return 0;
}
, g++-4.5-O3의 , 관련부, 컴분로일x%3 == 0 될 것입니다.
mov rcx,QWORD PTR [rbp-0x8] # rbp-0x8 = &x
mov rdx,0xaaaaaaaaaaaaaaab
mov rax,rcx
mul rdx
lea rax,"yes"
shr rdx,1
lea rdx,[rdx+rdx*2]
cmp rcx,rdx
lea rdx,"no"
cmovne rax,rdx
mov QWORD PTR [rbp-0x10],rax
다시 C 코드로 번역하면, 그것은
(hi64bit(x * 0xaaaaaaaaaaaaaaab) / 2) * 3 == x ? "yes" : "no"
// equivalatent to: x % 3 == 0 ? "yes" : "no"
(로 여에관사없참습다니은단련기된로고▁(참▁no다▁involved니▁(▁that없note습▁division.)0xaaaaaaaaaaaaaaab == 0x20000000000000001L/3)
편집:
- 마법 상수 0xaaaaaaaaaab은 http://www.hackersdelight.org/magic.htm 에서 계산할 수 있습니다.
- 양식n 2 - 1의 나눗셈기에 대해서는 http://graphics.stanford.edu/ ~seander/bithacks.html#ModulusDivision을 확인하십시오.
정다하추로 합니다.number이라unsigned(32비트).그렇다면 다음은 16까지 분할을 매우 빠르게 계산하는 방법입니다. (측정하지는 않았지만 어셈블리 코드에 그렇게 표시되어 있습니다.)
bool divisible_by_2 = number % 2 == 0;
bool divisible_by_3 = number * 2863311531u <= 1431655765u;
bool divisible_by_4 = number % 4 == 0;
bool divisible_by_5 = number * 3435973837u <= 858993459u;
bool divisible_by_6 = divisible_by_2 && divisible_by_3;
bool divisible_by_7 = number * 3067833783u <= 613566756u;
bool divisible_by_8 = number % 8 == 0;
bool divisible_by_9 = number * 954437177u <= 477218588u;
bool divisible_by_10 = divisible_by_2 && divisible_by_5;
bool divisible_by_11 = number * 3123612579u <= 390451572u;
bool divisible_by_12 = divisible_by_3 && divisible_by_4;
bool divisible_by_13 = number * 3303820997u <= 330382099u;
bool divisible_by_14 = divisible_by_2 && divisible_by_7;
bool divisible_by_15 = number * 4008636143u <= 286331153u;
bool divisible_by_16 = number % 16 == 0;
다에의한관하여에할분에 의한 .d다음 규칙이 적용됩니다.
- 때
d는 22의 입니다.
James Kanze가 지적했듯이, 당신은 다음을 사용할 수 있습니다.is_divisible_by_d = (number % d == 0)를 컴일러이다같음구이영만다리니합큼현할파과것으로 구현할 만큼 합니다.(number & (d - 1)) == 0매우 효율적이지만 난독화되어 있습니다.
, 지만하 때, 제언.d위에 표시된 난독화는 현재 컴파일러가 수행하는 것보다 더 효율적인 것처럼 보입니다. (자세한 내용은 나중에)
- 때
d홀수:
그 기술은 형태를 취합니다.is_divisible_by_d = number * a <= ba그리고.b교묘하게 얻은 상수입니다.필요한 것은 곱셈 1개와 비교 1개뿐입니다.
- 때
d짝수이지만 2의 거듭제곱이 아닙니다.
나서, 리고쓰다를 쓰세요.d = p * qp과 2의 거듭제곱입니다.q홀수이고 언피토닉이 제안한 "볼에 있는 상처"를 사용합니다. 즉,is_divisible_by_d = is_divisible_by_p && is_divisible_by_q곱셈은 다시, 하의의곱셈서나에계 (산오직의)▁againis_divisible_by_q이 수행됩니다.
많은 컴파일러(godbolt를 사용하여 clang 5.0.0, gcc 7.3, icc 18 및 msvc 19를 테스트했습니다)가 교체됩니다.number % d == 0타고(number / d) * d == number그들은 나눗셈을 곱셈과 비트 시프트로 대체하기 위해 영리한 기술을 사용합니다(Olof Forshell의 답변 참조).그들은 결국 두 번의 곱셈을 하게 됩니다.이와 대조적으로 위의 기법은 1회 곱셈만 수행합니다.
2018년 10월 01일 업데이트
위의 알고리즘이 곧 GCC에 제공될 것으로 보입니다(이미 트렁크에 있음).
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853
GCC의 구현은 훨씬 더 효율적으로 보입니다.은 1짝수 2)홀수 분할, 3) 점자의 홀수 부분에 의한 3) 점자의 부분으로 구성되어 있습니다.&&이전 두 단계의 결과를 연결합니다.조립자 지침을 사용하여
표준 C++에서는 효율적으로 사용할 수 없습니다. (ror부분에 한 세 로 묶습니다.), GCC는 홀수 부분에 의한 나눗셈과 유사합니다.좋은 물건!이 구현을 사용할 수 있게 되면 (명확성과 성능 모두를 위해) 다시 사용하는 것이 좋습니다.%
업데이트 05-2020년 5월
이 주제에 대한 제 기사가 출판되었습니다.
빠른 모듈러 계산(Part 1), 오버로드 저널 154, 2019년 12월 11-15페이지
빠른 모듈러 계산(Part 2), 과부하 저널 155, 2020년 2월 14-17페이지
빠른 모듈러 계산(Part 3), 과부하 저널 156, 2020년 4월 10-13페이지
약간의 농담이지만, 당신이 나머지 답을 얻었다고 가정하면:
Divisible_by_6 = Divisible_by_3 && Divisible_by_2;
Divisible_by_10 = Divisible_by_5 && Divisible_by_2;
Divisible_by_12 = Divisible_by_4 && Divisible_by_3;
Divisible_by_14 = Divisible_by_7 && Divisible_by_2;
Divisible_by_15 = Divisible_by_5 && Divisible_by_3;
먼저 이진법의 bn...b2b1b0 형식의 숫자는 다음과 같은 값을 갖습니다.
number = bn*2^n+...+b2*4+b1*2+b0
자, 여러분이 숫자%3을 말할 때, 여러분은 다음을 가지고 있습니다:
number%3 =3= bn*(2^n % 3)+...+b2*1+b1*2+b0
(정합 모듈로 3을 나타내기 위해 =3=를 사용했습니다.) 또한참은 다음과 같습니다.b1*2 =3= -b1*1
이제 + 및 -와 곱셈을 사용하여 16개의 모든 눈금을 작성하겠습니다(곱셈은 다른 위치로 이동된 시프트 또는 동일한 값의 합으로 작성될 수 있음).를 들어 를들면입니다.5*x은 단입니다.x+(x<<2)이 는위하치를 계산하는 것.x 번만
그번호전요화해로▁the요전해로 부르자.n리고예를그를예고▁and's.Divisible_by_i부울 값입니다.중간값으로, 상상해 보세요.Congruence_by_i는 와일하 값니다입는에 입니다.ni.
또한, 이렇게 말하죠.n00 n, n 트 비 0 의 합 니 다미을의▁bit다를 의미합니다.n11 등,즉 1 등의 1 미니다합즉비▁bit,즉▁1,를 의미합니다.
ni = (n >> i) & 1;
Congruence_by_1 = 0
Congruence_by_2 = n&0x1
Congruence_by_3 = n0-n1+n2-n3+n4-n5+n6-n7+n8-n9+n10-n11+n12-n13+n14-n15+n16-n17+n18-n19+n20-n21+n22-n23+n24-n25+n26-n27+n28-n29+n30-n31
Congruence_by_4 = n&0x3
Congruence_by_5 = n0+2*n1-n2-2*n3+n4+2*n5-n6-2*n7+n8+2*n9-n10-2*n11+n12+2*n13-n14-2*n15+n16+2*n17-n18-2*n19+n20+2*n21-n22-2*n23+n24+2*n25-n26-2*n27+n28+2*n29-n30-2*n31
Congruence_by_7 = n0+2*n1+4*n2+n3+2*n4+4*n5+n6+2*n7+4*n8+n9+2*n10+4*n11+n12+2*n13+4*n14+n15+2*n16+4*n17+n18+2*n19+4*n20+n21+2*n22+4*n23+n24+2*n25+4*n26+n27+2*n28+4*n29+n30+2*n31
Congruence_by_8 = n&0x7
Congruence_by_9 = n0+2*n1+4*n2-n3-2*n4-4*n5+n6+2*n7+4*n8-n9-2*n10-4*n11+n12+2*n13+4*n14-n15-2*n16-4*n17+n18+2*n19+4*n20-n21-2*n22-4*n23+n24+2*n25+4*n26-n27-2*n28-4*n29+n30+2*n31
Congruence_by_11 = n0+2*n1+4*n2+8*n3+5*n4-n5-2*n6-4*n7-8*n8-5*n9+n10+2*n11+4*n12+8*n13+5*n14-n15-2*n16-4*n17-8*n18-5*n19+n20+2*n21+4*n22+8*n23+5*n24-n25-2*n26-4*n27-8*n28-5*n29+n30+2*n31
Congruence_by_13 = n0+2*n1+4*n2+8*n3+3*n4+6*n5-n6-2*n7-4*n8-8*n9-3*n10-6*n11+n12+2*n13+4*n14+8*n15+3*n16+6*n17-n18-2*n19-4*n20-8*n21-3*n22-6*n3+n24+2*n25+4*n26+8*n27+3*n28+6*n29-n30-2*n31
Congruence_by_16 = n&0xF
또는 인수 분해된 경우:
Congruence_by_1 = 0
Congruence_by_2 = n&0x1
Congruence_by_3 = (n0+n2+n4+n6+n8+n10+n12+n14+n16+n18+n20+n22+n24+n26+n28+n30)-(n1+n3+n5+n7+n9+n11+n13+n15+n17+n19+n21+n23+n25+n27+n29+n31)
Congruence_by_4 = n&0x3
Congruence_by_5 = n0+n4+n8+n12+n16+n20+n24+n28-(n2+n6+n10+n14+n18+n22+n26+n30)+2*(n1+n5+n9+n13+n17+n21+n25+n29-(n3+n7+n11+n15+n19+n23+n27+n31))
Congruence_by_7 = n0+n3+n6+n9+n12+n15+n18+n21+n24+n27+n30+2*(n1+n4+n7+n10+n13+n16+n19+n22+n25+n28+n31)+4*(n2+n5+n8+n11+n14+n17+n20+n23+n26+n29)
Congruence_by_8 = n&0x7
Congruence_by_9 = n0+n6+n12+n18+n24+n30-(n3+n9+n15+n21+n27)+2*(n1+n7+n13+n19+n25+n31-(n4+n10+n16+n22+n28))+4*(n2+n8+n14+n20+n26-(n5+n11+n17+n23+n29))
// and so on
이러한 값이 음수가 되면 다음과 같이 추가합니다.i그들이 양성이 될 때까지.
할 은 방금 과 같은 이하는 것입니다.Congruence_by_i 작집니다아보다 .i 분명히).>= 0이것은 우리가 숫자의 나머지를 3이나 9로 찾고 싶을 때 하는 것과 비슷합니다. 기억나세요?숫자를 합합니다. 숫자가 두 개 이상이면 일부는 한 자리만 얻을 때까지 결과의 숫자를 다시 합합니다.
, 이제 은음다입니다.i = 1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16:
Divisible_by_i = (Congruence_by_i == 0);
그리고 나머지는:
Divisible_by_6 = Divisible_by_3 && Divisible_by_2;
Divisible_by_10 = Divisible_by_5 && Divisible_by_2;
Divisible_by_12 = Divisible_by_4 && Divisible_by_3;
Divisible_by_14 = Divisible_by_7 && Divisible_by_2;
Divisible_by_15 = Divisible_by_5 && Divisible_by_3;
편집: 일부 추가 사항은 처음부터 피할 수 있습니다.를 들어 를들면입니다.n0+2*n1+4*n2는 와동합다니와 .n&0x7로, 하게유사게▁similarlyn3+2*n4+4*n5이라(n>>3)&0x7따라서 각 공식을 사용하면 각 비트를 개별적으로 얻을 필요가 없습니다. 작동의 명확성과 유사성을 위해 그렇게 썼습니다.각 공식을 최적화하려면 사용자가 직접 작업해야 합니다. 즉, 피연산자를 그룹화하고 작업을 요인화해야 합니다.
이 숫자들의 LCM은 720720인 것 같습니다.매우 작기 때문에 단일 계수 연산을 수행하고 나머지를 사전 계산된 LUT의 인덱스로 사용할 수 있습니다.
(i % N) == 0을 검정으로 사용해야 합니다.
내 컴파일러(상당히 오래된 버전의 gcc)는 내가 시도한 모든 경우에 대해 좋은 코드를 생성했습니다.비트 테스트가 적절한 경우에는 그렇게 했습니다.N이 상수인 경우, 어떤 경우에도 명백한 "분할"을 생성하지 않고 항상 일부 "꼼수"를 사용했습니다.
컴파일러가 당신을 위해 코드를 생성하게 하면, 그것은 당신이 하는 것보다 기계의 구조에 대해 거의 확실히 더 많이 알게 될 것입니다 :) 그리고 이것들은 컴파일러가 하는 것보다 더 나은 것을 생각하지 않는 쉬운 최적화입니다.
하지만 흥미로운 질문입니다.다른 컴퓨터에서 컴파일해야 하기 때문에 각 상수에 대해 컴파일러가 사용하는 트릭을 나열할 수 없습니다.하지만 아무도 나를 이기지 못하면 나중에 이 답장을 업데이트할 것입니다 :)
이것은 아마도 코드에서 도움이 되지 않을 것이지만, 어떤 경우에는 머리 속에서 이것을 할 수 있도록 도와주는 깔끔한 속임수가 있습니다.
3으로 나누기: 10진수로 표시된 숫자의 경우 모든 숫자를 합하여 3으로 나누기가 가능한지 확인할 수 있습니다.
예:12345 => 1+2+3+4+5 = 15 => 1+5 = 6은 33 로 나 수 있 는 눌 으 는 있▁3로 나눌 수 있습니다.(3 x 4115 = 12345).
더 흥미로운 것은 X-1의 모든 요인에 대해 동일한 기법이 적용된다는 것입니다. 여기서 X는 숫자를 나타내는 기저입니다.그래서 십진수는 3 또는 9로 나눗셈을 확인할 수 있습니다.16진수의 경우 3, 5 또는 15로 나눗셈을 선택할 수 있습니다.그리고 팔진수는 7로 나눗셈을 확인할 수 있습니다.
이전 질문에서, 저는 N-1의 요인인 지수에 대해 N을 기반으로 하는 빠른 알고리즘을 보여주었습니다.서로 다른 2의 거듭제곱 사이의 기본 변환은 사소한 것입니다. 즉, 비트 그룹화입니다.
따라서 4번 베이스에서는 3번을 쉽게 확인할 수 있고 16번 베이스에서는 5번을 쉽게 확인할 수 있으며 64번 베이스에서는 7번과 9번을 쉽게 확인할 수 있습니다.
비우량 지수는 사소한 것이기 때문에 11과 13만이 어려운 경우입니다.11의 경우 기본 1024를 사용할 수 있지만, 그 시점에서는 작은 정수에 대해서는 효율적이지 않습니다.
모든 정수 값의 모듈로 감소를 도울 수 있는 방법은 비트 슬라이싱과 팝 카운트를 사용합니다.
mod3 = pop(x & 0x55555555) + pop(x & 0xaaaaaaaa) << 1; // <- one term is shared!
mod5 = pop(x & 0x99999999) + pop(x & 0xaaaaaaaa) << 1 + pop(x & 0x44444444) << 2;
mod7 = pop(x & 0x49249249) + pop(x & 0x92492492) << 1 + pop(x & 0x24924924) << 2;
modB = pop(x & 0x5d1745d1) + pop(x & 0xba2e8ba2) << 1 +
pop(x & 0x294a5294) << 2 + pop(x & 0x0681a068) << 3;
modD = pop(x & 0x91b91b91) + pop(x & 0xb2cb2cb2) << 1 +
pop(x & 0x64a64a64) << 2 + pop(x & 0xc85c85c8) << 3;
이러한 변수의 최대값은 48, 80, 73, 168 및 203으로, 모두 8비트 변수에 적합합니다.두 번째 라운드는 병렬로 진행할 수 있습니다(또는 일부 LUT 방법을 적용할 수 있습니다).
mod3 mod3 mod5 mod5 mod5 mod7 mod7 mod7 modB modB modB modB modD modD modD modD
mask 0x55 0xaa 0x99 0xaa 0x44 0x49 0x92 0x24 0xd1 0xa2 0x94 0x68 0x91 0xb2 0x64 0xc8
shift *1 *2 *1 *2 *4 *1 *2 *4 *1 *2 *4 *8 *1 *2 *4 *8
sum <-------> <------------> <-----------> <-----------------> <----------------->
2승이 아닌 상수로 나눗셈을 곱셈으로 대체할 수 있으며, 기본적으로 나눗셈의 역수를 곱합니다.이 방법으로 정확한 결과를 얻기 위한 세부 사항은 복잡합니다.
Hacker's Delight는 10장에서 이에 대해 자세히 설명합니다(안타깝게도 온라인에서는 사용할 수 없습니다).
계수에서 또 다른 곱셈과 뺄셈을 통해 계수를 구할 수 있습니다.
한 가지 고려해야 할 것은 16까지의 분할에만 관심이 있기 때문에 소수 16까지의 분할만 확인하면 됩니다.이것들은 2, 3, 5, 7, 11, 13입니다.
숫자를 각 소수로 나누고 부울(예: div2 = true)로 추적합니다.숫자 2와 3은 특별한 경우입니다.div3가 참이면 div9를 설정하여 다시 3으로 나눕니다.두 가지 기능은 매우 간단합니다(참고: '&'은 프로세서가 수행할 수 있는 가장 빠른 작업 중 하나입니다).
if n & 1 == 0:
div2 = true
if n & 3 == 0:
div4 = true
if n & 7 == 0:
div8 = true
if n & 15 == 0:
div16 = true
이제 불의 div2, div3, div4, div5, div7, div8, div9, div11, div13, div16이 있습니다.예를 들어, div6는 (div2 & & div3)와 같습니다.
따라서 5개 또는 6개의 실제 분할만 수행하면 됩니다(숫자를 3으로 나눌 수 있는 경우에만 6개).
나 자신을 위해, 나는 아마도 불리언을 위해 단일 레지스터의 비트를 사용할 것입니다. 예를 들어 bit_0은 div2를 의미합니다.그런 다음 마스크를 사용할 수 있습니다.
if (flags & (div2+div3)) == (div2 + div3): do_6()div2+div3는 사전 계산된 상수일 수 있습니다.div2가 비트0이고 div3가 비트1이면 div2+div3 == 3입니다.따라서 위의 'if'가 다음과 같이 최적화됩니다.
if (flags & 3) == 3: do_6()자, 이제... 구분 없이 모드:
def mod(n,m):
i = 0
while m < n:
m <<= 1
i += 1
while i > 0:
m >>= 1
if m <= n: n -= m
i -= 1
return n
div3 = mod(n,3) == 0
...
btw: 위의 코드에 대한 최악의 경우는 32비트 숫자에 대한 루프를 31번 통과하는 것입니다.
FYI: 위에 있는 Msalter의 게시물을 방금 보았습니다.그의 기술은 몇몇 소수에 대해 mod(...) 대신 사용될 수 있습니다.
분할에 대한 빠른 검정은 숫자가 표시되는 기저에 크게 의존합니다.베이스가 2인 경우, 2의 거듭제곱으로 나눗셈에 대한 "빠른 테스트"만 할 수 있다고 생각합니다.2진수는 해당 숫자의 마지막 n개의 2진수가 0인 경우 2로 나눌n 수 있습니다.다른 테스트의 경우 일반적으로 보다 빠른 것을 찾을 수 없다고 생각합니다.%.
약간의 사악하고 난독화된 비트 트위들링은 당신을 15로 분열시킬 수 있습니다.
32비트 부호 없는 숫자의 경우:
def mod_15ish(unsigned int x) {
// returns a number between 0 and 21 that is either x % 15
// or 15 + (x % 15), and returns 0 only for x == 0
x = (x & 0xF0F0F0F) + ((x >> 4) & 0xF0F0F0F);
x = (x & 0xFF00FF) + ((x >> 8) & 0xFF00FF);
x = (x & 0xFFFF) + ((x >> 16) & 0xFFFF);
// *1
x = (x & 0xF) + ((x >> 4) & 0xF);
return x;
}
def Divisible_by_15(unsigned int x) {
return ((x == 0) || (mod_15ish(x) == 15));
}
유사한 분할 루틴을 만들 수 있습니다.3그리고.5에 기반을 둔mod_15ish.
처리해야 할 64비트 부호 없는 int가 있는 경우 각 상수를 다음 값 이상으로 확장합니다.*1명백한 방법으로 선을 긋고, 위에 선을 추가합니다.*1 32비트 시프트를 입니다.0xFFFFFFFF두될 수 ) (마지막두줄동유게지수될있음하일은▁()마mod_15ish계약에 , 그런다 음동기계준만지수하약을, 값현사다니입이재은반환본일한▁is▁now▁then다,▁between▁value니▁return▁contract 사이입니다.0그리고.31(그래서 유지되는 것은x % 15==mod_15ish(x) % 15)
여기 아직 아무도 제안하지 않은 몇 가지 팁이 있습니다.
한 가지 아이디어는 다음과 같습니다.switch문 또는 일부 배열을 사전 계산합니다.그런 다음 적절한 최적화 도구를 사용하여 각 사례를 직접 인덱싱할 수 있습니다.예:
// tests for (2,3,4,5,6,7)
switch (n % 8)
{
case 0: break;
case 1: break;
case 2: do(2); break;
case 3: do(3); break;
case 4: do(2); do(4) break;
case 5: do(5); break;
case 6: do(2); do(3); do(4); break;
case 7: do(7); break;
}
응용 프로그램이 약간 모호하지만 n=16보다 작은 소수만 확인하면 됩니다.이는 모든 숫자가 현재 또는 이전 소수의 요인이기 때문입니다.그래서 n=16의 경우, 당신은 확인만 하면 벗어날 수 있을 것입니다.2, 3, 5, 7, 11, 13일 뿐입니다.생각일 뿐이야.
언급URL : https://stackoverflow.com/questions/6896533/fast-divisibility-tests-by-2-3-4-5-16
'programing' 카테고리의 다른 글
| 하위 쿼리를 처리하기 위한 MariaDB 이전 버전 (0) | 2023.08.09 |
|---|---|
| UIScrollView 페이지 변경 검색 중 (0) | 2023.08.09 |
| 드롭(존재하는 경우)과 드롭(존재하지 않는 경우)? (0) | 2023.08.09 |
| Excel Q - 2차원 배열이 있는 SUMIFS (0) | 2023.08.09 |
| JavaScript 또는 jQuery에서 값이 숫자인지 확인합니다. (0) | 2023.08.09 |