Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Simple algorithms
Replies: 16   Last Post: Jun 14, 2012 12:35 AM

 Messages: [ Previous | Next ]
 mensanator Posts: 5,039 Registered: 12/6/04
Re: Simple algorithms
Posted: Apr 27, 2012 3:10 PM

On Apr 27, 12:58 pm, Frederick Williams
<freddywilli...@btinternet.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++' (Addison-Wesley, 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
>
> 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

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*4-5)/9
g0=(32-5)/9
g0=27/9
g0=3

Now, the next solution is a0+Y, a1=4+9=13

g1=8*(13-5)/9
g1=(104-5)/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.

Date Subject Author
4/27/12 Frederick Williams
4/27/12 mensanator
4/27/12 mensanator
4/28/12 Ken.Pledger@vuw.ac.nz
5/1/12 Frederick Williams
5/1/12 Ken.Pledger@vuw.ac.nz
5/1/12 Ken.Pledger@vuw.ac.nz
5/2/12 Frederick Williams
5/1/12 David Bernier
5/1/12 amzoti
5/11/12 JEMebius
5/3/12 Graham Cooper
5/3/12 Graham Cooper
6/13/12 Dann Corbit
6/13/12 Graham Cooper
6/14/12 KBH