Code Analysis

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

C version

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;
}

Pascal version

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;

Python version

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

Notes

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.

Submission

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