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

LinkBack Thread Tools Display Modes
May 19th, 2008, 01: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:

	v=vector(#a * #b);
			v[(i-1)*#b+j] = a[i] + b[j]
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!


  My Computer Forum > Computer Science Forum > Algorithms

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 04:32 AM

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