Implemting basic computations with counter automata
Overview
By Church's Thesis, all reasonable models of computation give the
same time complexity classes. Somehow, counter programs are not
defined reasonably for polynomial time as it takes at least $2^n$ steps
to compute the number $2^n$ by iterative counting up. For this reason,
an alternative approach to counter automata can be formalized by permitting
the following operations with integer variables:
- All control structures of Java Script (if, while, do, for, usage
of user-defined functions).
- Addition, substraction and comparisons of integers, the
latter for the usage in if and while conditions.
- Arrays and other compound data types
are not permitted since otherwise one could simulate a Turing
machine directly what is not intended.
Task
The task of this homework is to complete the below programs for
multiplication, division, remainder and squareroot
such that they are carried out in polynomial time. The implementation
should only use the above permitted actions, although the testing loop
then verifies the operations using the standard arithmetic. Illegal
values should have 0 as return-value and the squareroots should be
downrounded.
Furthermore, the remainder of x over y and x+y over y are always the
same and the remainder of -x over -y is the negative value of the
remainder of x over y. The value of divide of x over y is given as
"Math.floor(x/y)" in Java Script notation.
The output "Please check the implementation" says that the result
is either incorrect due to an incorrect algorithm or that some
Java Script rounding errors occured within the program; the latter
occurs only for quite large testing data. This output comes up by
default as the preimplemented functions are incorrect.