Zählen mit einer Integer Divide-basierten Routine - Gibt es einen formelhaften Ansatz?

Question

Betrachten Sie eine Routine, die durch sukzessive Division mit Restoperationen zählt.

Beginnend mit einem 64-Bit-Dividend teilt sich die Routine durch einen konstanten Divisor.
Wenn der Rest 0 ist, kehrt die Routine zurück.
Andernfalls wird ein neuer Dividend konstruiert, indem der Rest mit 2^32 multipliziert und der ganzzahlige Quotient addiert wird.

In Code:

/// 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; 
} 

mit einer beliebigen Divisor gibt es ein vorzugsweise nicht-Iterieren Verfahren die notwendige Dividend zur Berechnung der gewünschten Zählwert zu erhalten?
Für viele anfängliche Dividenden scheint dies schnell die Bedingung "Assert" zu treffen. Würden einige Dividenden dafür sorgen, dass sich das für immer wiederholt?

---

Wenn anstelle einer Zählung, kehrt die Routine der Quotient, kann ich berechnen die Dividende der Nummer I zurückgegeben werden soll produzieren?

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

Würden einige Dividenden führen diese immer in einer Schleife?

Dividend = 0x1ffffffffL, Divisor = 2 ein ziemlich offensichtliches Beispiel ist, und die ganze Familie (Divisor < < 32) -1, Divisor sind Punkte festgelegt.

Arbeiten von diesen können viele zyklischen Kombinationen von Anfängen Dividend und Divisor gefunden werden, und ich bin sicher, es gibt mehr:

#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);  
}