A few style questions - Smalltalk

Fernando,

> Do you think that returning an array is OK or should I use a specific
> class to represent the result explicitly?

It's obviously a matter of taste. In this case, I would probably just use an
array (but see below) since there isn't much real semantics (behaviour) for a
special object to have. At least, I can't think of anything plausible -- it's
just a triple of numbers with nothing much interesting for them to say or do.

Another technique is, instead of passing back three numbers from the method,
pass a block /into/ the method which takes three parameters. I.e.

Integer>>withExtendedCGD: anInteger do: a3Block
| gcd x y |
...calculations, then...
^ a2Block value: gcd value: x value: y.

Or you could even return the GCD, and use a two-parameter block for the
auxilary information.

That technique is used here and there in the image.


> Could this mehtod be generating too
> much garbage (a buch of arrays with the temporary results)?

I /very/ much doubt it. For one thing the GCD calculation is fairly expensive,
so the allocation/gc overhead isn't going to be large in comparison. For
another thing Dolphin's gc implementation, although OA say it is very simple,
is very fast and effective in practice (provided you don't use so much memory
at once that the OS needs to page virtual memory).

BTW. Your implementation uses the result of both a // b and a \\ b. You may
find it more efficient, especially for large numbers, to compute both at once
using Integer>>quoAndRem: (Which returns an Array ;-)

-- chris

Hello Fernando, i once implemented recursive algorithm answering Array
that i would reuse in backtracking.

I have also a little experiment written in VW that i provide as is.
You will find several variants.
If you improve, i would appreciate that you share, but of course you
have no obligation.

Nicolas



Fernando Rodríguez a écrit :
>
> I'm playing around with some discrete math algorithms and Dolphin and
> have a few questions. Here's a recursive implementation of the extended
> gcd algorithm (see
> http://en.wikipedia.org/wiki/Extende...an_algorithm):
>
> -------------------------------------------------------------------------------------------------------------
>
> Integer>>extendedRecursiveGcd: anInteger
>
> "The Euclidean Algorithm is extended to compute not only the
> gcd(a,b), but also the integer coefficients
> x and y such that:
> d = gcd(a,b) = ax + by
>
> x and y might be zero or negative.
>
> Assuming d = gcd(self, operand)
> d = self x + operand y
>
> The method returns an array (d x y)
> "
>
> |a b|
>
> a := self abs.
> b := anInteger abs.
>
> (b isZero) ifTrue: [^Array with: a with: 1 with: 0.]
> ifFalse:
> [|temp d tempX tempY x y|
> temp := b extendedRecursiveGcd: (a \\ b).
> d := temp first.
> tempX := temp second.
> tempY := temp third.
> x := tempY.
> y := tempX - (tempY * ( a // b)).
> ^Array with: d with: x with: y.
> ]
> ---------------------------------------------------------------------------------------------------------------
>
>
> Do you think that returning an array is OK or should I use a specific
> class to represent the result explicitly? Could this mehtod be
> generating too much garbage (a buch of arrays with the temporary results)?
>
> Thanks
>
>


'From VisualWorks® NonCommercial, 7.3.1 of April 20, 2005 on March 1, 2007 at 12:51:23 pm'!


Object subclass: #BezoutAlgorithm
instanceVariableNames: 'a b u v gcd x y '
classVariableNames: ''
poolDictionaries: ''
category: 'Magnitude-Numbers'!

BezoutAlgorithm class
instanceVariableNames: ''!

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!


!BezoutAlgorithm class methodsFor: 'instance creation'!

a: aInteger b: bInteger
^self new a: aInteger b: bInteger! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!


BezoutAlgorithm comment:
'Bezout Algorithm : find gcd of two integers a & b.
Also find u v x and y such that :
(a * u) + (b * v) = gcd
(x * u) + (y * v) = 1
x * gcd = a
y * gcd = b

Instance Variables:
a <Integer> description of a
b <Integer> description of b
gcd <Integer> description of gcd
u <Integer> description of u
v <Integer> description of v
x <Integer> description of x
y <Integer> description of y

'!

!BezoutAlgorithm methodsFor: 'instance creation'!

a: aInteger b: bInteger
| swap |
a := aInteger.
b := bInteger.
(swap := a abs < b abs) ifTrue: [self seta: b b: a].
b = 0
ifTrue: [
gcd := a.
x := 1.
y := 0.
u := 1.
v := 0]
ifFalse: [ self iterativeSolve2].
swap ifTrue: [self setx: y y: x u: v v: u].
a := aInteger.
b := bInteger.! !

!BezoutAlgorithm methodsFor: 'private'!

backPropagateQuotient: q
self
setx: y + (q * x)
y: x
u: v
v: u - (q * v)!

iterativeSolve
| q r qs |
qs := OrderedCollection new: 64.

[q := a // b.
r := a - (q * b).
r isZero] whileFalse:
[a := b.
b := r.
qs add: q].
self trivialSolutionQuotient: q.
qs size to: 1 by: -1 do: [:i |
self backPropagateQuotient: (qs at: i)].!

iterativeSolve2
| q r qs aa bb |
aa := a.
bb := b.
qs := OrderedCollection new: 64.

[q := a // b.
r := a - (q * b).
r isZero] whileFalse:
[a := b.
b := r.
qs add: q].
gcd := b. u := 0. v := 1.
qs size to: 1 by: -1 do: [:i |
self
setu: v
v: u - ((qs at: i) * v)].
x := aa quo: gcd.
y := bb quo: gcd!

iterativeSolve3
| q r qs |
qs := OrderedCollection new: 64.

[q := a // b.
r := a - (q * b).
r isZero] whileFalse:
[a := b.
b := r.
qs add: q].
self trivialSolutionQuotient: q.
qs reverseDo: [:qi | self backPropagateQuotient: qi].!

recursiveSolve
| q r |
q := a // b.
r := a - (q*b).
r isZero ifTrue: [^self trivialSolutionQuotient: q].
a := b.
b := r.
self recursiveSolve.
self backPropagateQuotient: q.!

recursiveSolve2
| q r |
q := a // b.
r := a - (q*b).
r isZero ifTrue: [^self trivialSolutionQuotient: q].
self seta: b b: r.
self recursiveSolve2.
self
setx: y + (q * x)
y: x
u: v
v: u - (q * v)!

seta: aa b: bb
a := aa.
b := bb!

setu: uu v: vv
u := uu.
v := vv!

setx: xx y: yy
x := xx.
y := yy!

setx: xx y: yy u: uu v: vv
x := xx.
y := yy.
u := uu.
v := vv!

solve
self iterativeSolve2!

solve2
| q r t |
q := a // b.
r := a - (q*b).
r isZero ifTrue: [
gcd := b.
x := q.
y := 1.
u := 0.
v := 1.
^self].

a := b.
b := r.
self solve2.

t := x. x := y. y := t.
t := u. u := v. v := t.

x := x + (q * y).
v := v - (q * u).!

trivialSolutionQuotient: q
gcd := b.
x := q.
y := 1.
u := 0.
v := 1! !

!BezoutAlgorithm methodsFor: 'accessing'!

a
^a!

b
^b!

gcd
^gcd!

u
^u!

v
^v!

x
^x!

y
^y! !

'From VisualWorks® NonCommercial, 7.3.1 of April 20, 2005 on March 1, 2007 at 12:51:35 pm'!


TestCase subclass: #BezoutAlgorithmTest
instanceVariableNames: ''
classVariableNames: ''
poolDictionaries: ''
category: 'Magnitude-Numbers'!

BezoutAlgorithmTest class
instanceVariableNames: ''!

BezoutAlgorithmTest comment:
'Test case for BezoutAlgorithm.
'!

!BezoutAlgorithmTest methodsFor: 'Running'!

test1
| nums |
nums := #(0 1 2 3 4 5 12 17 42 100 4654 8976543 132486765145786410 132486765145786411 12346874174312684321541214421341).
nums do: [:a |
nums do: [:b |
| bezout |
bezout := BezoutAlgorithm a: a b: b.
self should: [bezout gcd = (a gcd: b)].
self should: [bezout x * bezout gcd = a].
self should: [bezout y * bezout gcd = b].
self should: [a * bezout u + (b * bezout v) = bezout gcd].
self should: [bezout x * bezout u + (bezout y * bezout v) = 1]]].!

test2
| nums |
nums := #(0 1 2 3 4 5 12 17 42 100 4654 8976543 132486765145786410 132486765145786411 12346874174312684321541214421341).
nums do: [:a |
nums do: [:b |
| bezout |
bezout := BezoutAlgorithm a: a b: b negated.
self should: [bezout gcd abs = (a gcd: b)].
self should: [bezout x * bezout gcd = a].
self should: [bezout y * bezout gcd = b negated].
self should: [a * bezout u - (b * bezout v) = bezout gcd].
self should: [bezout x * bezout u + (bezout y * bezout v) = 1]]].!

test3
| nums |
nums := #(0 1 2 3 4 5 12 17 42 100 4654 8976543 132486765145786410 132486765145786411 12346874174312684321541214421341).
nums do: [:a |
nums do: [:b |
| bezout |
bezout := BezoutAlgorithm a: a negated b: b negated.
self should: [bezout gcd abs = (a gcd: b)].
self should: [bezout x * bezout gcd = a negated].
self should: [bezout y * bezout gcd = b negated].
self should: [a negated * bezout u - (b * bezout v) = bezout gcd].
self should: [bezout x * bezout u + (bezout y * bezout v) = 1]]].!

test4
| nums |
nums := #(0 1 2 3 4 5 12 17 42 100 4654 8976543 132486765145786410 132486765145786411 12346874174312684321541214421341).
nums do: [:a |
nums do: [:b |
| bezout |
bezout := BezoutAlgorithm a: a negated b: b.
self should: [bezout gcd abs = (a gcd: b)].
self should: [bezout x * bezout gcd = a negated].
self should: [bezout y * bezout gcd = b].
self should: [a negated * bezout u + (b * bezout v) = bezout gcd].
self should: [bezout x * bezout u + (bezout y * bezout v) = 1]]].! !

Hello nicolas,

> Hello Fernando, i once implemented recursive algorithm answering Array
> that i would reuse in backtracking.
>
> I have also a little experiment written in VW that i provide as is.
> You will find several variants.
> If you improve, i would appreciate that you share, but of course you
> have no obligation.

Sure, as soon as I have something more substantial I'll make it available.