exercise from "art of computer programming"

[Mauro Bertani]

The exercise that trouble me is:

Give the "effective" formal algorithm for computing the greatest
common divisor of positive integer m and n. Let the input be
represente by the string (a^m)(b^n), that is, m a's follow n b's.
Take from "art of computer programming"
Donald E. Knuth

Solution:
Let us formally define a computational method to be a quadruple
(Q,N,U,f), in which Q is a set containing the subset N and U;
and N is the set of input and U is the set of output.
Furthermore f should leave U fixed; that is f(q) should
equal q for all element q of U.

Let A a set equal {a,b} and let A* the set with all
possible combination of element of A with the structure
(a^m)(b^n) with m,n >= 0.
The set Q is made by the truple ($,j,i) with $ belong to A*
and 0 =< i,j <m,n , the singletons $ and the singleton j.
The set N = $.
The set U = j.

The function that define the algorithms is:

f(( $, j, i)) = f(( (a^j)(b^i), min(i,j), |j-i| ))
if i != 0
f(( $, j, i)) = f(( (a^j), j, j))
if i == 0
f(( (a^j), j, j)) = j

Is that corret? Or ia all wrong? This is my first formally definition
of an algorithm so if you have some time to spend
help me

[Ben Bacarisse]

Mauro Bertani <bertan...@gmail.com> writes:

> The exercise that trouble me is:
>
> Give the "effective" formal algorithm for computing the greatest
> common divisor of positive integer m and n. Let the input be
> represente by the string (a^m)(b^n), that is, m a's follow n b's.
> Take from "art of computer programming"
> Donald E. Knuth

For reference (it took me a while to find) Ex 8, page 9 book 1.

> Solution:
> Let us formally define a computational method to be a quadruple
> (Q,N,U,f), in which Q is a set containing the subset N and U;
> and N is the set of input and U is the set of output.
> Furthermore f should leave U fixed; that is f(q) should
> equal q for all element q of U.

This is in the "set-up" -- you don't need to write it out as part of the
solution (though it will help reader here who don't have TAOCP). You've
renamed things to avoid Greek letters (that's good) but N is used by
Knuth's presentation so I'll have to be careful to avoid confusion.

> Let A a set equal {a,b} and let A* the set with all
> possible combination of element of A with the structure
> (a^m)(b^n) with m,n >= 0.
> The set Q is made by the truple ($,j,i) with $ belong to A*
> and 0 =< i,j <m,n , the singletons $ and the singleton j.
> The set N = $.
> The set U = j.

But here you stray from what Knuth uses to define an "effective"
algorithm. His presentation defines the set Q to be pairs of the form
($, j) for 0 <= j <= M for some integer M. The set of inputs, N is just
those pairs ($, 0), and the set of outputs, U, are the pairs ($, M).

This does two things. First, it simplifies the computation function f.
There is no need now to define f on singletons:

f(($)) = ($, 0)

just to "get the computation going" and no need to define "output"
cases:

f(($, j)) = ($) if j = M.

Secondly, it ensures that the computation function is, in some sense,
finitely specified. This is done by further restricting how the cases
in the definition of f can be written.

Two sets of M strings must be specified. I'll call them match strings,
mj, and replacement strings, rj (Knuth uses theta_j and phi_j). f then
consists of a set of clauses like this:

f(($, N)) = ($, N)
f(($, j)) = ($, aj) if mj does not occur in $
f(($, j)) = (p rj s, bj) if mj does occur in $

Here p is the shortest string for which p mj s = $. The numbers aj and
bj are all in [0, M].

> The function that define the algorithms is:
>
> f(( $, j, i)) = f(( (a^j)(b^i), min(i,j), |j-i| ))
> if i != 0
> f(( $, j, i)) = f(( (a^j), j, j))
> if i == 0
> f(( (a^j), j, j)) = j
>
> Is that corret? Or ia all wrong?

The exercise asks for the strings mj and rj along with the numbers aj
and bj for all 0 <= j <= M. Knowing all of these is all you need to
know the function f. There's no need to write down all of f's cases.

> This is my first formally definition
> of an algorithm so if you have some time to spend
> help me

I haven't helped with the algorithm, but I hope I've clarified how it is
to be specified.

The computation has a state determined by a pair ($, j), and it proceeds
by transforming that into a new pair by optionally replacing a string in
$ with some other string and maybe a new j. If you know Turing
machines, this is similar with the numbers, j, representing the finite
states, and the strings $ representing the tape. The transformations of
the string (tape) that f can do are more general the in a Turing machine
which makes writing an algorithm like this somewhat simpler.

--
Ben.

[Bert_emme]

On Jun 5, 12:45 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

> Mauro Bertani <bertanima...@gmail.com> writes:
> > The exercise that trouble me is:
>
> > Give the "effective" formal algorithm for computing the greatest
> > common divisor of positive integer m and n. Let the input be
> > represente by the string (a^m)(b^n), that is, m a's follow n b's.
> >                       Take from "art of computer programming"
> >                  Donald E. Knuth
>
> For reference (it took me a while to find) Ex 8, page 9 book 1.

I'm so much careless in my citation, thanks to fixed my care-free life

> But here you stray from what Knuth uses to define an "effective"
> algorithm.  His presentation defines the set Q to be pairs of the form
> ($, j) for 0 <= j <= M for some integer M.  The set of inputs, N is just
> those pairs ($, 0), and the set of outputs, U, are the pairs ($, M).
>
> This does two things.  First, it simplifies the computation function f.
> There is no need now to define f on singletons:
>
>   f(($)) = ($, 0)
>
> just to "get the computation going" and no need to define "output"
> cases:
>
>   f(($, j)) = ($) if j = M.

this is a point that I haven't understood, now is ok

>
> Secondly, it ensures that the computation function is, in some sense,
> finitely specified.  This is done by further restricting how the cases
> in the definition of f can be written.
>

On this point I desire to spend some time to clarify me (?finitely
specified?)

"An alert reader will have notice a gaping hole in our last proof
of Algorithm E, however. We never showed that the algorithm
terminates;
all we have prove is that if terminates, it gives the right answer"
art of computer programming book 1
pag 16

> Two sets of M strings must be specified.  I'll call them match strings,
> mj, and replacement strings, rj (Knuth uses theta_j and phi_j).  f then
> consists of a set of clauses like this:
>
>   f(($, N)) = ($, N)
>   f(($, j)) = ($, aj)       if mj does not occur in $
>   f(($, j)) = (p rj s, bj)  if mj does occur in $
>
> Here p is the shortest string for which p mj s = $.  The numbers aj and
> bj are all in [0, M].

I will spend the next week-end on this

> > This is my first formally definition
> > of an algorithm so if you have  some time to spend
> > help me
>
> I haven't helped with the algorithm, but I hope I've clarified how it is
> to be specified.

You teach me much more than an algorithm and I thank you.

> The computation has a state determined by a pair ($, j), and it proceeds
> by transforming that into a new pair by optionally replacing a string in
> $ with some other string and maybe a new j.  If you know Turing
> machines, this is similar with the numbers, j, representing the finite
> states, and the strings $ representing the tape.  The transformations of
> the string (tape) that f can do are more general the in a Turing machine
> which makes writing an algorithm like this somewhat simpler.
>
> --
> Ben.

I come back home now by work, I spend my week-end for studing...
but my mind is always on some problem to solve.
I hope to solve this, you help me more than you think... you have gave
me
a new problem that is solvable

[Ben Bacarisse]

For an algorithm to be realistic it's specification must be finite. If
there were no upper bound, M, the function would not have a bounded
number of clauses in it's definition. It might be a perfectly
well-defined function but it would not be possible to imagine it being
carried out by a machine (or even a person). To perform even a single
step, an infinity of strings would have to be examined (the mj described
below) to see if they occur in the argument string.

All the usual models of computation -- Turing machines, lambda calculus,
recursive functions and so on -- require that a computation be specified
with a finite amount of information.

> "An alert reader will have notice a gaping hole in our last proof
> of Algorithm E, however. We never showed that the algorithm
> terminates;
> all we have prove is that if terminates, it gives the right answer"
> art of computer programming book 1
> pag 16
>
>> Two sets of M strings must be specified.  I'll call them match strings,
>> mj, and replacement strings, rj (Knuth uses theta_j and phi_j).  f then
>> consists of a set of clauses like this:
>>
>>   f(($, N)) = ($, N)
>>   f(($, j)) = ($, aj)       if mj does not occur in $
>>   f(($, j)) = (p rj s, bj)  if mj does occur in $
>>
>> Here p is the shortest string for which p mj s = $.  The numbers aj and
>> bj are all in [0, M].
>
> I will spend the next week-end on this

Good luck. It's a hard book, but very rewarding if you find that the
style suits you.

<snip>
--
Ben.

[Bert_emme]

I'm wrote:

> Give the "effective" formal algorithm for computing the greatest
> common divisor of positive integer m and n. Let the input be
> represente by the string (a^m)(b^n), that is, m a's follow n b's.
> Take from "art of computer programming"
> Donald E. Knuth

To avoid ambiguity of terminology I rename the string (a^m)(b^n) as
(q^m)(z^n).

My solution is:

Let A a set of finite letter {q,z} and A* the set of possible
combination
of element of set A with the structure (q^m)(z^n), with m,n >0.
Now let N be a nonnegative integer and let Q be the set of all ($,,j)
where $ is in A* and j is an integer 0<=j<=N.
Let IN be the subset of Q with j = 0 and OUT be the subset with j = N.
If mj and $ are string in A*, we say that mj occur in $ if $ has the
form
(p mj s) for string p,s where p is the shortest string for which
(p mj s) = $.
Now let rj the string that replace mj when it occurs in $.
Let f a function that compute the gcd as:

f(($,N)) = ($,N)
f(($,j)) = ($,aj) se mj doesn't occur in $
f(($,j)) = (p rj s, bj) se mj occur in $ where:
{ n = |m-n| e bj = min(m,n)
{ { (q^n)(z^bj) if n>=bj
{{ and rj = {{
{ { (q^bj)(z^n) otherwise
{

I think that this is the solution of the exercise.
If someone want to comment it I appreciate him.
with thanks of Ben that sure correct my error... I hope

[Bert_emme]

I'm wrote:

> Give the "effective" formal algorithm for computing the greatest
> common divisor of positive integer m and n. Let the input be
> represente by the string (a^m)(b^n), that is, m a's follow n b's.
> Take from "art of computer programming"
> Donald E. Knuth

To avoid ambiguity of terminology I rename the string (a^m)(b^n) as
(q^m)(z^n).

My solution is:

Let A a set of finite letter {q,z} and A* the set of possible
combination

[Ben Bacarisse]

Bert_emme <bertan...@gmail.com> writes:

> I'm wrote:
>
>> Give the "effective" formal algorithm for computing the greatest
>> common divisor of positive integer m and n. Let the input be
>> represente by the string (a^m)(b^n), that is, m a's follow n b's.
>> Take from "art of computer programming"
>> Donald E. Knuth
>
> To avoid ambiguity of terminology I rename the string (a^m)(b^n) as
> (q^m)(z^n).
>
> My solution is:
>
> Let A a set of finite letter {q,z} and A* the set of possible
> combination
> of element of set A with the structure (q^m)(z^n), with m,n >0.

Did Knuth make this restriction? I'd have thought that m,n >= 0 was
more natural.

> Now let N be a nonnegative integer and let Q be the set of all ($,,j)
> where $ is in A* and j is an integer 0<=j<=N.
> Let IN be the subset of Q with j = 0 and OUT be the subset with j = N.
> If mj and $ are string in A*, we say that mj occur in $ if $ has the
> form
> (p mj s) for string p,s where p is the shortest string for which
> (p mj s) = $.
> Now let rj the string that replace mj when it occurs in $.
> Let f a function that compute the gcd as:
>
> f(($,N)) = ($,N)
> f(($,j)) = ($,aj) se mj doesn't occur in $
> f(($,j)) = (p rj s, bj) se mj occur in $ where:
> { n = |m-n| e bj = min(m,n)
> { { (q^n)(z^bj) if n>=bj
> {{ and rj = {{
> { { (q^bj)(z^n) otherwise
> {
>
> I think that this is the solution of the exercise.

No, this is not yet a solution.

The main problem is that it is not finite. The N that bounds the size
of all the sets must be specified and is independent of the input. In
your example, the range of j depends on the input -- bj is min(m, n) and
there is no upper limit on how large that can be.

Once you have a solution you can say what N is. Lets say your solution
requires N to be 8 (my solution has N=8). You can then simply list the
8 numbers a0, a1, ... a9, the 8 numbers b0, b1, ... b8 and similarly for
the 8 match strings, mj and the 8 replacement strings rj.

> If someone want to comment it I appreciate him.
> with thanks of Ben that sure correct my error... I hope

Here's an example. Consider multiplication: give an effective
algorithm to compute the string (c^(nm)) from an input of the form
(a^n)(n^n). I.e. we want to turn "aaabb" into "cccccc" and "aabb" into
"cccc". The inputs "bbb" and "aa" both turn into "" since x*0 = 0.

In my solution (probably not optimal) N = 7. The "match" strings are:
"ab", "ab", "b", "x", "b", "a" and "b", the "replacement" strings are
"b", "xc", "xc", "b", "c", "" and "". The numbers aj, for 0 <= j < N
are 5, 4, 3, 1, 7, 6 and 7. The bj are 1, 2, 2, 3, 4, 5 and 6.

It's very hard to understand the solution when it's written like this,
but it specifies a function, p, of this form:

p(($, 0)) = ($/ab/b/, 1) or ($, 5)
p(($, 1)) = ($/ab/xc/, 2) or ($, 4)
p(($, 2)) = ($/b/xc/, 2) or ($, 3)
p(($, 3)) = ($/x/b/, 3) or ($, 1)
p(($, 4)) = ($/b/c/, 4) or ($, 7)
p(($, 5)) = ($/a//, 5) or ($, 6)
p(($, 6)) = ($/b//, 6) or ($, 7)
p(($, 7)) = ($, 7)

where $/m/r/ is the result of replacing the first occurrence of m in $
with r. If m does not occur in $, p takes the second value shown.
Notice how everything is finite.

The computation of p(("aabb", 0)) proceeds as follows:

p(("aabb",0)) = ("abb",1)
p(("abb",1)) = ("xcb",2)
p(("xcb",2)) = ("xcxc",2)
p(("xcxc",2)) = ("xcxc",3)
p(("xcxc",3)) = ("bcxc",3)
p(("bcxc",3)) = ("bcbc",3)
p(("bcbc",3)) = ("bcbc",1)
p(("bcbc",1)) = ("bcbc",4)
p(("bcbc",4)) = ("ccbc",4)
p(("ccbc",4)) = ("cccc",4)
p(("cccc",4)) = ("cccc",7)

Does this help?

--
Ben.

[Bert_emme]

> Did Knuth make this restriction?  I'd have thought that m,n >= 0 was
> more natural.

ok is more natural, it's the obvious that it isn't thought

> No, this is not yet a solution.

Now I think that I understand, It wasn't clear the rule of N, aj and
bj.

> The main problem is that it is not finite.  The N that bounds the size
> of all the sets must be specified and is independent of the input.  In
> your example, the range of j depends on the input -- bj is min(m, n) and
> there is no upper limit on how large that can be.
>
> Once you have a solution you can say what N is.  Lets say your solution
> requires N to be 8 (my solution has N=8).  You can then simply list the
> 8 numbers a0, a1, ... a9, the 8 numbers b0, b1, ... b8 and similarly for
> the 8 match strings, mj and the 8 replacement strings rj.
>

N is 4 in my solution, so there is some error because Knuth say that N
is 5.
I'm sure that I jump some fundamental step

The solution:

f(($,0)) = ($/ab/c,1) or ($,3)
f(($,1)) = ($/b/a,2) or ($,2)
f(($,2)) = ($/c/b,3) and go ($,0)
f(($,3)) = ($,4)


> Does this help?

Ohh, I don't know how thank you... all post was usefull to understand
each steps.
if you only correct my final work I appreciate
thanks a lot
bye
Mauro

[Ben Bacarisse]

Bert_emme <bertan...@gmail.com> writes:

>> Did Knuth make this restriction?  I'd have thought that m,n >= 0 was
>> more natural.
>
> ok is more natural, it's the obvious that it isn't thought
>
>> No, this is not yet a solution.
>
> Now I think that I understand, It wasn't clear the rule of N, aj and
> bj.
>
>> The main problem is that it is not finite.  The N that bounds the size
>> of all the sets must be specified and is independent of the input.  In
>> your example, the range of j depends on the input -- bj is min(m, n) and
>> there is no upper limit on how large that can be.
>>
>> Once you have a solution you can say what N is.  Lets say your solution
>> requires N to be 8 (my solution has N=8).  You can then simply list the
>> 8 numbers a0, a1, ... a9, the 8 numbers b0, b1, ... b8 and similarly for
>> the 8 match strings, mj and the 8 replacement strings rj.
>>
>
> N is 4 in my solution, so there is some error because Knuth say that N
> is 5.

You could make N = 5 just by adding another clause:

f(($, 4)) = ($, 5)

In fact the sky's the limit! The fact that you already have this:

f(($, 3)) = ($, 4)

means that the N for your solution is not really 4 but 3. And you are
right; if Knuth says that 5 "states" are needed, you are very unlikely
to find a solution with N = 3.

> I'm sure that I jump some fundamental step
>
> The solution:
>
> f(($,0)) = ($/ab/c,1) or ($,3)
> f(($,1)) = ($/b/a,2) or ($,2)
> f(($,2)) = ($/c/b,3) and go ($,0)
> f(($,3)) = ($,4)
>
>> Does this help?
>
> Ohh, I don't know how thank you... all post was usefull to understand
> each steps.
> if you only correct my final work I appreciate
> thanks a lot

I am not sure what you mean. You presumably know that this is not a
solution so are you asking me to post my (far from optimal) solution?

--
Ben.

[Bert_emme]

On Jun 11, 4:12 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

> Bert_emme <bertanima...@gmail.com> writes:
> >> Did Knuth make this restriction?  I'd have thought that m,n >= 0 was
> >> more natural.
>
> > ok is more natural, it's the obvious that it isn't thought
>
> >> No, this is not yet a solution.
>
> > Now I think that I understand, It wasn't clear the rule of N, aj and
> > bj.
>
> >> The main problem is that it is not finite.  The N that bounds the size
> >> of all the sets must be specified and is independent of the input.  In
> >> your example, the range of j depends on the input -- bj is min(m, n) and
> >> there is no upper limit on how large that can be.
>
> >> Once you have a solution you can say what N is.  Lets say your solution
> >> requires N to be 8 (my solution has N=8).  You can then simply list the
> >> 8 numbers a0, a1, ... a9, the 8 numbers b0, b1, ... b8 and similarly for
> >> the 8 match strings, mj and the 8 replacement strings rj.
>
> > N is 4 in my solution, so there is some error because Knuth say that N
> > is 5.
>
> You could make N = 5 just by adding another clause:
>
>   f(($, 4)) = ($, 5)
>
> In fact the sky's the limit!  The fact that you already have this:
>
>   f(($, 3)) = ($, 4)
>
> means that the N for your solution is not really 4 but 3.  And you are
> right; if Knuth says that 5 "states" are needed, you are very unlikely
> to find a solution with N = 3.

where is the mistake? don't play with me, all young have great hope,
is the nature of age... it's not so wrong as it can be thought

> I am not sure what you mean.  You presumably know that this is not a
> solution so are you asking me to post my (far from optimal) solution?

Yes, see your possible solution will be the final step
of this two week.
Do you know that gcd was the first program run on first computer?
I have read the Hodges' book "Alan Turing. The Enigma" and the
writer says that the 21 June 1948 a program write by Kilburn
solve the gcd between two integer with brute force
(I'm not sure of the traslation).
And gcd was my first program write at the university
taking the algorithm by a discrete mathematic book.
It's so important this algorithms for me that your solution
will be an other piece of the puzzle in my little search
in computer science

bye

[Ben Bacarisse]

Bert_emme <bertan...@gmail.com> writes:

> On Jun 11, 4:12 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> Bert_emme <bertanima...@gmail.com> writes:

<snip>

>> > N is 4 in my solution, so there is some error because Knuth say that N
>> > is 5.
>>
>> You could make N = 5 just by adding another clause:
>>
>>   f(($, 4)) = ($, 5)
>>
>> In fact the sky's the limit!  The fact that you already have this:
>>
>>   f(($, 3)) = ($, 4)
>>
>> means that the N for your solution is not really 4 but 3.  And you are
>> right; if Knuth says that 5 "states" are needed, you are very unlikely
>> to find a solution with N = 3.
>
> where is the mistake? don't play with me, all young have great hope,
> is the nature of age... it's not so wrong as it can be thought

That's not a good question. I don't know where the mistake is, but it's
clear it doesn't work.

>> I am not sure what you mean.  You presumably know that this is not a
>> solution so are you asking me to post my (far from optimal) solution?
>
> Yes, see your possible solution will be the final step
> of this two week.

OK, here is my 7-state solution (I miss-counted when I said N was 8 in my
solution):

f 0 s = case replace s "ab" "ab" of {Just s' -> f 1 s'; Nothing -> f 6 s}
f 1 s = case replace s "ab" "" of {Just s' -> f 2 s'; Nothing -> f 3 s}
f 2 s = case replace s "" "m" of {Just s' -> f 1 s'}
f 3 s = case replace s "a" "b" of {Just s' -> f 3 s'; Nothing -> f 4 s}
f 4 s = case replace s "m" "a" of {Just s' -> f 4 s'; Nothing -> f 5 s}
f 5 s = case replace s "b" "b" of {Just s' -> f 1 s'; Nothing -> f 7 s}
f 6 s = case replace s "b" "a" of {Just s' -> f 6 s'; Nothing -> f 7 s}
f 7 s = s

test m n = all (== 'a') answer && length answer == gcd m n
where answer = f 0 (replicate m 'a' ++ replicate n 'b')

replace s m r = repl s m r []
where repl s [] r p = Just (p ++ r ++ s)
repl [] _ _ _ = Nothing
repl (s:ss) (m:ms) r p
| m == s = repl ss ms r p
| otherwise = repl ss (m:ms) r (p ++ [s])

It's a Haskell program, but I think it should be clear what the strings
and state numbers are. (It's just easier to include the file rather than
translate f into the form we've been using.)

> Do you know that gcd was the first program run on first computer?
> I have read the Hodges' book "Alan Turing. The Enigma" and the
> writer says that the 21 June 1948 a program write by Kilburn
> solve the gcd between two integer with brute force

I've read that "fact" but I am not sure it's true. Three programs are
listed in the letter that Williams and Kilburn published -- highest
factor, GCD and integer division. It seems likely that the highest
factor program was the first, but I'm not sure it matters much.

You can also get different answers depending on how you define the term.
Curiously, GCD was almost certainly the first published program if you
define "computer" to be someone who computes. It's in Euclid's
Elements.

If you exclude people, but include mechanical computers, it was Ada
Lovelace who has the honour for a program to compute Bernoulli numbers.

If you insist that computers be electronic, then analog computers must
be included and these were widely used long before digital computers.
Goodness knows what the first program was for one of these, but I'll bet
it was for a differential equation.

Some early digital computers did not store the program (either entirely
or in part) inside the machine's memory so these (like Colossus) are
often excluded.

If you take computer mean "electronic digital stored-program computer"
then I think Cambridge's EDSAC was the first. It's first program
printed a table of squares and primes. This machine takes some beating
in terms of firsts, because it had a primitive assembler and a loader
allowing symbolic programming, with subroutines, in 1949.

<snip>
--
Ben.