Yioop - PHP Search Engine

Mar 20 In-Class Exercise Thread.

Post you solutions to the Mar 20 In-Class Exercise to this thread.

Best,

Chris

Post you solutions to the Mar 20 In-Class Exercise to this thread. Best, Chris

-- Mar 20 In-Class Exercise Thread

Show step-by-step what Extended-Euclid(210, 858) would compute.

``

Solution: `(6, -49, 12) : 6 = (-49)*210 + 12*858`

Extended-Euclid(210, 858) --> return `(6, -49, -12 - \lfloor\frac{210}{858}\rfloor*-49) = (6, -49, 12)`

Extended-Euclid(858, 210) --> return (6, 12, -1 - `\lfloor\frac{858}{210}\rfloor`*12) = (6, 12, -49)

Extended-Euclid(210, 18) --> return (6, -1, 1 - `\lfloor\frac{210}{18}\rfloor`*-1) = (6, -1, 12)

Extended-Euclid(18, 12) --> return (6, 1, 0 - `\lfloor\frac{18}{12}\rfloor`*1) = (6, 1, -1)

Extended-Euclid(12, 6) --> return (6, 0, 1 - `\lfloor\frac{12}{6}\rfloor`*0) = (6, 0, 1)

Extended-Euclid(6, 0) --> return (6, 1, 0)

(Edited: 2019-03-20)

'''Show step-by-step what Extended-Euclid(210, 858) would compute.''' @BT@@BT@ '''Solution:''' @BT@(6, -49, 12) : 6 = (-49)*210 + 12*858@BT@ Extended-Euclid(210, 858) --> return @BT@(6, -49, -12 - \lfloor\frac{210}{858}\rfloor*-49) = (6, -49, 12)@BT@ Extended-Euclid(858, 210) --> return (6, 12, -1 - @BT@\lfloor\frac{858}{210}\rfloor@BT@*12) = (6, 12, -49) Extended-Euclid(210, 18) --> return (6, -1, 1 - @BT@\lfloor\frac{210}{18}\rfloor@BT@*-1) = (6, -1, 12) Extended-Euclid(18, 12) --> return (6, 1, 0 - @BT@\lfloor\frac{18}{12}\rfloor@BT@*1) = (6, 1, -1) Extended-Euclid(12, 6) --> return (6, 0, 1 - @BT@\lfloor\frac{12}{6}\rfloor@BT@*0) = (6, 0, 1) Extended-Euclid(6, 0) --> return (6, 1, 0)

-- Mar 20 In-Class Exercise Thread

Ext-Euclid(210,858)

210x+858y = d = gcd(210,858)

858x' + 210y'= gcd(858, 210) = 6

143x' + 35y' = 1

gcd(143, 35) = 0

(Edited: 2019-03-20)

Ext-Euclid(210,858) 210x+858y = d = gcd(210,858) 858x' + 210y'= gcd(858, 210) = 6 143x' + 35y' = 1 gcd(143, 35) = 0

-- Mar 20 In-Class Exercise Thread

Recursive call (from bottom to up):

1. Extended-Euclid(6, 0) (6,1,0)

2. Extended-Euclid(12,6) (6,0,1)

3. Extended-Euclid(18,12) (6,1,-1)

4. Extended-Euclid(210,18) (6,-1,12)

5. Extended-Euclid(858,210) (6,12,-49)

6. Extended-Euclid(210,858) (6,-49,12)

Result: (6,-49,12)

(Edited: 2019-03-20)

Recursive call (from bottom to up): 1. Extended-Euclid(6, 0) (6,1,0) 2. Extended-Euclid(12,6) (6,0,1) 3. Extended-Euclid(18,12) (6,1,-1) 4. Extended-Euclid(210,18) (6,-1,12) 5. Extended-Euclid(858,210) (6,12,-49) 6. Extended-Euclid(210,858) (6,-49,12) Result: (6,-49,12)

-- Mar 20 In-Class Exercise Thread

((resource:extended-euclid.PNG|Resource Description for extended-euclid.PNG))

-- Mar 20 In-Class Exercise Thread

 
 
Extended-Euclid(210, 858)
(d', x', y') = Extended-Euclid(858, 210 % 858 = 210) = (6, 12, -49)
(d, x, y) = (6, -49, 12 - floor(210/858)*-49) = (6, -49, 12)
return (6, -49, 12) 
 
Extended-Euclid(858, 210)
(d', x', y') = Extended-Euclid(210, 858 % 210 = 18) = (6, -1, 12)
(d, x, y) = (6, 12, -1 - floor(858/210)*12) = (6, 12, -49)
return (6, 12, -49) 
 
Extended-Euclid(210, 18)
(d', x', y') = Extended-Euclid(18, 210 % 18 = 12) = (6, 1, -1)
(d, x, y) = (6, -1, 1 - floor(210/18)*-1) = (6, -1, 12)
return (6, -1, 12) 
 
Extended-Euclid(18, 12)
(d', x', y') = Extended-Euclid(12, 18 % 12 = 6) = (6, 0, 1)
(d, x, y) = (6, 1, 0 - floor(18/12)*1) = (6, 1, -1)
return (6, 1, -1) 
 
Extended-Euclid(12, 6)
(d', x', y') = Extended-Euclid(6, 12 % 6 = 0) = (6, 1, 0)
(d, x, y) = (6, 0, 1 - floor(12/6)*0) = (6, 0, 1)
return (6, 0, 1) 
 
Extended-Euclid(6, 0)
return (6, 1, 0)

<pre> Extended-Euclid(210, 858) (d', x', y') = Extended-Euclid(858, 210 % 858 = 210) = (6, 12, -49) (d, x, y) = (6, -49, 12 - floor(210/858)*-49) = (6, -49, 12) return (6, -49, 12) Extended-Euclid(858, 210) (d', x', y') = Extended-Euclid(210, 858 % 210 = 18) = (6, -1, 12) (d, x, y) = (6, 12, -1 - floor(858/210)*12) = (6, 12, -49) return (6, 12, -49) Extended-Euclid(210, 18) (d', x', y') = Extended-Euclid(18, 210 % 18 = 12) = (6, 1, -1) (d, x, y) = (6, -1, 1 - floor(210/18)*-1) = (6, -1, 12) return (6, -1, 12) Extended-Euclid(18, 12) (d', x', y') = Extended-Euclid(12, 18 % 12 = 6) = (6, 0, 1) (d, x, y) = (6, 1, 0 - floor(18/12)*1) = (6, 1, -1) return (6, 1, -1) Extended-Euclid(12, 6) (d', x', y') = Extended-Euclid(6, 12 % 6 = 0) = (6, 1, 0) (d, x, y) = (6, 0, 1 - floor(12/6)*0) = (6, 0, 1) return (6, 0, 1) Extended-Euclid(6, 0) return (6, 1, 0) </pre>

-- Mar 20 In-Class Exercise Thread

Extended_Euclid(858, 210) 858 = 210 * 4 + 18

    Extended_Euclid(210, 18) 210 = 18 * 11 + 12
        Extended_Euclid(18, 12) 18 = 1 * 12 + 6
            Extended_Euclid(12, 6) 12 = 2 * 6 + 0
                Extended_Euclid(6, 0)
                returns(6, 1, 0)
            (d', x', y') = (6, 1, 0)
            (d, x, y) = (d', y', x' - floor(12/6) * y') = (6, 0, 1)
            returns (6, 0, 1)
        (d', x', y') = (6, 0, 1)
        (d, x, y) = (d', y', x' - floor(18, 12) * y') = (6, 1, -1)
        returns (6, 1, -1)
    (d', x', y') = (6, 1, -1)
    (d, x, y) = (d', y', x' - floor(210/18) * y') = (6, -1, 1 - 11 * (-1)) = (6, -1, 12)
    returns (6, -1, 12)

(d', x', y') = (6, -1, 12) (d, x, y) = (d', y', x' - floor(858/210) * y') = (6, 12, -1 - 4 * 12) = (6, 12, -49) returns(6, 12, -49)

Extended_Euclid(858, 210) 858 = 210 * 4 + 18 Extended_Euclid(210, 18) 210 = 18 * 11 + 12 Extended_Euclid(18, 12) 18 = 1 * 12 + 6 Extended_Euclid(12, 6) 12 = 2 * 6 + 0 Extended_Euclid(6, 0) returns(6, 1, 0) (d', x', y') = (6, 1, 0) (d, x, y) = (d', y', x' - floor(12/6) * y') = (6, 0, 1) returns (6, 0, 1) (d', x', y') = (6, 0, 1) (d, x, y) = (d', y', x' - floor(18, 12) * y') = (6, 1, -1) returns (6, 1, -1) (d', x', y') = (6, 1, -1) (d, x, y) = (d', y', x' - floor(210/18) * y') = (6, -1, 1 - 11 * (-1)) = (6, -1, 12) returns (6, -1, 12) (d', x', y') = (6, -1, 12) (d, x, y) = (d', y', x' - floor(858/210) * y') = (6, 12, -1 - 4 * 12) = (6, 12, -49) returns(6, 12, -49)

-- Mar 20 In-Class Exercise Thread

 Extended_Euclid(210, 858) -> (6, -49, 12 - floor(210 / 858) * (-49)) -> return (6, -49, 12)

 Extended_Euclid(858, 210) -> (6, 12, 1 - floor(858 / 210) * 12) -> return (6, 12, -49)

 Extended_Euclid(210, 18) -> (6, -1, 1 - floor(210 / 18) * (-1)) -> return (6, -1, 12)

 Extended_Euclid(18, 12) -> (6, 1, 0 - floor(18 / 12) * 1) -> return (6, 1, -1)

 Extended_Euclid(12, 6) -> (6, 0, 1 - floor(12 / 6) * 0) -> return (6, 0, 1)

 Extended_Euclid(6, 0) -> return (6, 1, 0)

 Final solution: (6, -49, 12)

(Edited: 2019-03-25)

Extended_Euclid(210, 858) -> (6, -49, 12 - floor(210 / 858) * (-49)) -> return (6, -49, 12) Extended_Euclid(858, 210) -> (6, 12, 1 - floor(858 / 210) * 12) -> return (6, 12, -49) Extended_Euclid(210, 18) -> (6, -1, 1 - floor(210 / 18) * (-1)) -> return (6, -1, 12) Extended_Euclid(18, 12) -> (6, 1, 0 - floor(18 / 12) * 1) -> return (6, 1, -1) Extended_Euclid(12, 6) -> (6, 0, 1 - floor(12 / 6) * 0) -> return (6, 0, 1) Extended_Euclid(6, 0) -> return (6, 1, 0) Final solution: (6, -49, 12)

-- Mar 20 In-Class Exercise Thread

((resource:15535017412421594746411.jpg|Resource Description for 15535017412421594746411.jpg))

-- Mar 20 In-Class Exercise Thread

EE(210,858)->(6,-49,12-floor(210/858)*(-49))=(6,-49,12) EE(858,210)->(6,12,-1-floor(858/210)*12)=(6,12,-49) EE(210,18)->(6,-1,1-floor(210/18)*-1)=(6,-1,12) EE(18,12)->(6,1,0-floor(18/12)*1)=(6,1,-1) EE(12,6)->(6,0,1-floor(12/6)*0)=(6,0,1) EE(6,0)->(6,1,0)