This page shows you an implementation of calculating the greatest common devisor of two positive integers in VPGL.
The greatest common devisor (GCD) of integer A and B is the number C which is the greatest one is both remainder of A / C and B / C is 0. For example, The GCD of 48 and 32 is 16. Devisor of them are 2, 4, 8, 16. Then the greatest one of them is 16. If they have no common devisors ( 7 and 4, for example), their GCD is 1.
The well-known method of finding GCD of two positive integers is Euclid’s algorithm, that is:
- Set two integers to X and Y for each.
- Set R to the remainder of X and Y.
- If R is not 0 then set X = Y, Y = R, go to step 2.
- If R is 0 then GCD is Y. (then stop)
Where if X < Y, then the remainder of X and Y (modulo Y of X) is X.
Try some example on this method:
(a) X = 54, Y=24
1a. X=54, Y=24
2a. R = 6
3a. X=24, Y=6
2b. R=0 (6*4=24(
4b. GCD=Y=6
(b) X=24, Y=54
1a. X=24, Y=54
2b. R=24 (In the case of X<Y)
3a, X=54, Y=24
2b. R=6
3b. X=24, Y=6
2c. R=0
4c. GCD=Y=6
(c) X=35, Y=22
1a. X=35, Y=22
2a. R=13
3a. X=22, Y=13
2b. R=9
3b. X=13, Y=9
2c. R=4
3c. X=9, Y=4
2d. R=1 (X = 2*Y+1)
3d. X=4, Y=1
2e. R=0, (X= 4*Y+0)
4e. GCD=Y=1.
Note that this method can find the GCD even if X<Y, see above example (b) which exchanges X and Y and steps same as (a).
An implementation of this method in VPGL is follows.
This definition takes 2 inputs, X from left (A4) and Y from top (D1).
The Step 2 of this method is A%B operation at tile C1 which takes X from left as input 0, and Y from right as input 1, then these remainder will emit to bottom(to C2)
The Step3 of this method is the area C2:E3, GT with option at D2 takes 1 input, emits *T* if (input 0) > (option), NIL otherwise. This comparison result is used at SWITCHs at C3 (for R) and E3 (for Y). If it is *T* (R > 0) then Recursive invocation of GCD at D4 with Y as input 0 (new X) and R as input 1 (new Y). Otherwise (R=0), Y is the result then passed to D7 (step 4). In this case, R(=0) should be discarded by being passed to END operation at B3. END takes1 or 2 or 3 or 4 inputs, fires on arriving any of them soon, simply discards it.
An other implementation of GCD using loop instead of recursive call is shown as follows. This example says “looping is not so easy for VPGL. Use recursive call”.
This has 3 overcrossing of data flow as C5, F5, and F6. They are required for replacing X <- Y, Y<-R at step 3. Y at E5 must be passed to A4 as new X, and R at C5 must be passed to D1 as new Y.
JOIN at G5 is a special consideration for keeping away from overtaking of data token.
JOIN takes 2 inputs, it executes on all inputs are arrived (waiting for arriving all inputs), emits input 0 to output 0. JOIN holds input 0 until arriving input 1.
VPGL executes picked one from all tiles which is able to execute, but pick it up random.
Therefore, it should be consider to synchronize each 2 loops(for R and Y). When “R loop” (C5 to E3) rounds, it will wait “Y loop” goes around. If “R loop” go around 2 times when “Y looping” 1 time, R data catches up previous R token then cause undefined result. (currently, previous token is discarded and will cause unexpected calculation)
This synchronization is not so easy and can implement at most 2 loops. This means over 3 variables looping is quite difficult. Thus recursive call is useful for VPGL.