Convert a 74-bit integer to base 31

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

I did not compile the psuedo code, but you can get the generate understanding of how to convert the number:

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