How do I emulate 256-bit integer math ops on a system with only a 32-bit int?

Question

I'd like to write a deadsimple bignum class using a series of (unsigned) integers. I can loosely see how addition and subtraction would work, but division and multiplication is another story. I know 32-bit compilers can emuate 64-bit int's by splitting the int64 in two int32's. I'm looking for an efficient method to do that.

I'd like to have C++ code, not assembly. Speed is no primary concern, but the most efficient solution without assemble is always nice to have.

Answer 1

Perhaps this can serve as a starting point. It implements up to 2,048-bit unsigned integers, using a base-65,536 representation. This means each digit fits in 16 bits, and we can trivially detect overflow (even when multiplying) by simply using 32 bits for the results.

This is C code however, but should be trivial to port to C++, or just use as an inspiration. It's very much optimized for readability rather than speed since this is not exactly the kind of stuff I'm good at. :)

Answer 2

You'd best have a look at arbitrary precision arithmetic which will explain the thinking behind the process of emulating higher precision processors than then one that your code is running on.

Answer 3

What's wrong with just using long long? That's guaranteed to be at least 64 bits. Otherwise, your Knuth (vol. 2) should provide the basic algorithms.

Answer 4

Use simple byte array. You can have size of integer whatever you want*. You just have to operate in binary and take endianess into consideration (your bits will be 7-6-5-4-3-2-1-0-15-14-13...)

*RAM is limited

Answer 5

for arbitrary sizes, give GMP a spin, it should also work for your 64bit math on 32bit if for some reason you can't rely on the compiler to do it for you.

Answer 6

Purchase a hardback book called NUMERICAL RECIPES IN C++ and you will find what you are looking for on pages starting on 20.6 page p916 onto to p925