Thanks very much, Guillaume, & Marc! Your profiler sounds like a good idea, and I'll try it. I knew adem.scm, which does the sorting, was the hotspot, and I sorta said so in my README file, e.g. "admissify takes a term and applies a zillion Adem relations to it in order to make it admissible. ... We're only going to admissify terms (a_1 ... a_s) with say s, a_i < 100. There's a lot of this going on, so it would be nice to do it *very quickly*, but no one admissify should take that long, on our fast machines." "As far as speed goes, I'm convinced that all the work goes into calc-d, which calls Curtis-alg a reasonable small number of times, but each Curtis-alg can involve a ton of time. Curtis-alg must construct a large simplified sorted polynomial, and keep taking d (which calls admissify), and merging the (d a)'s into the large polynomial. That's what takes the time. My advisor talked about millions of terms here." Also, you can speed up your code quite a bit simply by adding some declarations in your code. You can read about it in the documentation: http://www.iro.umontreal.ca/~gambit/doc/gambit-c_6.html#IDX153 Now this is just the Gambit Manual, which you can read in Emacs with info files, right? There's not enough info here for me: These declarations are compatible with the semantics of Scheme. Typically used declarations that enhance performance, at the cost of violating the Scheme semantics, are: (standard-bindings), (block), (not safe) and (fixnum). That's the only hit in the Manual for the string "(fixnum)". Ah, but I see there's lots of hits for just "fixnum", so I'll read up. Something like this [say, at the top of 'Curtis-algorithm.scm']: (declare (standard-bindings) (fixnum) (not safe) (inline) (inlining-limit 1000) (block)) will give you some boost (I assume your numerals are all fixnums, but that might be wrong). Of course there are tradeoffs to doing this, so make sure you understand what those declarations means. How about I tell you, since I have manual troubles: I have lists of integers a with -1 <= x < 100, and they're not long lists. I call them monomials, or terms. Then I have loooong lists of terms, called polynomials.

Guillaume, I'm really getting almost *30* times faster!!! Your advice is better than I thought. I did t = 0 to 51 in 4.7 minutes. Yahoo! you can speed up your code quite a bit simply by adding some declarations in your code....Something like this [say, at the top of 'Curtis-algorithm.scm']: (declare (standard-bindings) (fixnum) (not safe) (inline) (inlining-limit 1000) (block)) Yesterday I goofed, and didn't put this quite at the top of the file. I put it below the line (include "adem.scm") where as your profiler showed, most of the action takes place. Now with your code at the top, I did t = 0 to 51 in 4.7 minutes, but my previous mark was 134.9 minutes, in 4 stages: ;; t = 0--45, 489826 ms real time, 8.1 minutes ;; t = 46--49 1510112 ms real time, 25.2 minutes ;; t = 50, 2484842 ms real time, 41.4 minutes ;; t = 51 3613899 ms real time, 60.2 minutes I calculate (/ 134.9 4.7) 28.70212765957447 My goof graphically demonstrates the truth of the Gambit info node "Miscellaneous extensions": - special form: declare DECLARATION... This form introduces declarations to be used by the compiler ... Declarations are lexically scoped in the same way as macros. Yup! I said something else dumb yesterday: I whinged that your profiler wouldn't work with gsc/gcc. But of course that's true: your profiler looks at the hits of the Scheme program. If it was gcc, it would looks at the hits of the C program, which wouldn't mean anything to us, and with `gcc -O2', the C line numbers wouldn't mean anything at all! I remember that from running gdb for Stallman on Emacs years ago: if you want to gdb emacs, you can't make Emacs optimized. I also tried rewriting my code to use s8vectors instead of lists for Monomials, and it is not running faster. At least I got the right answers up through (s, t) = (11, 50). Ah, I think I see the problem! I have multiple definitions: (define Min_t 55) (define Max_t 55) (define Min_t 0) (define Max_t 51) I should've commented the first pair out. It's funny, but I've noticed this slows the a.out down by quite a bit. Dunno why. The homogeneous vectors look like really nice stuff, partly because of the extra functions we don't have for ordinary vectors: - procedure: s8vector-append S8VECTOR... - procedure: subs8vector S8VECTOR START END Perhaps that should say - procedure: subs8vector S8VECTOR START (- END 1)

(Guillaume has profiled your original code and the results are at: http://www.iro.umontreal.ca/~germaing/tmp/richter/). Quite cool stuff! Thanks, Marc, and Guillaume! I think I understand what your profiler does, and I looked at the link. I'll post this here in case there are other newbies out there who, like me, were reluctant to try the profiler, or maybe didn't see the point. I was surprised to see that Mono-left-lex of Lambda-defs.scm gets 50% of the hits, topping the charts, followed by merge-1, which gets 22%. I guess that sounds right, but I goofed something up, you see. I knew the toughest part of the code is these 2 lines of Curtis-alg of Curtis-algorithm.scm: (let ([X+db (merge-1 (d b) X Mono-left-lex)]) (Curtis-alg a X+db top-level-tags)) X is a huge sorted polynomial, and we have to merge this little sorted polynomial (d b) into it. So merge-1 is the hog, except that merge-1 keeps calling Mono-left-lex, which is the less-than? function. So it makes sense that Mono-left-lex would be the real hog. But if I'd understood that, I would have moved Mono-left-lex to adem.scm, to put all the sorting-rats in the same file-trap. Here's how I got 22%. It would be nice if I could paste better from the browser window into Emacs. Maybe that's impossible because of the cool colors. But I pasted all of merge-1 in, and got I pasted some of the browser into Emacs and got 31: [1374/45367] (cond 32: [458/45367] etc, and then I used an Emacs kbd macro to regexp-search for the numerators and add up them up: (+ 1374 458 463 2115 1744 639 56 652 46 620 1730) 9897 (/ 9897.0 45367) 0.21815416492163908 That's 22%. Did I get that right? None of the other hits seem high: [1567/45367] (Curtis-alg a X+db top-level-tags)) so about 3% of the time, and quicksort is a bit lower, and filter of drscheme.scm gets hits, but that's because of quicksort. Using the same paste + kbd macro on Mono-left-lex, I get (+ 3656 1040 951 2448 2792 4670 1613 1734 3710) 22614 (/ 22614.0 45367) 0.4984680494632662 or 50%. Thanks! What value of Min_t & Max_t did you use? I'll try values myself. Anyway, I guess I see the point of your profiler: by making code changes, I can see how the hits & colors change, so I see whether I'm making it faster or not. I've got questions right now about accumulators that I can attack this way. By `quite cool stuff', I assume you mean the program itself, which was popular among my mathematicians 20 years ago, and there's one good book written on coding the Curtis algorithm, Tangora's AMS Memoir I cited in my README. None of this cool stuff is due to me. But 20 years ago, there was a lot of good Math left unsettled, and their programs probably no longer run. Tangora's programs were in Snobol, e.g. My aim here (i.e. the Subject `Math paper') is to write a paper on how to do these calculations by hand up to say t = 30. The problem is that the paperwork gets completely out of hand, even though the Math is tractable. So the only way to do it is to write computer programs that calculate and print the answers, and then we mathematically check the answers. It turns out there's no real cheating: we just use the computer to generate conjectures and paperwork. I think this is an interesting mixture of Math and computers. But 2 things are important: 1) The computer code should be human-readable. Someone who understands the Curtis algorithm ought to be able to flip through the code and say, yeah I understand, and then they will feel confident to run the code, and play with it even. I've just written the dumbest vanilla version of the program. There's all kinds of cool tricks to play here, some described by Tangora. 2) The computer code should run reasonably fast compared to the stone-age code of 20 years ago. On DrScheme (from which I learned a lot of good programming tips), I was much slower than the stone-age. That's an gaffe that would sink my paper. This is just PR, I know. -- Best, Bill