My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
LinkBack Thread Tools Display Modes
May 19th, 2008, 02:02 PM   #1
 
Joined: Dec 2007
Posts: 232
Sumsets in Pari/GP

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:
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.[/*:m:2tgf291h]
  • Assign to each vector element a sum[/*:m:2tgf291h]
  • Remove duplicates by casting to a set (slow: turns numbers to strings!)[/*:m:2tgf291h]
  • Cast from back to numeric form (slow)[/*:m:2tgf291h]
  • Sort the vector (relatively slow)[/*:m:2tgf291h]
Any ideas on improving this?
CRGreathouse is offline  
 

My Computer Forum is free to register and we welcome everyone!

Reply

  My Computer Forum > Computer Science Forum > Algorithms

Tags
pari or gp, sumsets



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
simple pari-GP code question billymac00 Programming 0 November 8th, 2013 05:32 AM





Copyright © 2017 My Computer Forum Forum. All rights reserved.