整数でのカウント除算ベースのルーチン - 式のアプローチはありますか？

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

、所望数を得るために必要な配当を計算するために、好ましくは非反復方法はありますか？
多くの初期配当に対して、これはすぐに「アサート」条件に当てはまるようです。配当によってはこれが永遠に繰り返されるのだろうか？

---

返される番号を生成するために、計算の代わりに商が返された場合、配当を計算することはできますか？

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