[gambit-list] gsc/gcc isn't as fast as I'd hoped: request for numerical help

Bill Richter richter at math.northwestern.edu
Tue Jan 11 23:37:58 EST 2005


Marc, I got gsc/gcc to work on my mod 2 tensor algebra program, and
I'm getting the right answers.  But it's not as fast as I was hoping!
It's about a thousand lines of code, and it compiled just fine with

gsc drscheme Lambda-defs AdemRelationTables adem7 Curtis-alg4-1

gcc -L. -I. drscheme.c Lambda-defs.c AdemRelationTables.c adem7.c Curtis-alg4-1.c Curtis-alg4-1_.c -lgambc 

and ./a.out gave me the 1180 lines of output I expected.  Proving to
me beyond a shadow of doubt that Gambit is really case-sensitive :)  

I exported LD_LIBRARY_PATH and symlinked the library & include file:

(banach)Gambit-Curtis-alg> echo $LD_LIBRARY_PATH
/rhome/richter/my-gambit/lib
(banach)Gambit-Curtis-alg> ll *gamb*
lrwxrwxrwx    1 richter  users          41 Jan 11 21:01 gambit.h -> /rhome/richter/my-gambit/include/gambit.h
lrwxrwxrwx    1 richter  users          40 Jan 11 21:01 libgambc.so -> /rhome/richter/my-gambit/lib/libgambc.so

But I wonder how I can make it faster.  There are 2 things I'm doing.
There's a fair amount of mod 2 arithmetic to create lookup
multiplication tables, but I think that gets done quickly.  Then the
rest is all applying these multiplication rules and sorting.

So I have "monomials" that are just lists (of length < say 100) of
integers between 0 and say 100.

Then I have "polynomials" that are just lists of monomials, and these
lists can get really long.   Let me just give one example of what I'm
doing:

We call a monomial (a b c ...) admissible if b < 2a, c < 2b,...

The monomial (0 4 12) is made admissible as the polynomial

((6 7 3) (6 5 5) (5 8 3) (5 7 4) (5 5 6) (4 7 5) (4 6 6) (3 6 7) (3 5 8))

and here's how:

  0 4 12 = (3 1 + 2 2) 12 

= 3 (10 3 + 9 4 + 8 5 + 6 7) + 2 (9 5 + 8 6 + 6 8) 

= (6 7 + 5 8) 3 + 5 7 4 + 4 7 5 + 3 6 7 

  + 6 5 5 + (5 5 + 4 6) 6 + 3 5 8

= 6 7 3 + 5 8 3  + 5 7 4 + 4 7 5 + 3 6 7 + 6 5 5 + 5 5 6 + 4 6 6 + 3 5 8

= 6 7 3 + 6 5 5 + 5 8 3  + 5 7 4 + 5 5 6 + 4 7 5 + 4 6 6 + 3 6 7 + 3 5 8

I used the multiplication rules, in order:

 0 4 = 3 1 + 2 2
 1 12 = 10 3 + 9 4 + 8 5 + 6 7 
 2 12 = 9 5 + 8 6 + 6 8 
 3 10 = 6 7 + 5 8 
  3 9 = 5 7 
  3 8 = 4 7 
  2 9 = 6 5 
  2 8 = 5 5 + 4 6 
  2 6 = 3 5 

and I sorted the polynomial by left-lexicographical order.  It was
rather tedious to do by hand right now, but you can see I got the
right answer.  And my program just does boatloads of this kind of
applying the multiplication rules & sorting.

Here's a note on speed.  I want to compute up to t = 80, and while
I've been typing this letter, I computed up to t = 47.  I imagine the
difficulty goes up exponentially with t.  I'm hoping that it will run
up to t = 60 all night.  DrScheme never came close to that, even with
their byte-compiler.  I'm including the output up to t = 30, just so
you can get an idea of my alleged exponential complexity.  All the
output you see is stored in vectors because I have to use this
information later over & over.  I imagined that the cost of vectors
would pay for themselves because of the frequent lookup...

-- 
Best,
Bill 


banach)Gambit-Curtis-alg> ./a.out 
(t = 0)
(t = 1)
(t = 2)
(((1) cycle))
(t = 3)
(t = 4)
(((3) cycle))
(((1 1) cycle))
(t = 5)
(((2 1) cycle))
(t = 6)
(((3 1) (5)))
(((1 1 1) cycle))
(t = 7)
(((1 2 1) (2 3)) ((2 1 1) (4 1)))
(t = 8)
(((7) cycle))
(((3 3) cycle))
(((3 1 1) (5 1)))
(((1 1 1 1) (2 2 1)))
(t = 9)
(((6 1) cycle))
(((3 2 1) (4 3)))
(((1 2 1 1) (2 3 1)) ((2 1 1 1) (4 1 1)))
(t = 10)
(((5 3) cycle) ((7 1) (9)))
(((5 1 1) cycle))
(((3 1 1 1) (4 2 1)))
(t = 11)
(((2 3 3) cycle) ((5 2 1) (6 3)) ((6 1 1) (8 1)))
(((4 1 1 1) cycle))
(((1 2 1 1 1) (2 3 1 1)))
(t = 12)
(((7 3) (11)))
(((3 3 3) cycle) ((7 1 1) (9 1)))
(((5 1 1 1) (6 2 1)))
(t = 13)
(((3 6 1) (4 7)) ((4 3 3) (10 1)) ((7 2 1) (8 3)))
(((1 2 3 3) cycle) ((6 1 1 1) (8 1 1)))
(t = 14)
(((11 1) (13)))
(((3 5 3) (5 7)) ((5 3 3) (9 3)))
(((2 2 3 3) (9 1 1)) ((3 5 1 1) (4 6 1)) ((7 1 1 1) (8 2 1)))
(((2 4 1 1 1) cycle))
(t = 15)
(((5 6 1) (6 7)) ((9 2 1) (10 3)) ((10 1 1) (12 1)))
(((2 3 3 3) (4 5 3)) ((3 2 3 3) (6 3 3)) ((3 6 1 1) (4 7 1)))
(((1 1 2 3 3) (8 1 1 1)) ((3 4 1 1 1) (4 5 1 1)))
(t = 16)
(((15) cycle))
(((7 7) cycle))
(((7 3 3) (11 3)) ((11 1 1) (13 1)))
(((3 3 3 3) (5 5 3)) ((5 5 1 1) (6 6 1)) ((9 1 1 1) (10 2 1)))
(((1 2 2 3 3) (2 4 3 3)) ((2 1 2 3 3) (4 2 3 3)) ((4 4 1 1 1) cycle))
(((1 2 4 1 1 1) cycle))
(t = 17)
(((14 1) cycle))
(((6 5 3) cycle) ((7 6 1) (8 7)) ((11 2 1) (12 3)))
(((3 4 3 3) (4 7 3)) ((4 3 3 3) (8 3 3)) ((10 1 1 1) (12 1 1)))
(((1 2 3 3 3) (2 3 5 3))
 ((3 1 2 3 3) (5 2 3 3))
 ((3 6 1 1 1) (4 7 1 1))
 ((5 4 1 1 1) (6 5 1 1)))
(((1 1 1 2 3 3) (2 2 2 3 3)) ((2 2 4 1 1 1) cycle))
(t = 18)
(((13 3) cycle) ((15 1) (17)))
(((7 5 3) (9 7)) ((13 1 1) cycle))
(((3 5 3 3) (5 7 3))
 ((5 3 3 3) (9 3 3))
 ((6 2 3 3) cycle)
 ((7 5 1 1) (8 6 1))
 ((11 1 1 1) (12 2 1)))
(((3 2 2 3 3) (4 4 3 3)))
(((1 2 1 2 3 3) (2 3 2 3 3))
 ((2 1 1 2 3 3) (4 1 2 3 3))
 ((3 2 4 1 1 1) (6 4 1 1 1)))
(((1 1 2 4 1 1 1) cycle))
(t = 19)
(((9 6 1) (10 7)) ((13 2 1) (14 3)) ((14 1 1) (16 1)))
(((6 3 3 3) (8 5 3)) ((7 2 3 3) (10 3 3)) ((12 1 1 1) cycle))
(((2 3 3 3 3) (4 5 3 3)) ((5 1 2 3 3) cycle) ((7 4 1 1 1) (8 5 1 1)))
(((3 1 1 2 3 3) (4 2 2 3 3)))
(((1 2 2 4 1 1 1) (2 4 4 1 1 1)) ((2 1 2 4 1 1 1) (4 2 4 1 1 1)))
(t = 20)
(((11 7) cycle) ((15 3) (19)))
(((11 3 3) cycle) ((15 1 1) (17 1)))
(((7 3 3 3) (9 5 3)) ((9 5 1 1) (10 6 1)) ((13 1 1 1) (14 2 1)))
(((2 4 3 3 3) cycle) ((6 1 2 3 3) (8 2 3 3)) ((8 4 1 1 1) cycle))
(((3 4 4 1 1 1) cycle))
(((1 2 1 1 2 3 3) (2 3 1 2 3 3)) ((3 1 2 4 1 1 1) (5 2 4 1 1 1)))
(((1 1 1 2 4 1 1 1) (2 2 2 4 1 1 1)))
(t = 21)
(((10 5 3) cycle) ((11 6 1) (12 7)) ((12 3 3) (18 1)) ((15 2 1) (16 3)))
(((3 6 5 3) (4 7 7))
 ((5 10 1 1) (6 11 1))
 ((8 3 3 3) cycle)
 ((14 1 1 1) (16 1 1)))
(((3 4 3 3 3) (4 7 3 3)) ((7 1 2 3 3) (9 2 3 3)) ((9 4 1 1 1) (10 5 1 1)))
(((1 2 3 3 3 3) (2 3 5 3 3)) ((6 2 4 1 1 1) cycle))
(((3 2 2 4 1 1 1) (4 4 4 1 1 1)))
(((1 2 1 2 4 1 1 1) (2 3 2 4 1 1 1)) ((2 1 1 2 4 1 1 1) (4 1 2 4 1 1 1)))
(t = 22)
(((19 1) (21)))
(((5 7 7) cycle) ((11 5 3) (13 7)) ((13 3 3) (17 3)))
(((5 7 3 3) cycle)
 ((9 3 3 3) cycle)
 ((10 2 3 3) (17 1 1))
 ((11 5 1 1) (12 6 1))
 ((15 1 1 1) (16 2 1)))
(((3 5 3 3 3) (4 6 5 3)) ((3 6 2 3 3) cycle))
(((1 2 4 3 3 3) cycle)
 ((5 4 4 1 1 1) (8 1 2 3 3))
 ((7 2 4 1 1 1) (10 4 1 1 1)))
(((5 1 2 4 1 1 1) cycle))
(((3 1 1 2 4 1 1 1) (4 2 2 4 1 1 1)))
(t = 23)
(((13 6 1) (14 7)) ((17 2 1) (18 3)) ((18 1 1) (20 1)))
(((5 6 5 3) (6 7 7)) ((10 3 3 3) (12 5 3)) ((11 2 3 3) (14 3 3)))
(((3 6 3 3 3) (4 7 5 3))
 ((4 5 3 3 3) cycle)
 ((5 10 1 1 1) (6 11 1 1))
 ((9 1 2 3 3) (16 1 1 1))
 ((11 4 1 1 1) (12 5 1 1)))
(((2 2 4 3 3 3) cycle) ((3 5 1 2 3 3) (4 6 2 3 3)))
(((2 3 4 4 1 1 1) cycle)
 ((5 2 2 4 1 1 1) (6 4 4 1 1 1))
 ((6 1 2 4 1 1 1) (8 2 4 1 1 1)))
(((4 1 1 2 4 1 1 1) cycle))
(((1 2 1 1 2 4 1 1 1) (2 3 1 2 4 1 1 1)))
(t = 24)
(((15 7) (23)))
(((7 7 7) cycle) ((15 3 3) (19 3)) ((19 1 1) (21 1)))
(((6 6 5 3) cycle)
 ((11 3 3 3) (13 5 3))
 ((13 5 1 1) (14 6 1))
 ((17 1 1 1) (18 2 1)))
(((10 1 2 3 3) (12 2 3 3)))
(((3 2 4 3 3 3) (5 6 2 3 3))
 ((3 6 1 2 3 3) (4 7 2 3 3))
 ((7 4 4 1 1 1) (12 4 1 1 1)))
(((1 1 2 4 3 3 3) cycle)
 ((3 3 4 4 1 1 1) (4 5 1 2 3 3))
 ((7 1 2 4 1 1 1) (9 2 4 1 1 1)))
(((5 1 1 2 4 1 1 1) (6 2 2 4 1 1 1)))
(t = 25)
(((7 14 1) (8 15)) ((14 5 3) (22 1)) ((15 6 1) (16 7)) ((19 2 1) (20 3)))
(((7 6 5 3) (8 7 7)) ((12 3 3 3) (16 3 3)) ((18 1 1 1) (20 1 1)))
(((4 7 3 3 3) cycle) ((11 1 2 3 3) (13 2 3 3)) ((13 4 1 1 1) (14 5 1 1)))
(((5 5 1 2 3 3) (6 6 2 3 3)))
(((1 2 2 4 3 3 3) (2 3 6 2 3 3))
 ((2 1 2 4 3 3 3) (4 2 4 3 3 3))
 ((3 6 2 4 1 1 1) (4 8 4 1 1 1))
 ((4 3 4 4 1 1 1) (10 2 4 1 1 1))
 ((7 2 2 4 1 1 1) (8 4 4 1 1 1)))
(((1 2 3 4 4 1 1 1) cycle) ((6 1 1 2 4 1 1 1) (8 1 2 4 1 1 1)))
(t = 26)
(((23 1) (25)))
(((7 13 3) (9 15)) ((9 7 7) (21 3)) ((15 5 3) (17 7)))
(((3 5 7 7) cycle)
 ((7 13 1 1) (8 14 1))
 ((8 6 5 3) (21 1 1))
 ((13 3 3 3) (17 3 3))
 ((15 5 1 1) (16 6 1))
 ((19 1 1 1) (20 2 1)))
(((3 5 7 3 3) cycle) ((7 6 2 3 3) (14 2 3 3)))
(((2 4 5 3 3 3) cycle)
 ((3 3 6 2 3 3) (4 8 3 3 3))
 ((5 8 4 1 1 1) (6 12 1 1 1))
 ((9 4 4 1 1 1) (12 1 2 3 3))
 ((11 2 4 1 1 1) (14 4 1 1 1)))
(((3 1 2 4 3 3 3) (5 2 4 3 3 3))
 ((3 5 4 4 1 1 1) (4 7 1 2 3 3))
 ((5 3 4 4 1 1 1) (6 5 1 2 3 3)))
(((1 1 1 2 4 3 3 3) (2 2 2 4 3 3 3))
 ((2 2 3 4 4 1 1 1) (9 1 2 4 1 1 1))
 ((3 5 1 2 4 1 1 1) (4 6 2 4 1 1 1))
 ((7 1 1 2 4 1 1 1) (8 2 2 4 1 1 1)))
(((2 4 1 1 2 4 1 1 1) cycle))
(t = 27)
(((9 14 1) (10 15)) ((17 6 1) (18 7)) ((21 2 1) (22 3)) ((22 1 1) (24 1)))
(((4 5 7 7) cycle)
 ((5 10 5 3) (6 11 7))
 ((6 11 3 3) (8 13 3))
 ((7 14 1 1) (8 15 1))
 ((9 6 5 3) (10 7 7))
 ((14 3 3 3) (16 5 3))
 ((15 2 3 3) (18 3 3)))
(((5 8 3 3 3) (20 1 1 1)) ((7 12 1 1 1) (8 13 1 1)) ((15 4 1 1 1) (16 5 1 1)))
(((3 4 5 3 3 3) (4 5 7 3 3))
 ((6 2 4 3 3 3) (13 1 2 3 3))
 ((7 5 1 2 3 3) (8 6 2 3 3)))
(((3 2 2 4 3 3 3) (4 3 6 2 3 3))
 ((5 6 2 4 1 1 1) (6 8 4 1 1 1))
 ((9 2 2 4 1 1 1) (10 4 4 1 1 1))
 ((10 1 2 4 1 1 1) (12 2 4 1 1 1)))
(((1 2 1 2 4 3 3 3) (2 3 2 4 3 3 3))
 ((2 1 1 2 4 3 3 3) (4 1 2 4 3 3 3))
 ((3 2 3 4 4 1 1 1) (6 3 4 4 1 1 1))
 ((3 6 1 2 4 1 1 1) (4 7 2 4 1 1 1)))
(((1 1 2 3 4 4 1 1 1) (8 1 1 2 4 1 1 1))
 ((3 4 1 1 2 4 1 1 1) (4 5 1 2 4 1 1 1)))
(t = 28)
(((23 3) (27)))
(((7 11 7) (11 15)) ((11 7 7) (19 7)) ((23 1 1) (25 1)))
(((5 5 7 7) (19 3 3))
 ((7 11 3 3) (9 13 3))
 ((9 13 1 1) (10 14 1))
 ((15 3 3 3) (17 5 3))
 ((17 5 1 1) (18 6 1))
 ((21 1 1 1) (22 2 1)))
(((3 6 6 5 3) cycle)
 ((5 5 7 3 3) (10 6 5 3))
 ((5 9 3 3 3) (6 10 5 3))
 ((5 10 2 3 3) (6 12 3 3))
 ((14 1 2 3 3) (16 2 3 3)))
(((4 4 5 3 3 3) (16 4 1 1 1))
 ((5 3 6 2 3 3) (6 8 3 3 3))
 ((7 2 4 3 3 3) (9 6 2 3 3))
 ((7 8 4 1 1 1) (8 12 1 1 1)))
(((1 2 4 5 3 3 3) (2 4 7 3 3 3))
 ((5 1 2 4 3 3 3) (11 4 4 1 1 1))
 ((7 3 4 4 1 1 1) (8 5 1 2 3 3))
 ((11 1 2 4 1 1 1) (13 2 4 1 1 1)))
(((3 1 1 2 4 3 3 3) (4 2 2 4 3 3 3))
 ((5 5 1 2 4 1 1 1) (6 6 2 4 1 1 1))
 ((9 1 1 2 4 1 1 1) (10 2 2 4 1 1 1)))
(((1 2 2 3 4 4 1 1 1) (2 4 3 4 4 1 1 1))
 ((2 1 2 3 4 4 1 1 1) (4 2 3 4 4 1 1 1))
 ((4 4 1 1 2 4 1 1 1) cycle))
(((1 2 4 1 1 2 4 1 1 1) cycle))
(t = 29)
(((11 14 1) (12 15)) ((19 6 1) (20 7)) ((20 3 3) (26 1)) ((23 2 1) (24 3)))
(((4 7 7 7) (10 13 3))
 ((6 5 7 7) (18 5 3))
 ((7 10 5 3) (8 11 7))
 ((7 12 3 3) (8 15 3))
 ((11 6 5 3) (12 7 7))
 ((22 1 1 1) (24 1 1)))
(((2 3 5 7 7) cycle)
 ((5 10 3 3 3) (6 11 5 3))
 ((6 9 3 3 3) (8 11 3 3))
 ((7 8 3 3 3) (16 3 3 3))
 ((7 14 1 1 1) (8 15 1 1))
 ((9 12 1 1 1) (10 13 1 1))
 ((15 1 2 3 3) (17 2 3 3))
 ((17 4 1 1 1) (18 5 1 1)))
(((2 3 5 7 3 3) cycle)
 ((3 4 7 3 3 3) (4 6 6 5 3))
 ((5 4 5 3 3 3) (6 5 7 3 3))
 ((5 9 1 2 3 3) (6 10 2 3 3))
 ((9 5 1 2 3 3) (10 6 2 3 3)))
(((2 2 4 5 3 3 3) (14 2 4 1 1 1))
 ((5 2 2 4 3 3 3) (6 3 6 2 3 3))
 ((6 1 2 4 3 3 3) (8 2 4 3 3 3))
 ((7 6 2 4 1 1 1) (8 8 4 1 1 1))
 ((11 2 2 4 1 1 1) (12 4 4 1 1 1)))
(((3 4 3 4 4 1 1 1) (4 7 4 4 1 1 1))
 ((4 1 1 2 4 3 3 3) (8 3 4 4 1 1 1))
 ((10 1 1 2 4 1 1 1) (12 1 2 4 1 1 1)))
(((1 2 1 1 2 4 3 3 3) (2 3 1 2 4 3 3 3))
 ((3 1 2 3 4 4 1 1 1) (5 2 3 4 4 1 1 1))
 ((3 6 1 1 2 4 1 1 1) (4 7 1 2 4 1 1 1))
 ((5 4 1 1 2 4 1 1 1) (6 5 1 2 4 1 1 1)))
(((1 1 1 2 3 4 4 1 1 1) (2 2 2 3 4 4 1 1 1)) ((2 2 4 1 1 2 4 1 1 1) cycle))
(t = 30)
(((27 1) (29)))
(((11 13 3) (13 15)) ((19 5 3) (21 7)) ((21 3 3) (25 3)))
(((5 7 7 7) (9 11 7))
 ((7 5 7 7) (13 7 7))
 ((7 13 3 3) (9 15 3))
 ((11 13 1 1) (12 14 1))
 ((18 2 3 3) (25 1 1))
 ((19 5 1 1) (20 6 1))
 ((23 1 1 1) (24 2 1)))
(((2 4 5 7 7) (9 11 3 3))
 ((3 3 5 7 7) (17 3 3 3))
 ((7 5 7 3 3) (12 6 5 3))
 ((7 9 3 3 3) (8 10 5 3))
 ((7 10 2 3 3) (8 12 3 3)))
(((3 3 5 7 3 3) (5 6 6 5 3))
 ((5 10 1 2 3 3) (6 11 2 3 3))
 ((6 4 5 3 3 3) (11 6 2 3 3))
 ((7 3 6 2 3 3) (8 8 3 3 3))
 ((9 8 4 1 1 1) (10 12 1 1 1))
 ((13 4 4 1 1 1) (16 1 2 3 3))
 ((15 2 4 1 1 1) (18 4 1 1 1)))
(((3 2 4 5 3 3 3) (4 4 7 3 3 3))
 ((5 7 4 4 1 1 1) (6 9 1 2 3 3))
 ((7 1 2 4 3 3 3) (9 2 4 3 3 3))
 ((9 3 4 4 1 1 1) (10 5 1 2 3 3))
 ((13 1 2 4 1 1 1) cycle))
(((5 1 1 2 4 3 3 3) (6 2 2 4 3 3 3))
 ((6 2 3 4 4 1 1 1) cycle)
 ((7 5 1 2 4 1 1 1) (8 6 2 4 1 1 1))
 ((11 1 1 2 4 1 1 1) (12 2 2 4 1 1 1)))
(((3 2 2 3 4 4 1 1 1) (4 4 3 4 4 1 1 1)))
(((1 2 1 2 3 4 4 1 1 1) (2 3 2 3 4 4 1 1 1))
 ((2 1 1 2 3 4 4 1 1 1) (4 1 2 3 4 4 1 1 1))
 ((3 2 4 1 1 2 4 1 1 1) (6 4 1 1 2 4 1 1 1)))
(((1 1 2 4 1 1 2 4 1 1 1) cycle))


More information about the Gambit-list mailing list