Below, you are given Stofl's latest program (as a *C*, *Pascal* and *Python* version – all identical).
He does some very complicated calculations in the function *Calculate* using the helper function *Operation*.
The aspiring programmer Andrew is looking at Stofl's source code but cannot figure out what it does. Can you help Andrew understand what the function *Calculate* computes?

Also, Andrew is curious if it is possible to write a new implementation of the function *Calculate* that works
as fast as possible and always returns the same outcome as the original one.

Note that we only care about the asymptotic running time and you do not have to improve the running time of your program by constant factors. So if you have found a solution and now see a way to make it $10$ times faster, this will not give you any more points but probably only make your explanation more complicated. If, on the other hand, you find a way to make your solution faster by a factor of $\sqrt{n}$ or even $n$, this will give significantly more points, assuming the new solution is still correct. Consequently we are also not interested in numerical measurements, so you do not have to include statements like «It takes 3.5 second for $n=1000$». We will score your program depending on the correctness, the description and the asymptotic running time complexity only.

You may assume that the function *Calculate* will only be called with $n\geq 2$ and $a\geq 0$.

int Operation(int c, int d) { if (c<d) { return 0; } else { return Operation(c-d,d)+1; } } int Calculate(int a, int n) { int i,j,x,res; res = a; for (i = 1; i<=n; i++) { for (j = 2; j<=i; j++) { x = Operation(i,j); if (x*j==i) { res = res ^ j; // A bitwise XOR-operation. } } } return res; }

function Operation(c,d: integer):integer; begin if c<d then Operation := 0 else Operation := Operation(c-d,d) + 1; end; function Calculate(a,n: integer):integer; var i,j,x : integer; begin Calculate := a; for i := 1 to n do begin for j := 2 to i do begin x := Operation(i,j); if x*j=i then Calculate := Calculate xor j; { A bitwise XOR-operation. } end; end; end;

def Operation(c,d): if c<d: return 0 else: return Operation(c-d,d)+1 def Calculate(a,n): res = a for i in range(1,n+1): for j in range(2,i+1): x = Operation(i,j) if x*j == i: res = res ^ j # A bitwise XOR-operation. return res

It is extremely important that your explanation of Stofl's program, as well as your optimized program, are correct. Hence, you need to give good arguments about the correctness of your solution. In particular, it is better to have a slower solution whose correctness you can prove than having a faster solution without convincing arguments. Arguments such as «my optimized program gives the same answer for any $n\leq 42$» are not convincing. Nonetheless it might be a good idea to verify your optimized programs by fuzzy-testing1) against the slow implementation.

In case you do not know what the bitwise XOR-operation does, you will find a lot of explanations online. For example the article http://www.codeproject.com/KB/cpp/bitbashing.aspx.

Also feel free to use the programming language you prefer, it does not have to be one of the example-languages.

1) Inputting arbitrary values and checking if they output the same.