Подсчет с помощью процедуры, основанной на целочисленном делении. Существует ли формульный подход? - PullRequest
Новая
       32

Подсчет с помощью процедуры, основанной на целочисленном делении. Существует ли формульный подход?

0 голосов
/ 04 марта 2009

Рассмотрим подпрограмму, которая рассчитывается путем последовательных операций деления с остатком.

Начиная с 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;
}

1 Ответ

1 голос
/ 04 марта 2009

Могут ли некоторые дивиденды зациклить это навсегда?

Dividend = 0x1ffffffffL, Divisor = 2 является довольно очевидным примером, и все семейство (Divisor << 32) -1, Divisor являются фиксированными точками. </p>

Исходя из этого, можно найти много циклических комбинаций начального дивиденда и делителя, и я уверен, что есть еще: 

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