Parse bignum into list of 16-bit integers

Question

Hello, I have to implement some bignum arithmetics. The number has to be split into a list of 16 bit integers.

That is not the problem. The problem is to parse a string into this notation. If it would be a single integer, i would go through the string backwards, get the number out of the char and would add <number>*10^stringposition. (last char has stringposition 1 in this example)

But the bignum should not have multiplication and I thing there should be a smarter faster way. (A int multiplication is O(1); a bignum multiplication not)

How to do it?

(I can not use a complete library like gmp)

Answer 1

I don't think there's a good way to do this as the internal representation actually 2^16 base. You need to convert a 10 based number into a 2^16 based number.

don't use x*10^(position x), because you don't have the representation of 10^n in 2^16 base. You can do something like

num = 0
for i=0 to len do
  num = num * 10 + a[i]

Answer 2

In Java you can solve your problem using java.math.BigInteger class.

1. Create a BigInteger from your String input:

   BigInteger x = new BigInteger(s);

2. Get a byte array containing the two's-complement representation of this BigInteger:

   byte[] b = x.toByteArray();

3. Convert the byte array to int[] merging consecutive pairs of 8-bit values into 16-bit values like this:

   int[] merge(byte[] b) {
       int[] result = new int[((b.length-1)>>1) + 1];
       for (int i = 0; i < b.length; i++) {
            result[i>>1] |= b[b.length-i-1] << ((i&1)<<3);
       }
       return result;
   }