2

So I have the following struct definition for my 1024-bit number (I want to use 2's complement representation here and I am on a 32-bit system):

typedef struct int1024
{
    int32_t num[32]; //should I use uint32_t?
} int1024;

Basically an array that holds the segments of the number.

For add since, signed and unsigned addition are the same. I can simply use the instructions add and adc to carry out the extended operation for my bigger array.

Now for multiplication. I was able to get an unsigned multiplication to work using a combination of imul (using the upper and lower results) and adc using the classic O(n^2) multiplication algorithm. However I need signed multiplication for my results. I know people say just to use the signed magnitude version. i.e. take the 2's complement when negative and at the end apply 2's complement if needed. But all the extra noting and adding 1 will be really expensive, since I need to do a lot of multiplications. Is there a technique for doing large signed multiplication for number representations like this. (I don't really want any branching or recursive calls here). I guess one of my main problems is how to deal with carry and the high part of the multiplication of negative numbers. (just an idea, maybe I could use a combination of signed and unsigned multiplication, but I don't know where to begin). If you don't have time for 1024 bits, a 128 bit answer will suffice (I will just generalize it).

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
yosmo78
  • 489
  • 4
  • 13
  • 2
    You would want to use an unsigned integer type for the array elements. Note that in an NxN->N integer multiplication (argument width = result width) it does not matter whether the multiplication is a signed or unsigned operation: the least significant N bits of the result are the same. Whether the multiply is signed or unsigned matters for the most significant N bits of a wide (NxN->2N) multiply, or the equivalent multiply-high operation. In that case the most significant bits of the signed multiply result can easily be generated from the most significant bits of the unsigned multiply. – njuffa Mar 16 '21 at 21:40
  • 1
    Are you doing this as an exercise? The `GMP` library does this and much more. See: https://gmplib.org/ BTW, what you call `num` they use `unsigned long long` for (if machine is natively 64 bits) And, each number maintains a count of cells, so they handle variable length numbers and grow as needed [which can speed things up as it is slow to do 32 multiplies if (e.g.) each number only uses a few number of bits] – Craig Estey Mar 16 '21 at 21:44
  • The negation is relatively cheap compared with the 'longhand' multiplication. My technique for big arithmetic is to work with 32-bit arrays and 64-bit intermediate values. – Weather Vane Mar 16 '21 at 21:52
  • @CraigEstey yah, as an exercise, thanks for the link. Let me see if I can find the source for their library – yosmo78 Mar 16 '21 at 22:02
  • @WeatherVane I am planning to port this to the GPU afterwards as more practice, and I don't want to have branching/negation since that would cause thread divergence. – yosmo78 Mar 16 '21 at 22:02
  • @njuffa thanks for the thoughts, much appreciated – yosmo78 Mar 16 '21 at 22:02
  • Try experimenting to see if *ignoring* the sign does it for you (assuming the product does not overflow). 8-bit example of `-5 * -23` which is binary `11111011 * 11101001 = 01110011` which is `115` decimal. Another example of `-5 * 23` which is binary `11111011 * 00010111 = 10001101` which is `-115` decimal. – Weather Vane Mar 16 '21 at 22:05
  • @WeatherVane I have tried doing completely unsigned, the problem is with 32-bit chunks there is carry between them. I think I should try unsigned for upper half of the internal products and signed for the lower. But I am still experimenting. Thanks for the thoughts! – yosmo78 Mar 16 '21 at 22:10
  • I am not suggesting you ignore the carry between elements, but yes, has to be carried over. I am not sure if its possible without carries. – Weather Vane Mar 16 '21 at 22:11
  • @WeatherVane I think you are right. I must have a bug in my unsigned mult code then. I will post an answer when I figure it out. thanks! – yosmo78 Mar 16 '21 at 22:45
  • 1
    @WeatherVane On ARM I used UMLAL (Unsigned Multiply and Accumulate Long) that does 32x32 + 32 -> 64, very handy to propagate the Carry. Is there anything similar in x86 ISA? – tum_ Mar 16 '21 at 22:46
  • Yes, 32 * 32 bit multiply to 64 bits but add it yourself: you'll need more than 64 bits accumulated. Unlees you want to go to bit shifting, what other way is there? The upper 32 bits of the product is the carry over for the next multiplication. But what is the question? Yes, you must use *unsigned* array. – Weather Vane Mar 16 '21 at 23:42
  • 1
    @tum_: x86's has always had widening multiply, but still doesn't have accumulate. (https://www.felixcloutier.com/x86/mul, up to 64x64 => 128-bit in x86-64 code.) Intel has a whitepaper comparing that against BMI2 MULX (widening mul that doesn't touch FLAGS, so it doesn't disturb ADC carry chains, and fewer implicit operands, only RDX input), and against MULX + ADOX/ADCX (Broadwell) to allow 2 independent carry chains (in CF and in OF): https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf for 512x64-bit or 512x512 – Peter Cordes Mar 17 '21 at 03:53

1 Answers1

2

Note that in a 1024-bit integer only the very top bit, bit 1023, is the sign bit and has a place-value of -(2**1023). All the other bits have their normal +(2**pos) place value. i.e. the lower "limbs" all need to be treated as unsigned when you do widening multiplies on them.

You have one sign bit and 1023 lower bits. Not one sign bit per limb.

Also, the difference between signed and unsigned multiply is only in the high half of a widening multiply (N x N => 2N bits). That's why x86 has separate instructions for imul r/m64 and mul r/m64 to do a full-multiply into RDX:RAX (https://www.felixcloutier.com/x86/imul vs. https://www.felixcloutier.com/x86/mul). But for non-widening there's only imul r, r/m and imul r, r/m, imm which compilers use for both unsigned and signed (and so should humans).

Since you want a 1024x1024 => 1024-bit product which discards the upper 1024 bits, you can and should just make your whole thing unsigned.

When you're writing in asm, you can use whatever chunk size you can, e.g. 64-bit in 64-bit mode, not limiting yourself to the C chunk size.

See https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf for how to use BMI2 mulx (leaves FLAGS untouched so doesn't disturb adc chains, and only has RDX as an implicit input, with other source and both outputs being explicit, saving on MOV instructions). And optionally also Broadwell ADOX / ADCX to run two dep chains in parallel to get more ILP for medium sized BigInteger stuff like 512x512-bit or 512x64-bit (which they use as an example).

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847