Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
mensanator

Posts: 5,039
Registered: 12/6/04
Re: Simple algorithms
Posted: Apr 27, 2012 3:10 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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++' (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
> 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*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.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.