How to represent a number in base 2³²?

Question

If I have some base 10 or base 16 number, how do I change it into base 2³²?

The reason I'm trying to do this, is for implementing BigInt as suggested by other members here Why to use higher base for implementing BigInt?

Will it be the same as integer (base 10) till 2³²? What will happen after it?

Answer 1

You are trying to find something of the form

a0 + a1 * (2^32) + a2 * (2^32)^2 + a3 * (2^32)^3 + ...

which is exactly the definition of a base-2³² system, so ignore all the people that told you that your question doesn't make sense!

Anyway, what you are describing is known as base conversion. There are quick ways and there are easy ways to solve this. The quick ways are very complicated (there are entire chapters of books dedicated to the subject), and I'm not going to attempt to address them here (not least because I've never attempted to use them).

One easy way is to first implement two functions in your number system, multiplication and addition. (i.e. implement BigInt add(BigInt a, BigInt b) and BigInt mul(BigInt a, BigInt b)). Once you've solved that, you will notice that a base-10 number can be expressed as:

b0 + b1 * 10 + b2 * 10^2 + b3 * 10^3 + ...

which can also be written as:

b0 + 10 * (b1 + 10 * (b2 + 10 * (b3 + ...

so if you move left-to-right in your input string, you can peel off one base-10 digit at a time, and use your add and mul functions to accumulate into your BigInt:

BigInt a = 0;
for each digit b {
    a = add(mul(a, 10), b);
}

Disclaimer: This method is not computationally efficient, but it will at least get you started.

Note: Converting from base-16 is much simpler, because 2³² is an exact multiple of 16. So the conversion basically comes down to concatenating bits.

Answer 2

Let's suppose that we are talking about a base-10 number:

a[0]*10^0 + a[1]*10^1 + a[2]*10^2 + a[3]*10^3 + ... + a[N]*10^N

where each a[i] is a digit in the range 0 to 9 inclusive.

I'm going to assume that you can parse the string that is your input value and find the array a[]. Once you can do that, and assuming that you have already implemented your BigInt class with the + and * operators, then you are home. You can simply evaluate the expression above with an instance of your BigInt class.

You can evaluate this expression relatively efficiently using Horner's method.

I've just written this down off the top of my head, and I will bet that there are much more efficient base conversion schemes.

Answer 3

If I have some base 10 or base 16 number, how do I change it into base 2^32?

Just like you convert it to any other base. You want to write the number n as

n = a_0 + a_1 * 2^32 + a_2 * 2^64 + a_3 * 2^96 + ... + a_k * 2^(32 * k).

So, find the largest power of 2^32 that divides into n, subtract off the multiple of that power from n, and repeat with the difference.

However, are you sure that you asked the right question?

I suspect that you mean to be asking a different question. I suspect that you mean to ask: how do I parse a base-10 number into an instance of my BigInteger? That's easy. Code up your implementation, and make sure that you've implemented + and *. I'm completely agnostic to how you actually internally represent integers, but if you want to use base 2^32, fine, do it. Then:

 BigInteger Parse(string s) {
      BigInteger b = new BigInteger(0);
      foreach(char c in s) { b = b * 10 + (int)c - (int)'0'; }
      return b;
 } 

I'll leave it to you to translate this to C.

Answer 4

Base 16 is easy, since 2³² is 16⁸, an exact power. So, starting from the least significant digit, read 8 base-16 digits at a time, convert those digits into a 32-bit value, and that is the next base-2³² "digit".

Base 10 is more difficult. As you say, if it's less than 2³², then you just take the value as a single base-2³² "digit". Otherwise, the simplest method I can think of is to use the Long Division algorithm to repeatedly divide the base-10 value by 2³²; at each stage, the remainder is the next base-2³² "digit". Perhaps someone who knows more number theory than me could provide a better solution.

Answer 5

I think this is a totally reasonable thing to do.

What you are doing is representing a very large number (like an encryption key) in an array of 32 bit integers.

A base 16 representation is base 2^4, or a series of 4 bits at a time. If you are receiving a stream of base 16 "digits", fill in the low 4 bits of the first integer in your array, then the next lowest, until you read 8 "digits". Then go to the next element in the array.

long getBase16()
{
  char cCurr;

  switch (cCurr = getchar())
  {
  case 'A':
  case 'a':
    return 10;
  case 'B':
  case 'b':
    return 11;
  ...
  default:
    return cCurr - '0';
  }
}

void read_input(long * plBuffer)
{
  long * plDst = plBuffer;
  int iPos = 32;

  *(++plDst) = 0x00;

  long lDigit;
  while (lDigit = getBase16())
  {
     if (!iPos)
     {
       *(++plDst) = 0x00;
       iPos = 32;
     }

     *plDst >> 4;
     iPos -= 4;
     *plDst |= (lDigit & 0x0F) << 28
  }
}

There is some fix up to do, like ending by shifting *plDst by iPos, and keeping track of the number of integers in your array.

There is also some work to convert from base 10.

But this is enough to get you started.