Jsevillamol

15 Reputation

3 Badges

6 years, 23 days

MaplePrimes Activity


These are questions asked by Jsevillamol

I am implementing the Extended Euclides Algorithm in Maple for arbitrary domains.

This is my function so far:

EEA:=proc(ED,a,b)
    description
    "Extended Euclidean Algorithm"
    "INPUT: an Euclidean Domain ED and two elements from said domain"
    "OUTPUT: r,s,t such that r = gcd(a,b) = s*a + t*b ";
    local r_0, r_1, r_aux, s_0, s_1, s_aux, t_0, t_1, t_aux, q;
    # Domain checks
    # TODO: check that ED is an euclidean domain
    if not ED[Type](a) then error "1st argument must be of type ED" end if;
    if not ED[Type](b) then error "2nd argument must be of type ED" end if;
    
    # Initialization
    r_0 := a; r_1 := b; # gcd series
    s_0 := 1; s_1 := 0; # 1st cofactor series
    t_0 := 0; t_1 := 1; # 2nd cofactor series

    # Loop
    while r_1 <> 0 do;
        print("All is fine before the Quo");
        print(r_0); print(r_1);
        q := ED[Quo](r_0, r_1);
        print("All is fine after the Quo");
        
        r_aux := r_0 - q * r_1;
        r_0 := r_1; r_1 := r_aux;
        
        s_aux := s_0 - q * s_1;
        s_0 := s_1; s_1 := s_aux;

        t_aux := t_0 - q * t_1;
        t_0 := t_1; t_1 := t_aux;
    od;

    # Result
    return r_0, s_0, t_0;
    end proc:

Where ED is a Domain object passed as a parameter to the function.

When I call the function with certain arguments, it goes once through the loop and then in the second iteration crashes between the second and third print statement.

Concretely, upon making the call:

with(Domains): GI := Gaussian(Z); a := GI[Input](-87+47*I): b := GI[Input](-90+43*I): r, s, t := EEA(GI, a, b); evalb(a*s+b*t = r)

I get the following output:

              

        "All is fine before the Quo"
                              -87 + 47 _i
                              -90 + 43 _i
                      "All is fine after the Quo"
                      "All is fine before the Quo"
                              -90 + 43 _i
                                3 + 4 _i
    Error, (in E[Domains:-Rem]) cannot determine if this expression is true or false: 0 <= -90*`domains/Gaussian/badge0`(-87, 47)-43*`domains/Gaussian/badge0`(1, 0)*`domains/Gaussian/badge0`(-90, 43)

From this we should infer that calling `Gaussian(Z)[Quo]` on arguments `-90 + 43 _i` and `3 + 4 _i` should produce this error, right?

Well, think again, because when I try reproducing that from the notebook it decides to stop crashing. Calling:

    with(Domains): GI:=Gaussians(Z): a := GI[Input](-90+43*I); b := GI[Input](3+4*I); GI[Quo](a, b);

Produces the output:

                            a := -90 + 43 _i
                b := 3 + 4 _i
               -4 + 20 _i

What is going on? Why does it crash inside the function but not in the workbook?

Page 1 of 1