
Re: Simple algorithms
Posted:
Apr 27, 2012 3:10 PM


On Apr 27, 12:58 pm, Frederick Williams <freddywilli...@btinternet.com> wrote: > "roboti...@googlemail.com" wrote: > > > What simple mathematical algorithms can be used as straightforward > > examples for teaching computer programming. > > > [...] > > > So, what other algorithms and operations are interesting examples? > > Sedgewick's 'Algorithms in C++' (AddisonWesley, 1992) has a chapter > headed 'Mathematical algorithms'. Also, the chapters titled 'Geometric > algorithms', 'Graph algorithms' and 'Advanced topics' have obvious > mathematical content. The last section of the chapter on string > processing is about cryptology. > > There are many books with titles like Sedgewick's, which (I know nothing > about, but) surely have similar content. > > A pedagogically nice thing about Sedgewick's book is the pictures. He > does not make use of C++'s more obscure features so his code can be > translated into your favourite language. (Which is what, by the way?) > > Happy hunting. >  > When a true genius appears in the world, you may know him by > this sign, that the dunces are all in confederacy against him. > Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting
I like the theory of Linear Congruence. It's nice for programming because it's all about integers, no mucking about with floats.
For g = (Xa  Z)/Y (X,Y,Z are constants)
you want to find a solution for a&g such that both are integers.
It's solvable if and only if GCD(X,Y) divides Z.
If the GCD is 1, you can solve using the Modular Inverse of (X,Y):
a0 = invert(X,Y)*M % Y
And once you find the a0 solution, you can find more because if a0 is a solution, so is a0+Y (or a0 +nY, for that matter).
EXAMPLE: g = (8a  5)/9
GCD(8,9)=1. 1 divides 5. invert(8,9)=8.
8*5 = 40. 40%9 = 4
S0, a=4 will result in g being an integer. g=(8*45)/9 g0=(325)/9 g0=27/9 g0=3
Now, the next solution is a0+Y, a1=4+9=13
g1=8*(135)/9 g1=(1045)/9 g1=99/9 g1=11
Note: not only are the 'a' solutions found by adding Y, but the g's can be found by adding X. So, without even doing the arithmetic, I know that (a2,g2) is (22,19).
Oh, if GCD(X,Y) divides Z but is >1, the congruence can still be solved, but you have to use the Extended Euclidean Algorithm, which I can't do off the top of head, in my particular application, X is always apower of 2 and Y always a power of 3, so GCD(X,Y) is always 1.

