278 ARITHMETIC 4.3.2 k 13. [M.%] (Automorphic numbers.) (Dedicated web hosting)
278 ARITHMETIC 4.3.2 k 13. [M.%] (Automorphic numbers.) Au n-place decimal number 5 > 1 is called an automorph by recreational mathematicians if the last n digits of z2 are equal to CL For example, 9376 is a 4-place automorph, since 93762 = 87909376. [See Scientific American 218 (January 1968), 125.1 a) Prove that an n-place number z > 1 is an automorph if and only if z mod 5n = 0 or 1 and ~rnod2~ = 1 or 0, respectively. (Thus, if ml = 2 and m2 = 5 , the only two n-place automorphs are the numbers Ml and MZ in (7).) b) Prove that if z is an n-place automorph, then (3~~ - 2~~) mod 102n is a an-place automorph. c) Given that cx E 1 (modulo y), find a simple formula for a number c depending on c and x but not on y, such that crx2 E 1 (modulo y2). l 4.3.3. How Fast Can We Multiply? The conventional method for multiplication in positional number systems, Algorithm 4.3.1M, requires approximately cmn operations to multiply an m-digit number by an n-digit number, where c is a constant. In this section, let us assume for convenience that m = n, and let us consider the following question: Does every general computer algorithm for multiplying two n-digit numbers require an execution time proportional to n2, as n increases? (In this question, a general algorithm means one that accepts, as input, the number n and two arbitrary n-digit numbers in positional notation, and whose output is their product in positional form. Certainly if we were allowed to choose a different algorithm for each value of n, the question would be of no interest, since multiplication could be done for any specific value of n by a table-lookup operation in some huge table. The term computer algorithm is meant to imply an algorithm that is suitable for implementation on a digital computer such as MIX, and the execution time is to be the time it takes to perform the algorithm on such a computer.) A. Digital methods. The answer to the above question is, rather surprisingly, No, and, in fact, it is not very difficult to see why. For convenience, let us assume throughout this section that we are working with integers expressed in binary notation. If we have two 2n-bit numbers u = (usn-r . . . uru~)s and v = (UZn-1. * * 211wo)a, we can write u = 2nUl + UrJ, 2) = 2 Vl + vo, (1) where Ur = (Q+-~. . . un)s is the most significant half of the number u and uo = (z&l.. . ~0)s is the least significant half ; similarly VI = (wzn–l . . . z1,)~ and V. = (u,-~. . .210)2. Now we have uw = (22, + 2 )U~V~ + 2yiY1 -Uo)(Vo -VI) + (2 + 1)UuVc. (2) This formula reduces the problem of multiplying an-bit numbers to three multi- plications of n-bit numbers, namely VI&, (Vi -Uo)(Vo -VI), and UoVo, plus some simple shifting and adding operations.