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))
