Tam Sayı Bölmeli tabanlı bir yordamla sayma - Formüle dayalı bir yaklaşım var mı?

Question

Ardışık bölme/kalan işlemler ile sayan bir yordamı düşünün.

64 bit temettü ile başlayarak, rutin sabit bir ayırıcı tarafından böler.
Kalan 0 ise, rutin geri döner.
Aksi takdirde, kalan kısmı 2^32 ile çarparak ve tamsayı katsayısını ekleyerek yeni bir temettü oluşturulur. kodda

: keyfi Divisor ile

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

istenen sayısını elde etmek için gerekli olan Temettünün hesaplamak için tercihen non-ilerlerken yöntem var mıdır?
Birçok ilk temettü için, bu "Assert" koşuluna hızlıca vurulur gibi görünüyor. Bazı temettüler sonsuza dek bu döngüye neden olur mu?

---

Eğer bir sayım yerine, rutin bölümleri döndürürse, İadeyi istediğim numarayı üretmek için Kâr Payını hesaplayabilir miyim?

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

bazı temettüler sonsuza döngü bu neden istiyorsunuz?

0x1ffffffffL, Bölen = 2 oldukça belirgin örneğidir = Kar ve bütün aile (Bölen < < 32) -1, Bölen noktaları sabitlenir. İlk temettü ve bölen bu, birçok siklik kombinasyondan Çalışma

buldum ve daha vardır eminim edilebilir:

tam assert amacı nedir

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