讲解：MACM 401、Maple worksheet、Java，Python、Java，c++SQL|MACM 401/MATH 801Assignment 1, Spring 2019.Michael MonaganThis assignment is to be handed in by 4pm Monday January 21st.Hand in to Dropoff box 1A outside AQ 4100.Late penalty: 20% for up to 48 hours late. Zero after that.For problems involving Maple calculations and Maple programming, please submit a printout of aMaple worksheet.Question 1 (15 marks): Karatsuba’s AlgorithmReference: Algorithm 4.2 in the Geddes text.(a) By hand, calculate 5432 × 3829 using Karatsuba’s algorithm. You will need to do threemultiplications involving two digit integers. Do the first one, 54 × 38, using Karatsuba’salgorithm (recursively). Do the other two using any method.(b) Let T(n) be the time it takes to multiply two n digit integers using Karatsuba’s algorithm.We will assume (for simplicity) that n = 2kfor some k > 0. Then for n > 1, we haveT(n) ≤ 3T(n/2) + cn for some constant c > 0 and T(1) = d for some constant d > 0.First show that 3k = nlog2 3. Now solve the recurrence relation and show that T(n) =(2c + d)nlog2 3 2cn thus concluding that T(n) ∈ O(nlog2 3) = O(n1.585). Show your working.(c) Show that T(2n)/T(n) ～ 3, that is, if we double the length of the integers then the time forKaratsuba’s algorithm increases by a factor of 3 (asymptotically).Question 2 (15 marks): GCD Algorithms(a) Implement the binary GCD algorithm in Maple as the Maple procedure named BINGCD tocompute the GCD of two positive integers a and b. Use the Maple functions irem(a,b) andiquo(a,b) for dividing by 2.Your Maple code will have a main loop in it. Each time round the loop please print outcurrent values of (a, b) using the commandprintf(a=%d b=%d\n,a,b);so that you and I can see the algorithm working. Test your procedure on the integers a =16 × 3 × 101 and b = 8 × 3 × 203.(b) I think Maple’s command GCD(A,B) mod p; uses the Euclidean algorithm to compute theGCD of two polynomials A(x) and B(x) in the ring Zp[x]. [ We will show later that for twopolynomials A(x) and B(x) of degree d, the Euclidean algorithm does O(d2) arithmetic operationsin Zp. ] Let’s verify if this could true by timing Maple’s Gcd(A,B) mod p; commandand seeing if the times are quadratic in the degree d. Execute the following code in Mapleand test to see if the times you get are quadratic in d. Justify your answer. Hint: if T(d) isthe time and T(d) is quadratic in d, what should T(2d)/T(d) approach when d large?1d := 1000;p := prevprime(2^30);for i to 7 doA := Randpoly(d,x) mod p;B := Randpoly(d,x) mod p;st := time();G := Gcd(A,B) mod p;tt := time()-st;printf(deg=%d G=%a time=%7.3fsecs \n,d,G,tt);d := 2*d;od:Question 3 (20 marks): The Gaussian IntegersLet G be the subset of the complex numbers C defined by G = { x + y i : x, y ∈ Z, i =√1 }.G is called the set of Gaussian integers and is usually denoted by Z[i].(a) Why is G an integral domain?What are the units in G?Let a, b ∈ G. In order to define the remainder of a divided by b we need a measure v : G → N forthe size of a non-zero Gaussian integer. We cannot use v(x + iy) = |x + iy| =px2 + y2 the lengthof the complex代做MACM 401作业、代写Maple worksheet作业、代做Java，Python语言作业、代写Java，c+ number x + iy because it is not an integer valued function. We will instead use thenorm N(x + iy) = x2 + y2for v(x + iy).(b) Show that for a, b ∈ G, N(ab) = N(a)N(b).Show that for a, b ∈ G with b 6= 0, N(ab) ≥ N(a).(c) Let a, b ∈ G with b 6= 0. Find a definition for the quotient q and remainder r satisfyinga = b q + r with r = 0 or v(r) 2 + y2. Using yourdefinition calculate the quotient and remainder of a = 63 + 10i divided by b = 7 + 43i.Hint: consider the real and imaginary parts of the complex number a/b and consider howto choose the quotient of a divided b. Note, you must prove that your definition for theremainder r satisfies r = 0 or v(r) will help you. Now since part (b) implies v(ab) ≥ v(b) for non-zero a, b ∈ G, this establishesthat G is a Euclidean domain.(d) Finally write a Maple procedure REM such that REM(a,b) computes the remainder r of adivided b using your definition from part (c). Now compute the gcd of a = 63 + 10i andb = 7 + 43i using the Euclidean algorithm and your REM procedure. You should get 2 + 3i upto multiplication by a unit. Also, test your procedure on a = 330 and b = ?260.Note, in Maple I is the symbol used for the complex number i and you can use the Re andIm commands to pick off the real and imaginary parts of a complex number. Also, the roundfunction may be useful. For example> a := 2+5/3*I;a := 2 + 5/3 I> Re(a);22> Im(a);5/3> round(a);2 + 2 IQuestion 4 (10 marks): The Extended Euclidean AlgorithmReference: Algorithm 2.2 in the Geddes text.Given a, b ∈ Z, the extended Euclidean algorithm solves sa + tb = g for s, t ∈ Z and g = gcd(a, b).More generally, for i = 0, 1, ..., n, n+ 1 it computes integers (ri, si, ti) where r0 = a, r1 = b satisfyingsia + tib = ri for 0 ≤ i ≤ n + 1.(a) For m = 99, u = 28 execute the extended Euclidean algorithm with r0 = m and r1 = u byhand. Use the tabular method presented in class that shows the values for ri, si, ti, qi. Hencedetermine the inverse of u modulo m.(b) Repeat part (a) but this time use the symmetric remainder, that is, when dividing a by bchoose the quotient q and remainder r are integers satisfying a = bq+r and ?|b/2| ≤ r instead of 0 ≤ r Question 5 (10 marks): MATH 701 and MATH 801 students onlySuppose we call the extended Euclidean algorithm with integers a ≥ b > 0. Thus r0 = a, r1 = band rn = g where g = gcd(a, b). Prove the following properties about the integers t0, t1, ..., tn, tn+1that appear in the extended Euclidean algorithm (assuming the positive remainder is used).(i) |ti1| | for i = 3, ..., n + 1.(ii) ri ti1 ri1 ti = (?1)i a for i = 1, ..., n + 1.(iii) tn+1 = (1)na/g. Hint: put i = n + 1 into (ii).Since the ti are increasing in magnitude from (i), then (iii) implies |tn| extended Euclidean algorithm with input a = m and b = u to compute the inverse of u modulo m.If g = 1, then we have ?m if tn 转自：http://ass.3daixie.com/2019012368012056.html