Convert a 74-bit integer to base 31

  • A+
Category:Languages

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?

 


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 231 - 1

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...32 = 0.(00001)32

and then x/31 can be calculated like this

x/31 = x*2-5 + x*2-10 + x*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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: