Sumsets in Pari/GP

[CRGreathouse]

I was looking for an efficient way to calculate sumsets. The sumset A + B is {a + b: a in A, b in B}; A + B could have up to #A * #B elements, though it could also have fewer than #A + #B elements. (Here #X denotes the length of X.)

I'm using an interpreted programming language which is domain-specific for math, Pari/GP. The code isn't too hard to follow -- it looks like C or JavaScript, though it's #X instead of X.length or the like. I have a description of the algorithm below; I'm looking for an elegant way to improve it.

Here's the code I'm using at the moment:

Code: Select all

sumset(a,b)={
   local(v);
   v=vector(#a * #b);
   for(i=1,#a,
      for(j=1,#b,
         v[(i-1)*#b+j] = a[i] + b[j]
      )
   );
   vecsort(eval(Set(v)))
}

The code takes two vectors of arbitrary size and returns a sorted vector.

• Create a blank vector v to hold the elements.
• Assign to each vector element a sum
• Remove duplicates by casting to a set (slow: turns numbers to strings!)
• Cast from back to numeric form (slow)
• Sort the vector (relatively slow)

Any ideas on improving this?