Big book of algorithms

March 5, 2008 7:02 AM

If you could use a great big free handbook of discrete math and algorithms, Jörg Arndt's fxtbook wants to be your friend. Plain text table of contents to whet your appetite.
posted by Wolfdog (11 comments total)

via
posted by Wolfdog at 7:04 AM on March 5, 2008

Wow, this is awesome.

Unfortunately, I think I may be too dumb to benefit. The only one I looked at in detail, 1.12 (bitwise rotation to the left), makes no sense to me. (Update: After studying it some more, it still makes no sense, but for a completely different reason. That's progress.)

Also, the explanation after that seems to imply that the result depends on the awesomeness of gcc, which is a bit optimistic for users of other compilers.
posted by DU at 7:18 AM on March 5, 2008

I love posts that make me feel dumb. wait, that didn't come out quite right ... Anyway, the probability that I'd ever use any of this is effectively 0, but it's neat to know that mathematicians have come up with all this cool stuff. Some of it, like Fourier transforms, lurks inside the software that drives some of our lab instruments, especially spectrometers of various types, but we don't actually deal with the math.

Other than that, I love the geek-speak of mathematics - it verges on poetry. Binary necklaces, star-transpositions and eigenvectors just sound awesomely cool, whatever the hell they are.
posted by Quietgal at 7:32 AM on March 5, 2008

Quietgal, I have tacked to my corkboard here a few pages of quotes from my complex analysis prof, one of the greatest mathematical quote machines ever to make vague hopeless gestures with a stick of chalk. Anyway, beside little gems like "It's a mistake to ever leave the real line" and "You don't have to be very big to be dense", and "There's no need to fill in what you're summing over or f-ing of", there is this one: "This pseudohyperbolic distance is a conformal invariant. [pause] Mathematicians like to say words like that."

Also on language: "I don't know why Gamelin doesn't use the term conformal automorphism [he uses 'conformal self map']. That's how you translate it. Morphism for map and auto for self."
And: "That's why they are called lunar domains: because they are circles and the moon is round."
posted by Wolfdog at 7:58 AM on March 5, 2008 [2 favorites]

Sweet! I deal with the permutation group a lot, and it looks like this has a lot of things I haven't seen before (though maybe just old things stated in different terms). And the entire section dedicated to 'Algorithms for Finite Fields?' Awesome! Thanks for the link, Wolfdog.
posted by kaibutsu at 8:15 AM on March 5, 2008

Meh. It looks like a DSP-oriented combination of HAKMEM and The Art, but without the proofs, the exercises, the illustrations, the historical exegesis, the clever quotations, the standard notation, or the readable typesetting. (But to the author's credit, with source code and without Knuth's fake machine language or a price tag.)

(For dog's sake, heapsort as the only comparison-based sorting algorithm? I mean really, heapsort? At least he avoided bubblesort.)

But then, I haven't been a programmer for a long time, so maybe I'm just the wrong audience.

Oooh, pretty! Walsh transforms!
posted by erniepan at 8:55 AM on March 5, 2008

And in case you thought there was no practical use for all this, consider this cautionary tale.
posted by skippyhacker at 9:03 AM on March 5, 2008

Wolfdog, I had a math professor at Purdue (Bob Zink, if you ever have the pleasure of meeting him) who had several established mannerisms when he was lecturing:

• When he was nearing the end of a proof: "And now for the coup de grâce — that's when you attack your enemy with a lawn mower." (It makes more sense if you read it out loud.)
• When summing something together elegantly: "Put them all together and they spell 'mother'..."
• When a variable named i or I was the subject of a sentence: "i is — no, wait, pardon me, i am..."

That (Modern Algebra) was a crazy class. We must have spent a week proving the transcendence of π, and Bézout's identity must have made an appearance every lecture.

Anyway, regarding the OP, great link! Chapter 27 looks like a really good overview of bignum multiplication techniques. Sure, you can use GMP, but it's always good to know what's going on.
posted by pmdboi at 9:18 AM on March 5, 2008

I also have recorded this little exchange that took place during a longish proof.
Student: Are the f_n's polynomials?
Prof: No! [Apparently really, truly annoyed at student for not keeping things straight - a rare occurrence]
Prof: [Firmly setting the matter straight] They are rational functions without poles!
Prof: [chuckling] Maybe they are polynomials.
Prof: [laughing riotously] Yes! They are polynomials.
posted by Wolfdog at 10:30 AM on March 5, 2008 [3 favorites]

One of my favorite non-sequiturs was in a signal processing class. The prof is going along with some proof involving imaginary numbers, which are typically represented using j instead of i to avoid confusion with what is commonly also the symbol for current. He's writing as he speaks some formula out-loud, inserting "wait, must remember, always j*b, never b*j" and continues on without missing a beat. The handful of us that caught it busted out laughing, while the rest of the class just looked confused.
posted by Bugg at 11:25 AM on March 5, 2008

It's more narrow in scope, but I've found Hacker's Delight useful.
posted by Crabby Appleton at 12:56 PM on March 5, 2008