[earthicus]

Thanks for stopping by! I'd like to ask a question / make a request. Unlike most of the people here, I was trained in mathematics but am just learning how to program, so I was wondering if you had any desire to expand the online algorithms material. In particular the 'generic programming' technique illustrated by Alexander Stepanov in these lectures (Four Algorithmic Journeys) [1] and book [2] caught my attention. He takes a simple number theoretic algorithm, considers what properties are required for it to work, then generalizes it and applies it in other useful and surprising cases.

For example, Stepanov starts with the problem of multiplying two integers n * m using the Ancient Egyptian Multiplication algorithm from the Rhind Papyrus (which runs in log n if i remember correctly), then observes the only property needed for the algorithm is associativity, so that it can run on any semi-group: mult(n,s) is n repetitions of the semi-group element s, using the semi-group operation. Useful and surprising applications are (1) matrix exponentiation to solve systems of linear recurrences in log n steps (no stupid Fibonacci implementation here!), and (2) encode a graph in your matrix, with elements in a tropical semi-ring, then matrix exponentiation solves shortest path. Not too bad for a 4,000 year old multiplication algorithm.

A second example is the euclidean algorithm, which he extends first to polynomials following Stevin, then to Gaussian integers, then to euclidean domains. A surprising application was to permutation algorithms managing memory.

Anyhow, I think it would be really cool if you showed these kind of applications of number-theoretic algorithms as well as the cryptography stuff. Unfortunately basically all of the modern algorithms literature seems to avoid even the tiniest hint of abstraction; it makes the subject so much harder to hold in your head! So providing a new set of examples that is more accessible than Stepanov would be doing the world a great service, i think.

[1] https://www.youtube.com/user/A9Videos/playlists

[2] https://www.amazon.com/Elements-Programming-Alexander-Stepan...

[martyweissman]

I would like to expand the programming tutorials, though I doubt I'll go as abstract as Stepanov. I do provide some discussion of algorithms that generalize, e.g. the Euclidean algorithm and Pingala's algorithm for exponentiation. But I don't present these in such a generic form.

I've got a grant application out right now... if it goes through, I'll have some funding to support expansion of programming tutorials. I'd like to include more depth in both programming and number theory. On the programming side, I'd include classes, recursion, memoization, visualization. On the number theory side, I'd include Gaussian/Eisenstein/polynomials, Pollard rho and maybe SQUFOF for factorization.