Assignment 9 - Digit Hunting

1. Getting started
   Go into the directory public_html of your homepage if not already done. Then download this homework.

         wget http://www.comp.nus.edu.sg/~gem1501/assignment09.html
         chmod 755 *.html 

   Make yourself familiar with the functions you find. You should know the following on the implimentation.
   1. General Outline
      Implemented is some fixed point arithmetic on arrays. These arrays have length 305 which represent 100 digits on base 100000 before and 205 digits on base 100000 behind the dot. This corresponds to 500 digits before and 1025 digits after the dot in the decimal system. The last 25 digits are not displayed but just an attempt to minimize the effect of rounding errors. These long numbers can be added, negated, substracted and printed. Furthermore, one can multiply and divide by relatively small integers.
   2. Creating a new variable
      Technically, variables are arrays of the length 305 which is hold in the variable longlength. So you can create a new variable with the command

                x = new Array(longlength); 

      Writing the variablename is better style than writing 305 since you can later change the value assigned to this variable without having to change other parts the program.
   3. Printing a value of a variable
      You can print the content of a variable x with the command

                longprint(x); 

      Leading and trailing lines full of zeroes are not printed. The decimal dot appears at the end of the corresponding line.
   4. Arithmetic Operations with variables
      If x and y are arrays of length 305 and i,j normal integer variables or integer-valued expressions then the following operations can be performed. As an explanation you see the normal commands performed if x,y would be normal numerical variables.

                 Command             Explanation
                 longadd(x,y);       Adding y to x           x = x+y;
                 longsub(x,y);       Substracting y from x   x = x-y;
                 longnegate(x);      Negating x              x = -x;
                 longinit(x,i,j);    Initiallize x as i/j    x = i/j;
                                     If j<1, this operation does just x = i;
                 longmult(x,i,j);    Multiplying x with i/j  x = x*i/j;
                                     If j<1, this operation does just x = x*i;
                 longnull(x)         Tests for 0             (x == 0) 

      One can use the command longnull in while loops for testing whether a certain value has been reached. Sample statements:

                 longinit(x,200,345*678);
                 var n = 3;
                 while (!longnull(y))
                   { longadd(x,y); longmult(y,4,n); n = n+3; }
                 longprint(x); 

      For further examples, see the routines already coded in the source code of the Main Program after the corresponding "document.write"-command.
   
   
   
2. Compute Euler's Function
   Euler's Number E is just the value EXP(1) of the exponential function. This function is an infinite sum:

         EXP(i/j) = 1 + i/(j*1) + i*i/(j*j*1*2) + i*i*i/(j*j*j*1*2*3) + ... 

   One can compute it iteratively by an algorithm which could be written as follows:

          x = 0; y = 1; n = 1;
          while (y >= 10000^{-305})
            { x = x+y; y = y*i/(j*n); n = n+1; } 

   where the number y becomes 0 when it falls below 10000 to the power of -305. More precisely, if y comes very close to 0 such that no digit of the representative is different from it, one can stop the summation. This algorithm is implemented as follows. Note that "!" denotes the logical negation in Java Script programs.

         longinit(x,0,0); longinit(y,1,0); n=1;
         while (!longnull(y))
           { longadd(x,y); longmult(y,1,n); n=n+1; }
         longprint(x); 

   Adapt these commands such that not E but its square is computed. So y should be multiplied with 2/n and not with 1/n in each round. If all implemented well, the displayed number should have 77157 as the last digits.



3. Computing the 1000-th power of a number
   This routine implements the following algorithm to compute 2^1000. It initializes y as 1 and then multiplies it with 1024 in total 100 times. Since the algorithm needs a lot of time, it is better to do 100 than 1000 multiplications and to apply the equation 2^1000 = 2^(10*100) = (2^10)^100 = 1024^100.
   
   Change the algorithm such that it computes 3^1000 instead of 2^1000. You can use that 3^10 = 59049. If all implemented well, the displayed number should be an integer and have 20001 as its last digits.



4. Computing the Arcus Tangens
   Inverting the Tangens function is one method to compute famous numbers. One of these numbers has the value 24*Arctan(1/8)+8*Arctan(1/57)+4*Arctan(1/239). Euler found the following method to compute these values:

         h = 1/(k*k+1);
         Arctan(1/k) = k*(h + h^2 * 2/3 + h^3 * 2*4/(3*5) +
                       h^4 * 2*4*6/(3*5*7) + h^5 * 2*4*6*8/(3*5*7*9) + ...)

   The implemented algorithm to compute 24*Arctan(1/8) is then the following:

         longinit(x,0,0);
         longinit(u,24*8,65);
         n = 3; m = 2;
         while(!longnull(u))
           { longadd(x,u);
             longmult(u,m,n*65);
             n=n+2; m=m+2; }
         longprint(x); 

   So x is initialized as 0 and should later contain 24*Arctan(1/8). The variable u contains the 24 times k times the term to be added, this multiple can be used due to the distributivity of the infinite sum. In each round, u is multiplied with m and divided by n*(k*k+1) where k = 8 and k*k+1 = 65.
   
   Update this algorithm by also considering variables v and w which contain the terms belonging to Arctan(1/57) and Arctan(1/239) which should be added to x as well. These variable should be initialized as 8*57/3250 and 4*239/57122, respectively. You can either update them in the same loop or write additional loops for v and w. Here 57 and 239 are the values for k and 3250 and 57122 for k*k+1, respectively.
   
   If all is implemented well, the final outcome should have the digits 01989 at the end. Which number did you obtain?