[씨] c에서 매우 큰 루프 수

예를 들어 재귀 적으로 반복 할 수 있습니다.

void loop( unsigned a, unsigned b ) {
    unsigned int i;
        if ( b == 0 ) {
                printf( "." );
                    } else {
                            for ( i = 0; i < a; ++i ) {
                                        loop( a, b - 1 );
                                                }
                                                    }
                                                    }
                                                    

... a ^ b .문자를 인쇄합니다 .

-------------------

첫 번째 질문에 답할 수는 없지만 ( libgmp 를 살펴보면 많은 수를 다루는 데 도움이 될 수 있습니다), a ^ b 번 작업을 수행하는 방법은 재귀를 사용하는 것입니다.

function (a,b) {
   if (b == 0) return;
      while (i < a) {
           function(a,b-1);
              }
              }
              

이것은 b가 0이 될 때까지 각 단계에 대해 루프를 한 번 수행합니다.

-------------------

댓글 중 하나에 대한 답변에 대해 : 하지만 두 줄의 입력과 2 ^ n 줄의 쓰레기가있는 경우 어떻게 건너 뛰나요? 모니터링해야하는 2 ^ 1000 줄의 쓰레기를 볼 수있는 실제 시나리오를 말씀해 주시겠습니까?

더 합리적 (작은) 수의 입력 을 위해 인덱스를 반복하는 것이 아니라 단순히 각 줄을 확인하여 실제 필요에 맞는 소리를 해결할 수 있습니다 (즉, 관련 입력 라인 만 처리). while 루프에서 처리되는 구성 요소 ...

의사 코드 :

BOOL criteriaMet = FALSE;
while(1)
{
    while(!criteriaMet)
        {
                 //test next line of input
                          //if criteria met, set criteriaMet = TRUE;
                                   //if criteria met, handle line of input
                                            //if EOF or similar, break out of loops
                                                }
                                                    //criteria met, handle it here and continue
                                                        criteriaMet = FALSE;//reset for more searching...
                                                        
                                                        }
                                                        

-------------------

각 셀이에서 까지의 값을 보유 하는 b크기의 배열을 사용하십시오 . 예를 들어 -3 크기의 부울 배열을 사용합니다.i[]0a-12^3

반복 할 때마다. 증분 i[0]. 이면 0으로 a==i[0]설정 i[0]하고 증가시킵니다 i[1]. 이면 0으로 0==i[1]설정 i[1]하고 i[2]증가하는 식으로 도달하지 않고 셀을 증가시킵니다 a. 이것은 루프에서 쉽게 수행 할 수 있습니다.

for(int j=0;j<b;++j){
    ++i[j];
        if(i[j]<a){
                break;
                    }
                    }
                    

a반복 후 i[0]0으로 돌아갑니다. 후 a^2반복, i[0], i[1]모두 0이됩니다. 후 a^b반복, 모든 셀이 될 것입니다 0그리고 당신은 루프를 종료 할 수 있습니다. 매번 어레이를 확인할 필요가 없습니다. 재설정하는 순간 i[b-1]모든 어레이가 0으로 돌아 간다는 것을 알 수 있습니다.

-------------------

귀하의 질문이 의미가 없습니다. 루프가 비어 있어도 초당 2 ^ 32 회 이상 반복해야합니다. 이 최상의 시나리오에서도 간단한 uint64_t변수로 수행 할 수있는 2 ^ 64 루프 반복 처리에는 136 년이 걸립니다. 이것은 루프가 전혀 아무것도하지 않는 경우입니다.

나중에 주석에서 설명했듯이 줄을 건너 뛰는 경우에도 마찬가지입니다. 텍스트에서 줄을 건너 뛰거나 세는 것은 개행을 세는 문제입니다. 2006 년에는 전 세계에 약 10 * 2 ^ 64 바이트의 스토리지가있는 것으로 추정되었습니다. 세계의 모든 데이터가 텍스트 (그렇지 않음)이고 평균 줄이 줄 바꿈을 포함하여 10 자 (아마도 아닐 것임)라고 가정하면 모든 데이터의 줄 수에 맞을 것입니다. 하나의 세계에서 uint64_t. 물론이 처리는 CPU의 캐시가 4 개의 10Gbps 네트워크 인터페이스에서 직접 공급 되더라도 최소한 136 년이 걸립니다 (컴퓨터에 그렇게 많은 디스크가있을 수 있다고 생각할 수 없기 때문에).

다시 말해서, 당신이 풀고 있다고 생각하는 문제는 uint64_tC 의 정상보다 더 많이 반복하는 문제가 아닙니다 . 2 ^ n의 n은 코드가 실행될 것으로 예상되는 하드웨어에서 합리적으로 50-55를 넘을 수 없습니다.

따라서 귀하의 질문에 답하십시오. a를 반복하는 uint64_t것만 으로 는 충분하지 않은 경우 무어의 법칙이 문제를 해결하고 문제를 해결할 때까지 최소 30 년을 기다리는 것입니다. 지금 프로그램을 실행하는 것보다 빠르게 진행됩니다. 나는 우리가 uint128_t그 시간에 있을 것이라고 확신 합니다.

출처
https://stackoverflow.com/questions/22019853