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

Question

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

Для генерации Номер UFI, Я использую bitset размером 74. Чтобы выполнить шаг 2 генерации UFI, мне нужно преобразовать это число:

9 444 732 987 799 592 368 290
(10000000000000000000000000000101000001000001010000011101011111100010100010)

в:

DFSTTM62QN6DTV1

путем преобразования первого представления в базу 31 и получения эквивалентных символов из таблицы.

#define PAYLOAD_SIZE 74
// payload = binary of 9444732987799592368290
std::bitset<PAYLOAD_SIZE> bs_payload(payload);
/*
perform modulo 31 to obtain:
12(D), 14(F), 24(S), 25(T), 25, 19, 6, 2, 22, 20, 6, 12, 25, 27, 1
*/

Есть ли способ выполнить преобразование для моего набора битов без использования внешней библиотеки BigInteger?

редактировать: Я наконец сделал BigInteger класс, даже если Ура и hth. Альфрешение работает как шарм

6

base-conversion bigint c++c++11 std-bitset

Решение

Другие решения

Чтобы получить по модулю 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

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

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

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

х / 31 = х * 2^-5 + х * 2^-10 + х * 2^-15 + …

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

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

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

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

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

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 от обоих Ответ Янива Шакеда а также Вольфрам Альфа

3

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

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

0

Источник

Accepted Answer

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

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

#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 ++:

Оригинал: 1000000000000000000000000000010100000100000101000001000001010000011101011111100010100010
Восстановлено: 1000000000000000000000000000010100000100000101000001110101110000011101011111100010100010
Начальные 31 цифры (от MSD до LSD): 12 14 24 25 25 19 6 2 22 20 6 12 25 27 1
Мод 31 = 1

1