Take the 2-minute tour ×

I'm still working on routines for arbitrary long integers in C++. So far, I have implemented addition/subtraction and multiplication for 64-bit Intel CPUs.

Everything works fine, but I wondered if I can speed it a bit by using SSE. I browsed through the SSE docs and processor instruction lists, but I could not find anything I think I can use and here is why:

  • SSE has some integer instructions, but most instructions handle floating point. It doesn't look like it was designed for use with integers (e.g. is there an integer compare for less?)

  • The SSE idea is SIMD (same instruction, multiple data), so it provides instructions for 2 or 4 independent operations. I, on the other hand, would like to have something like a 128 bit integer add (128 bit input and output). This doesn't seem to exist. (Yet? In AVX2 maybe?)

  • The integer additions and subtractions handle neither input nor output carries. So it's very cumbersome (and thus, slow) to do it by hand.

My question is: is my assessment correct or is there anything I have overlooked? Can long integer routines benefit from SSE? In particular, can they help me to write a quicker add, sub or mul routine?

share|improve this question
add comment

1 Answer

up vote 14 down vote accepted

You are correct. SSE/AVX are not well-suited for arbitrary precision arithmetic.

You've pretty much covered all the reasons:

  • No carry-propagation support.
  • No 128-bit integer add/sub.
  • No 64 x 64-bit integer multiply. (low or high...)
  • AVX only supports 128-bit wide integer SIMD. (AVX2 will have 256-bit)

The first three of these are pretty much the deal breakers for bignum arithmetic on SSE.

On the other hand, the normal integer instructions (via general-purpose registers) are well suited.

  • Add with carry: adc, sbb
  • 64 x 64-bit multiply (high and low)

So for the foreseeable future, SSE/AVX (or SIMD in general) is not likely to be helpful.

Many have tried and failed to make SSE useful for bignums... it's not happening anytime soon.

There is one exception though. For very large sizes, large multiplications can be done using floating-point FFTs. Those are very vectorizable and actually do benefit from SSE/AVX.

Otherwise, SSE/AVX is pretty much limited to mem-copies and other data-movement.

EDIT + Disclosure:

I'm actually the author of y-cruncher. So I do have a bit of experience in this area.

share|improve this answer
Looking forward to MULX,ADCX,ADOX in Haswell/Broadwell... –  Brett Hale Feb 8 at 15:46
add comment

Your Answer


