Code Analysis

Below, you are given yet another of Stofl's complicated programs (as a C++, Pascal and Python version – all identical). The function algorithm performs a mathematical operation. Your task is to figure out what the function calculates and, more importantly, why it calculates what you claim. Also you should think about whether it always works or if there are some constraints on the value of input and the initial value of output for the function to succeed.

This is a theoretical task and you are not expected to write any code but you should submit a textual solution instead. You can, however, add (pseudo-)code if you think it helps your explanations.

You may assume that the value of input is a non-negative real number.

C++ version

#include <cmath>
 
double algorithm(double input) {
  double output = 100.0, change = 2.0;
  const double eps = 0.0000001;
  const double magic = 0.69314718056;
  while(fabs(change - 1.0) > eps) {
    change = input/pow(2.0,output);
    output -= (1.0-change)/magic;
  }
  return output;
}

Pascal version

Uses Math;
 
function algorithm (input : double) : double;
var change, eps, magic : double;
begin
   algorithm := 100.0;
   eps := 0.0000001;
   change := 2.0;
   magic := 0.69314718056;
   while abs(change - 1.0) > eps do
   begin
      change := input/power(2.0,algorithm);
      algorithm := algorithm - (1.0 - change)/magic;
   end
end;

Python version

from math import fabs, pow
 
def algorithm(input):
    output, eps, change, magic = 100.0, 0.0000001, 2.0, 0.69314718056
    while fabs(change - 1.0) > eps:
        change = input/pow(2,output)
        output -= (1.0-change)/magic
    return output

Notes

Stofl's program uses the mathematical operations for the absolute value and the power function. More precisely, you can assume that the C++ function fabs(x), the Pascal function abs(x) and the Python function fabs(x) all calcuate the following value \begin{align*} \lvert x\rvert = \cases{x, &\text{ if } x\geq 0 \cr -x &\text{ otherwise}} \end{align*}

Moreover the C++ function pow(2, x), the Pascal function power(2, x) and the Python function pow(2, x) calculate $2$ to the power of $x$, that is, they calculate the value \begin{align*} 2^x. \end{align*} Note that in our example, the values of $x$ need not be integers, that is, $x$ can be any real number, such as $8.25612$.

Corrections

  • October 1: Initial value of output in Python sourcecode was incorrectly set to 1 instead of 100.

Submission