(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