Please refer to this page for information on how to work on your assignment.
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.
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.
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.
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.
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.
Euler's Number e is just the value e^{1} 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.
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.
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)$$ $$\mathrm{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?