Convert a 74-bit integer to base 31

Question

To generate a UFI number, I use a bitset of size 74. To perform step 2 of UFI generation, I need to convert this number:

9 444 732 987 799 592 368 290
(10000000000000000000000000000101000001000001010000011101011111100010100010)

into:

DFSTTM62QN6DTV1

by converting the first representation to base 31 and getting the equivalent chars from a table.

#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
*/    

Is there a way to perform the conversion on my bitset without using an external BigInteger library?

Edit: I finally done a BigInteger class even if the Cheers and hth. - Alf's solution works like a charm

Answer 1

To get modulo 31 of a number you just need to sum up the digits in base 32, just like how you calculate modulo 3 and 9 of a decimal number

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

You can speedup the modulo calculation by running the additions in parallel like how its done here. The similar technique can be used to calculate modulo 3, 5, 7, 15... and 2³¹ - 1

• C - Algorithm for Bitwise operation on Modulus for number of not a power of 2
• Is there any easy way to do modulus of 2^32 - 1 operation?
• Logic to check the number is divisible by 3 or not?

However since the question is actually about base conversion and not about modulo as the title said, you need to do a real division for this purpose. Notice 1/b is 0.(1) in base b + 1, we have

1/31 = 0.000010000100001000010000100001...₃₂ = 0.(00001)₃₂

and then N/31 can be calculated like this

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

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

Since both modulo and division use shift-by-5, you can also do both them together in a single loop.

However the tricky part here is how to round the quotient properly. The above method will work for most values except some between a multiple of 31 and the next power of 2. I've found the way to correct the result for values up to a few thousands but yet to find a generic way for all values

You can see the same shift-and-add method being used to divide by 10 and by 3. There are more examples in the famous Hacker's Delight with proper rounding. I didn't have enough time to read through the book to understand how they implement the result correction part so maybe I'll get back to this later. If anyone has any idea to do that it'll be grateful.

One suggestion is to do the division in fixed-point. Just shift the value left so that we have enough fractional part to round later

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)

Note that your result above is incorrect. I've confirmed the result is CEOPPJ62MK6CPR1 from both Yaniv Shaked's answer and Wolfram alpha unless you use different symbols for the digits

Answer 2

This code seems to work. To guarantee the result I think you need to do additional testing. E.g. first with small numbers where you can compute the result directly.

Edit: Oh, now I noticed you posted the required result digits, and they match. Means it's generally good, but still not tested for corner cases.

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

Results with 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