2226.sagews

# This is an exercise to get a sense of the time to do a GCD computation.
# we will use the "three by two" column method
# We set up a very long array to make sure 
# we can contain all the relevant data

A = matrix(3,500,range(1500));A

3 x 500 dense matrix over Integer Ring (type 'print A.str()' to see all of the entries)

# Set the array to zero
for i in range(3):
    for j in range(500):
                        A[i,j]=0

# This is the GCD to compute
# Note the numbers have 72 digits

A[0,0]=34825630485762805762856347562354630576310857461075601856784347639274927
A[1,0]=1
A[2,0]=0
A[0,1]=23492482373428573249587345325630576105610561351305110560257947597057393
A[1,1]=0
A[2,1]=1
print "We are trying to compute the GCD of ",A[0,0]," and ",A[0,1]

We are trying to compute the GCD of 34825630485762805762856347562354630576310857461075601856784347639274927 and 23492482373428573249587345325630576105610561351305110560257947597057393

# Here's the computation. See how many iterations it takes.

k=2
while(A[0,k-1]>0):
    for j in range(3):
        A[j,k]=A[j,k-2]-A[j,k-1]*floor(A[0,k-2]/A[0,k-1]);
    k+=1
print "The greatest common divisor is", A[0,k-2]
if(A[0,k-2]==1):
    if(A[2,k-2]<0):
        A[2,k-2]=A[2,k-2]+A[0,0]
    print "And the inverse mod ",A[0,0]," is ",A[2,k-2];
    print "And it took ",k-2," iterations to find the GCD."

The greatest common divisor is 1 And the inverse mod 34825630485762805762856347562354630576310857461075601856784347639274927 is 26189883072675859200900755161290466467033857448958219585905974727504645 And it took 142 iterations to find the GCD.

# A partial printout

for i in range(3):
    print "In the computation of the GCD, row no. ",i+1," is:  "
    print A[i,0], A[i,1], A[i,2], A[i,3],A[i,4]

In the computation of the GCD, row no. 1 is: 34825630485762805762856347562354630576310857461075601856784347639274927 23492482373428573249587345325630576105610561351305110560257947597057393 11333148112334232513269002236724054470700296109770491296526400042217534 826186148760108223049340852182467164209969131764127967205147512622325 592728178452825613627571158351981335970697396836827722859482378127309 In the computation of the GCD, row no. 2 is: 1 0 1 -2 27 In the computation of the GCD, row no. 3 is: 0 1 -1 3 -40