[gambit-list] Re: Scheme/C help request for code needed for Math paper

Bill Richter richter at math.northwestern.edu
Tue Jan 25 20:45:49 EST 2005


   (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 




More information about the Gambit-list mailing list