Euclidean Algorithm in Mathematica

[Nena]

Alrightie folks, here is a code for the Euclidean Algorithm taken from
http://mathworld.wolfram.com/EuclideanAlgorithm.html

Remainder[a_, b_] := a - Quotient[a, b] b
Remainder[a_, 0] := 0
EuclideanAlgorithmGCD[a_, b_] :=
FixedPointList[{Last[#], Remainder @@ #} &, {a, b}][[-3, 1]]

Provided a and b are known. I want to get my hands on the
first two remainders (call them alpha and beta) that are less
than sqrt[a].
Meaning: How can I manage to take hold of alpha and beta
so I can do further manipulation with alpha and beta?

Many thanks!

Nena

[Jean-Marc Gulliet]

Basically, the function EuclideanAlgorithmGCD generates a list of pairs
where the second element of each pair is the remainder of the division.
The GCD is located in the third pair from the end of the generated
list (this is the meaning of -3) and it is the first element of the pair.

In[1]:=
Remainder[a_, b_] := a - Quotient[a, b]*b

Remainder[a_, 0] := 0
EuclideanAlgorithmGCD[a_, b_] :=

FixedPointList[{Last[#1], Remainder @@ #1} & , {a, b}][[-3, 1]]

In[4]:=
EuclideanAlgorithmGCD[12, 7]

Out[4]=
1

The following function will help to see what's going on

In[5]:=
Clear[f];
f[a_, b_] :=
FixedPointList[{Last[#1], Remainder @@ #1} & , {a, b}]

In[7]:=
f[12, 7]

Out[7]=
{{12, 7}, {7, 5}, {5, 2}, {2, 1}, {1, 0}, {0, 0}, {0, 0}}

So what you are looking for is the second column (where the remainders
are stored) of the second and third elements of the list (the first
element is just the pair of initial values {a, b}).

In[8]:=
myRemainders[a_, b_] :=
FixedPointList[{Last[#1], Remainder @@ #1} & , {a, b}][[{2, 3}, 2]]

In[9]:=
myRemainders[12, 7]

Out[9]=
{5, 2}

Regards,
Jean-Marc

[Nena]

Good morning,

Thank you very much!

> So what you are looking for is the second column (where the remainders
> are stored) of the second and third elements of the list (the first
> element is just the pair of initial values {a, b}).

Actually, I'm looking for the first two remainders which appear in the
Euclidean Algorithm *and* are less than the square-root of the
variable a.

So far I obtain with your function "myRemainders[a_, b_]" only the
first two remainders. But these remainders do not satisfying the
condition
of being the first two ones which are less than the square-root of
the variable a.

Much appreciated,
Nena

[Jeremy Watts]

"Nena" <Nivea.Sc...@web.de> wrote in message
news:1162977146....@m73g2000cwd.googlegroups.com...

cant mathematica be used to program your own algorithms? why not code up
your own version of the euclidean algorithm and get it to display all the
remainders rather than using built in functions
>

[Jean-Marc Gulliet]

Nena wrote:
> Good morning,
>
> Thank you very much!
>
>> So what you are looking for is the second column (where the remainders
>> are stored) of the second and third elements of the list (the first
>> element is just the pair of initial values {a, b}).
>
> Actually, I'm looking for the first two remainders which appear in the
> Euclidean Algorithm *and* are less than the square-root of the
> variable a.
>
> So far I obtain with your function "myRemainders[a_, b_]" only the
> first two remainders. But these remainders do not satisfying the
> condition
> of being the first two ones which are less than the square-root of
> the variable a.
>
> Much appreciated,
> Nena

Oops! My mistake, I have completely forgotten that part of the
requirement. One possible solution to get the first two remainders that
are less than the root of a is to use the Mathematica built in function
*Select* with the appropriate test as second argument and the third
argument set to two to get only the first two results that fulfill the
required condition (*Select* lists all matching values, by default).

In[1]:=
Remainder[a_, b_] := a - Quotient[a, b]*b
Remainder[a_, 0] := 0

myRemainders[a_, b_] :=
Module[{lst},
lst = FixedPointList[{Last[#1], Remainder @@ #1} & , {a, b}];
Select[lst, #1[[2]] < Sqrt[a] & , 2][[All,2]]
]

In[4]:=
myRemainders[12, 7]

Out[4]=
{2,1}

Regards,
Jean-Marc

[Nena]

Excellent! Thanks!

Just one little alternation.
Let alpha and beta be the first two remainders with
the condition that they are both less than the square root
of a. And also alpha > beta.

How can I list alpha and beta separately?
So that I can treat alpha and beta as variables for further
manipulations. For example to calculate
g[alpha_, beta_] := alpha^2 + beta^2

Cheers,
Nena

[Nena]

Hi Jeremy,

mm, I just follow the rule not to invent the wheel twice.
It's probably taking longer (especially for me as Mathematica-beginner)
to write my own version of the Euclidean Algorithm than to use built in
functions.

[Jean-Marc Gulliet]

Nena wrote:
> Excellent! Thanks!
>
> Just one little alternation.
> Let alpha and beta be the first two remainders with
> the condition that they are both less than the square root
> of a. And also alpha > beta.
>
> How can I list alpha and beta separately?
> So that I can treat alpha and beta as variables for further
> manipulations. For example to calculate
> g[alpha_, beta_] := alpha^2 + beta^2

For example

In[1]:=
Remainder[a_, b_] := a - Quotient[a, b]*b
Remainder[a_, 0] := 0
myRemainders[a_, b_] := Module[{lst},

lst = FixedPointList[{Last[#1], Remainder @@ #1} &, {a, b}];

Select[lst, #1[[2]] < Sqrt[a] &, 2][[All, 2]]]

In[4]:=
{alpha, beta} = myRemainders[12, 7]

Out[4]=
{2,1}

In[5]:=
alpha

Out[5]=
2

In[6]:=
beta

Out[6]=
1

In[7]:=
alpha^2 + beta^2

Out[7]=
5

Regards,
Jean-Marc

[Richard J. Fateman]

You certainly seem to be distracted by the possibility of writing
obscure programs in Mathematica.
Consider

f[a_, b_, lim_] := If [a < lim, {a, Mod[a, b]}, f[b, Mod[a, b], lim]]

I think that for specific integers a>b>0, you can call f[a,b,Sqrt[a]].

[Nena]

Well, thanks!

I need a slighty different example.

I would like to call the first two remainders within
a new function without defining the variables
alpha and beta outside first.

So I don't want to have this line first

> {alpha, beta} = myRemainders[12, 7]

but something of the shape
g[a, b] = alpha + beta where
alpha is the first entry of the result of
myRemainders[a, b] and beta the second one.

Many thanks,
Nena

[Richard J. Fateman]

Nena wrote:
> Well, thanks!
>
> I need a slighty different example.
>
> I would like to call the first two remainders within
> a new function without defining the variables
> alpha and beta outside first.

You mean, instead of my previous solution

f[a_, b_, lim_] := If [a < lim, {a, Mod[a, b]}, f[b, Mod[a, b], lim]]

you need this:

f[a_, b_, lim_] := If [a < lim, g[a + Mod[a, b]], f[b, Mod[a, b], lim]]

FixedPointList and @@ #1 are, so far as I can tell, quite unnecessary.
I would say that it was like trying to swat a gnat with a sledgehammer,
but the analogy seems wrong. It is more like trying to write on a
PostIt (c) with an InkJet Printer.

>

[Nena]

Yeah, you're right.
Your solution is much more clear and easy to handle with!
I've made the alternations I needed.

Thanks a lot Prof. Fateman!