# Algorithm for converting a 128-bit value to a string

I am trying to convert 128-bit data to a string in a PLC, but the PLC has max. 32-bit data. I store 128-bit data as a byte array and bit array. Now I need to convert this value to a string, but the PLC does not have such a variable. I did some research, but I couldn't find the answers I wanted.

Basically I need to add the remaining numbers after multiplying their multiples in the binary system to convert a bit array to decimal. But since the number has grown so much, I can't do such a process on the PLC.

My thought is that basically the whole system is processed in binary, and it should split my 128-bit array and convert it to decimal numbers in chunks. Am I thinking wrong?

A 128-bit number has 39 characters. When you convert this number to a byte array, 16 bytes are obtained, so 16*8=128 bits. I need to expand this byte array or bit array to 39 characters again, and I have to do this without using 64-bit or 128-bit variables. I can use max. 32-bit variables.

Does anyone have any information or ideas on the subject?

I haven't had time to try the methods, but the threads may be useful for other friends.

@davetweed >> https://en.wikipedia.org/wiki/Double_dabble

https://en.wikipedia.org/wiki/Base64

https://en.wikipedia.org/wiki/Ascii85

@greybeard >> "chunk-wise two-step"

Thank you for your support. special thanks:@benmiller , @davetweed , @greybeard

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Jan 21, 2023 at 6:20

There are basically two ways to convert a natural number from base $$\b\$$ to base $$\B\$$:
(Following the diction of D.E. Knuth: TAoCP vol 2: Seminumerical Algorithms 4.4: Radix Conversion)

• Method (1a): Division by $$\B\$$ (using base $$\b\$$ arithmetic) (bin2dec: Division by 10)
• Method (1b): Multiplication by $$\b\$$ (using base $$\B\$$ arithmetic) (* powers of 2 "in base 10(ᵏ)")

I find "long division" a more intimidating prospect than long multiplication and suggest using 1b: computing with parts "a power of 10" - never mind how arithmetic is done "within parts".
Converting chunks of 10 bits to "millipeds" of 3 decimal digits is a bit more intuitive for a low number of chunks. Once it is working, little of the source code should change switching to groups of 4 digits (and 14-16 bits).

• by parameter part
(including double dabble for a smart name for a basic (1 bit at a time) method)
+ doesn't need any precomputation/table(s)
- (I think it's) more operations
• by result part (some like to call this Vedic)
+ (I think it's) less operations
- needs precomputation/table(s)
• Didn't get the hang of structured text / SCL (yet). Coded "Vedic" 4*32bit→39 digits in Java&Python 3 (~39 divisions&36 multiplications - all 31+1 bits, only); don't quite like either. Commented Jan 23, 2023 at 0:07
• Got the same number of multiplications with by parameter part, but about 37-52 more divisions. (Following an addition, a "divmod" can be substituted by a conditional subtraction+change.) Has no use for the 46-72 16-bit coefficients the by result part variant uses to shift some divmods to initialisation/compile time. Commented Jan 23, 2023 at 8:07
• For "method 1a" (the usual, improved by doing 4 digits per chunk), I again got the same number of multiplications and 77 divmods. This may be teaching something about these radix conversion methods I don't get. Commented Jan 23, 2023 at 10:57

Assuming you have BCD addition with carry available you could store 128 39-nibble constants (maybe packed 4 digits per word, but it doesn't matter as long as you can implement extensible BCD addition) representing the BCD value of 2^i for i = 0..127.

Then you iterate through the 128 bits of the unknown value, doing a BCD add of the constant (starting from zero, of course) for each '1' in the original value (and no addition if there is a zero). This is essentially multiplication with a BCD result. There's also the 'add 6' algorithm for BCD correction if BCD operations are not native.

so the array of constants would be {1, 2, 4, ... , 85070591730234615865843651857942052864, 170141183460469231731687303715884105728}

Perhaps a bit slow, but it's hard to go wrong.

If you didn't want to pre-compute the constants you could just add a register to itself in BCD, starting from 1 and compute the constants on the fly, which would take at least twice as long.

• Or start with a "multiword BCD accumulator" initialised to zero, adding it to itself with carry set to each bit from most to least significant in the original value for the lowest accumulator word. Just 128 "long BCD additions" later (worst case), you're done. Commented Jan 26, 2023 at 16:44