Assignment 9 - Digit Hunting

1. Getting started

   Please refer to this page for information on how to work on your assignment.

2. Task of this exercise

   The task of this homework is to get familiar with the usage of functions written by others, which occurs when working in teams of programmers in companies. Furthermore, this homework should give an idea how digit hunting — that is computing large quantities of digits of famous numbers — is performed in practice.

3. 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.

4. 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 variable name 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.

5. 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.

6. 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 and y would be normal numerical variables:

   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 longnull() command 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.

7. Compute Euler's Function

   Euler's Number e is just the value e¹ of the exponential function. This function is an infinite sum:

   $$e^{\raisebox{1ex}{$i$}\!\left/ \!\raisebox{-1ex}{$j$}\right.}=1+\frac{i^1}{j^1\times 1!}+\frac{i^2}{j^2\times 2!}+\frac{i^3}{j^3\times 3!}+\dots$$

   One can compute it iteratively by an algorithm which could be written as the following pseudo-code:

   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 JavaScript 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.

8. Computing the 1000-th power of a number

   This routine implements the following algorithm to compute 2¹⁰⁰⁰. 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¹⁰⁰⁰ = 2^10×100 = (2¹⁰)¹⁰⁰ = 1024¹⁰⁰.

   Change the algorithm such that it computes 3¹⁰⁰⁰ instead of 2¹⁰⁰⁰. You can use that 3¹⁰ = 59049. If all implemented well, the displayed number should be an integer and have 20001 as its last digits.

9. Computing the arctangent

   Inverting the tangent 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/\left(k^2+1\right)$$ $$\arctan \left(\frac{1}{k}\right)=k\times \left(h+h^2\times \frac{2}{3}+h^3\times \frac{2\times 4}{3\times 5}+h^4\times \frac{2\times 4\times 5}{3\times 5\times 7}+\dots \right)$$

   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 u variable 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 the v and w variables which contain the terms belonging to arctan(1/57) and arctan(1/239) which should be added to x as well. These variables 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?