0

考虑一个通过连续除法和余数运算进行计数的例程。

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

1 回答 1

1

一些红利会导致它永远循环吗？

Dividend = 0x1ffffffffL, Divisor = 2 是一个相当明显的例子，整个家族 (Divisor<<32)-1, Divisor 都是不动点。

根据这些，可以找到许多初始被除数和除数的循环组合，我相信还有更多：

#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);    
}
于 2009-03-04T18:19:04.993 回答