Vector Addition (Subtraction)

Josh Liu zliu2 at
Wed Jun 2 21:43:25 CEST 2004

It was mentioned that the implementation of the addition (subtraction) 
routine will involve the computation of the sum (difference) between 
the two operand limbs, or poly-limbs, modulo the radix of the limb, or 
poly-limb, using vector instructions and the carries will be computed 
in as second or third pass. How are the carries computed? Do we have to 
set the nail bit length to be greater than zero for us to be able to do 
this? Is there a way to compute rather a number is greater than another 
number using only subtractions, additions, shifts, and simple bitwise 
operations? These two numbers can take up every bit in a word. Is there 
a fast way to compare these two numbers where the additions and 
subtractions do not give us a carry? This is the problem with the 
Pentium 4 addition (subtraction) routine. We do not have an instruction 
that can compare two unsigned quad-words. I believe that a shift and 
some bitwise operations are definitely involved, sorry to say. The good 
news is that if we can implement this method efficiently, we can do 
four limb operations in two passes on the Pentium 4. The first addition 
pass is easy and involves very little forethought, except maybe for the 
way we handle the cache. The second addition pass will involve some 
planning to work. So the point is to speed up the second addition, or 
rather, comparison, pass. Can I look at some current code that 
implements multi-pass addition (subtraction)? Thank you.

More information about the gmp-devel mailing list