0

What is the most space efficient way to store arbitrary length univariate polynomials? I have a large amount of polynomials that look like

3*x^7  + 12*x - 13
9*x^32 - x^14 + 2*x^3 - 9
...

Each polynomial is composed of an arbitrary number of integer coefficients for a given power, e.g. the following polynomials could be stored as

(3,7) (12,1) (-13,0)
(9,32) (1,14) (2,3) (-9, 0)

which is in fact exactly what I do now. I have a SQLite schema that looks something like

 CREATE TABLE poly_lookup (
     poly_id INTEGER PRIMARY KEY AUTOINCREMENT
 ); 
 CREATE TABLE poly (
     poly_id INTEGER,
     coeff   INTEGER,
     power   INTEGER
 );
 CREATE INDEX idx_poly  ON poly(poly_id);

This works, but I'm not sure this is the most space efficient solution. caveat responsum, I only know SQLite, but I would be willing to learn a completely new type of database system (mongodb, neo4j, ...) if it would help the solution.

3
  • Your solution seems legit. I would add a NOT NULL constraint to poly.poly_id column to ensure each row in poly is associated with a polynomial, but otherwise it's a reasonable RBDMS solution to the problem. If you only care about space and nothing else, you could denormalize your schema and put polynomial coefficients and powers into a string field in the poly_lookup table (serizalized, i.e. 3,7,12,1,-13,0 for your first poly) but that would take all the flexibility out of the solution.
    – zgguy
    May 28 '15 at 20:48
  • @zgguy Wouldn't storing them as strings be inefficient? They are integers, so I feel like there should be a more optimal way of storing them.
    – Hooked
    May 28 '15 at 20:57
  • Well, yes, integers should be stored as integers. I definitively think your current solution is much better than storing numbers as strings, I merely suggested it as something to try if you really want to. It is true that a single integer will usually take less place on disk than "serialized" as varchar, however, you have 3 integers per row in your table + you have an index, which can take up a significant amount of space. Bottom line - you can't be sure until you try. But, again, your current solution is probably the way to go, not because of storage, but because of flexibility.
    – zgguy
    May 28 '15 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.