Преобразование 74-битного целого числа в основание 31

Этот код, кажется, работает. Чтобы гарантировать результат, я думаю, вам нужно сделать дополнительное тестирование. Например. сначала с небольшими числами, где вы можете вычислить результат напрямую.

Редактировать: О, теперь я заметил, что вы опубликовали требуемые цифры результата, и они совпадают. Значит в целом неплохо, но еще не проверено на крайние случаи.

#include <assert.h>
#include <algorithm>            // std::reverse
#include <bitset>
#include <vector>
#include <iostream>
using namespace std;

template< class Type > using ref_ = Type&;

namespace base31
{
    void mul2( ref_<vector<int>> digits )
    {
        int carry = 0;
        for( ref_<int> d : digits )
        {
            const int local_sum = 2*d + carry;
            d = local_sum % 31;
            carry = local_sum / 31;
        }
        if( carry != 0 )
        {
            digits.push_back( carry );
        }
    }

    void add1( ref_<vector<int>> digits )
    {
        int carry = 1;
        for( ref_<int> d : digits )
        {
            const int local_sum = d + carry;
            d = local_sum % 31;
            carry = local_sum / 31;
        }
        if( carry != 0 )
        {
            digits.push_back( carry );
        }
    }

    void divmod2( ref_<vector<int>> digits, ref_<int> mod )
    {
        int carry = 0;
        for( int i = int( digits.size() ) - 1; i >= 0; --i )
        {
            ref_<int> d = digits[i];
            const int divisor = d + 31*carry;
            carry = divisor % 2;
            d = divisor/2;
        }
        mod = carry;
        if( digits.size() > 0 and digits.back() == 0 )
        {
            digits.resize( digits.size() - 1 );
        }
    }
}


int main() {
    bitset<74> bits(
        "10000000000000000000000000000101000001000001010000011101011111100010100010"
        );
    vector<int> reversed_binary;
    for( const char ch : bits.to_string() ) { reversed_binary.push_back( ch - '0' ); }

    vector<int> base31;
    for( const int bit : reversed_binary )
    {
        base31::mul2( base31 );
        if( bit != 0 )
        {
            base31::add1( base31 );
        }
    }

    { // Check the conversion to base31 by converting back to base 2, roundtrip:
        vector<int> temp31 = base31;
        int mod;
        vector<int> base2;
        while( temp31.size() > 0 )
        {
            base31::divmod2( temp31, mod );
            base2.push_back( mod );
        }
        reverse( base2.begin(), base2.end() );
        cout << "Original     : " << bits.to_string() << endl;
        cout << "Reconstituted: ";
        string s;
        for( const int bit : base2 ) { s += bit + '0'; cout << bit; };  cout << endl;
        assert( s == bits.to_string() );
    }

    cout << "Base 31 digits (msd to lsd order): ";
    for( int i = int( base31.size() ) - 1; i >= 0; --i )
    {
        cout << base31[i] << ' ';
    }
    cout << endl;

    cout << "Mod 31 = " << base31[0] << endl;
}

Результаты с MinGW g++:

Original     : 10000000000000000000000000000101000001000001010000011101011111100010100010
Reconstituted: 10000000000000000000000000000101000001000001010000011101011111100010100010
Base 31 digits (msd to lsd order): 12 14 24 25 25 19 6 2 22 20 6 12 25 27 1
Mod 31 = 1

Чтобы получить число по модулю 31, вам просто нужно суммировать цифры в основание 32, точно так же, как вы вычисляете по модулю 3 и 9 десятичного числа

unsigned mod31(std::bitset<74> b) {
    unsigned mod = 0;
    while (!b.none()) {
        mod += (b & std::bitset<74>(0x1F)).to_ulong();
        b >>= 5;
    }
    while (mod > 31)
        mod = (mod >> 5) + (mod & 0x1F);
    return mod;   
}

Вы можете ускорить расчет по модулю, запустив дополнения параллельно, например как это сделано здесь. Аналогичный метод можно использовать для вычисления по модулю 3, 5, 7, 15... и 2³¹ - 1.

• C - Алгоритм побитовой операции над модулем для числа, не равного степени 2
• Есть ли простой способ выполнить операцию по модулю 2^32 - 1?
• Логика проверки числа делится на 3 или нет?

Однако, поскольку вопрос на самом деле касается базового преобразования, а не модуля, как сказано в заголовке, для этой цели вам нужно выполнить реальное деление. Обратите внимание, что 1/b равно 0.(1) по основанию b + 1, мы имеем

1/31 = 0,000010000100001000010000100001...₃₂ = 0.(00001)₃₂

и тогда N/31 можно рассчитать так

N/31 = N×2^-5 + N×2^-10 + N×2^-15 + ...

uint128_t result = 0;
while (x)
{
    x >>= 5;
    result += x;
}

Поскольку и по модулю, и по делению используется сдвиг на 5, вы также можете выполнить их вместе в одном цикле.

Однако сложная часть здесь заключается в том, как правильно округлить частное. Вышеупомянутый метод будет работать для большинства значений, за исключением некоторых между кратным 31 и следующей степенью 2. Я нашел способ исправить результат для значений до нескольких тысяч, но еще не нашел общий способ для всех значений

Вы можете видеть, что тот же метод сдвига и добавления используется для деления на 10 и на 3. В знаменитом Hacker's Delight есть еще примеры с правильным округлением. У меня не было достаточно времени, чтобы прочитать книгу, чтобы понять, как они реализуют часть коррекции результатов, поэтому, возможно, я вернусь к этому позже. Если у кого-то есть идеи, как это сделать, буду признателен.

Одно предложение состоит в том, чтобы сделать деление в фиксированной точке. Просто сдвиньте значение влево, чтобы у нас было достаточно дробной части для последующего округления.

uint128_t result = 0;
const unsigned num_fraction = 125 - 75 // 125 and 75 are the nearest multiple of 5
// or maybe 128 - 74 will also work
uint128_t x = UFI_Number << num_fraction; 

while (x)
{
    x >>= 5;
    result += x;
}
// shift the result back and add the fractional bit to round
result = (result >> num_fraction) + ((result >> (num_fraction - 1)) & 1)

Обратите внимание, что ваш результат выше неверен. Я подтвердил, что результат CEOPPJ62MK6CPR1 из обоих ответа Янива Шакеда и Wolfra разные символы для цифр

Я не компилировал псевдокод, но вы можете получить представление о том, как преобразовать число:

// Array for conversion of value to base-31 characters:
char base31Characters[] = 
{
    '0',
    '1',
    '2',
    ...
    'X',
    'Y'
};

void printUFINumber(__int128_t number)
{
    string result = "";
    while (number != 0)
    {
        var mod = number % 31;
        result = base31Characters[mod] + result;
        number = number / 31;
    }
    cout << number;
}