정수 나누기 기반 루틴 계산 - 수식 접근 방식이 있습니까?

Question

연속 나머지 나누기 연산으로 계산되는 루틴을 고려하십시오.

64 비트 배수부터 시작하여 루틴은 상수 약수로 나눕니다.
나머지가 0이면 루틴이 반환됩니다.
그렇지 않으면, 나머지를 2^32로 곱하고 정수를 더함으로써 새로운 배당금이 생성됩니다. 코드에서

: 임의의 제수

/// ULong - 64 bit, unsigned 
/// UInt - 32 bit, unsigned 
const UInt Divisor; 
int TrickyCounter(ULong Dividend) 
{ 
    int count = 0; 
    Ulong Quotient; 
    UInt Remainder; 

    do { 
     Quotient = Dividend/Divisor; 
     Remainder = Dividend%Divisor; 
     assert((Quotient >> 32) == 0); 
     count = count + 1; 
     Dividend = ((ULong)Remainder << 32) + Quotient; 
    } while (Remainder != 0); 
    return count; 
} 

원하는 수를 얻기 위해 필요한 배당금을 산출하는 것이 바람직 비 반복하는 방법이 있는가?
초기 배당금이 많으면 "Assert"조건에 빨리 도달하는 것 같습니다. 일부 배당금으로 인해이를 반복 할 수 있습니까?

---

루틴이 몫을 반환하는 경우 반환 할 번호를 생성하기 위해 배당금을 계산할 수 있습니까?

Uint TrickyNumber(ULong Dividend, int count) 
{ 
    Ulong Quotient = 0; 
    UInt Remainder; 

    while (count > 0) 
     Quotient = Dividend/Divisor; 
     Remainder = Dividend%Divisor; 
     assert((Quotient >> 32) == 0); 
     count = count - 1; 
     Dividend = ((ULong)Remainder << 32) + Quotient; 
    } 
    return (UInt)Quotient; 
} 

Answer 1

어떤 배당금은 영원히 루프이 원인이겠습니까?

0x1ffffffffL은 제수 = 2가 비교적 분명한 예이다 = 배당 및 가족 (제수 < < 32) -1, 제수 점 고정된다. 초기 배당 및 제수 이러한 많은 순환 조합에서 근무

이 발견, 나는 더있다 확신 할 수 있습니다

정확히 어설의 목적은 무엇

#include <stdio.h> 
#include <stdint.h> 
#include <inttypes.h> 


size_t tricky_counter(uint64_t dividend, const uint32_t divisor) 
{ 
    const size_t cycle_buffer_size = 1024; 
    size_t count = 0; 
    uint64_t quotient; 
    uint32_t remainder; 

    uint64_t pre[cycle_buffer_size]; 

    do { 
     pre[ count % cycle_buffer_size ] = dividend; 

     quotient = dividend/divisor; 
     remainder = dividend%divisor; 

     if ((quotient >> 32) != 0) { 
      printf("quotient: 0x%" PRIx64 "\n", quotient); 
     } 

     count = count + 1; 

     dividend = ((uint64_t)remainder << 32) + quotient; 

     for (size_t i = 0; i < count && i<cycle_buffer_size;++i) { 
      if (pre[i] == dividend) { 
       size_t cycle = 0; 

       printf("dividend repeats: \n"); 

       while (i != count % cycle_buffer_size) { 
        //~ printf(" 0x%" PRIx64 "/%" PRId32 " \n", pre[i], divisor); 
        i = (i + 1) % cycle_buffer_size; 
        ++cycle; 
       } 

       printf(" 0x%" PRIx64 "/%" PRId32 " cycle size %zd \n", dividend, divisor, cycle); 

       return 0; 
      } 
     } 

    } while (remainder != 0); 

    return count; 
} 


int main (void) 
{ 
    for (uint64_t k = 1; k < 256; ++k) 
     for (uint64_t x = 2; x < 1024; ++x) 
      tricky_counter((x-1 << 32) + 0x01010101L * k, x);  
}