Comptage avec une routine Integer Divide - Existe-t-il une approche stéréotypée?

Question

Considérons une routine qui compte par opérations successives de division w/reste. À partir d'un dividende de 64 bits, le sous-programme divise par un diviseur constant

Si le reste est 0, la routine revient.
Sinon, un nouveau dividende est construit en multipliant le reste par 2^32 et en ajoutant le quotient entier.

Dans le 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; 
} 

Avec un diviseur arbitraire, il est de préférence un procédé non-itération pour calculer le dividende nécessaire pour obtenir le nombre souhaité?
Pour beaucoup de dividendes initiaux, cela semble rapidement atteindre la condition "Assert". Est-ce que certains dividendes provoqueraient cette boucle pour toujours? Si, au lieu d'un nombre, la routine renvoie le quotient, puis-je calculer le Dividende pour produire le nombre que je veux renvoyer?

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

Est-ce que certains dividendes causer cette boucle à jamais?

Dividende = 0x1ffffffffL, Diviseur = 2 est un exemple assez évident, et toute la famille (Diviseur < < 32) -1, Diviseur sont des points fixes.

de travail de ces derniers, de nombreuses combinaisons cycliques de dividende initial et diviseur se trouvent, et je suis sûr qu'il ya plus:

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