A Disgusting Function

I have a few friends in the engineering program at Purdue. They have to take a class called CS159, which formally teaches them the programming language C, presumably with its applications to engineering. I don’t really know the details, as I neither am in their program nor the class.

They had an assignment that revolves around a user selecting between three given formulas, inputting an argument and receiving the computed value. The catch? If-statements are entirely illegal. The majority of C is similarly off limits.

The approach they are told to use is to generate some expression in C that based on two values, an integer that stores the choice between equations 1, 2 and 3 and the actual argument, that would both select the desired formula and evaluate the argument in the formula. ~~I don’t remember the exact term, and Google isn’t helping with my searches, but I believe it to be something along the lines of “selection by computing.”~~ [EDIT:] The official term is selection by calculation. Anyways, the solution the TAs and students came up with is the following, where $n$ is a variable that stores the choice of formula and $x$ is the argument. Here, I will use $f_n(x)$ to designate the nth formula.

$A = \left((\text{int}) \frac{1}{n}\right)f_1(x) + \left((n+1) \% 2\right)f_2(x) + \left((\text{int}) \frac{n}{3}\right)f_3(x).$

The idea is that if $n=1$ , only $f_1(x)$ should be evaluated and not the rest. How is this done? We wish for $f_1(x)$ to, well, exist. and not the other two functions. The easiest way is to have some function in terms of $n$ that is 1 when $n$ is 1, but 0 for all other values. We also need a function that is 0 when $n$ is not 2 but 1 if it is, and likewise for $n$ is 3. Their method takes advantage of how rounding in C works.

$\frac{1}{n}$ is 1 when $n$ is 1, but a number less than 1 for all other relevant values $n$ . By casting it to an integer, it is always rounded down to the greatest integer less than it. That is, 1 will stay as 1, but 0.5 would become 0.

If $n=1$ , $\frac{1}{1}=1$ , which is rounded down to 1. This means if the user selects formula 1, formula 1 will be run.
If $n=2$ , $\frac{1}{2}=0.5$ which is rounded down to 0. This means if the user selects formula 2, formula 1 will not be run.
The same logic for $n=1$ applies here.

The second term takes advantage of modular arithmetic. It says to increment the choice variable by 1, divide by two then take the remainder.

If $n=1$ , $n+1=2$ , which has remainder 0 modulo 2. This means if the user selects formula 1, formula 2 will not be run.
If $n=2$ , $n+1=3$ which has remainder 0 modulo 2. This means if the user selects formula 2, formula 2 will be run.
The same logic for $n=1$ applies here.

The third term again takes advantage of how rounding works.

If $n=1$ , $\frac{1}{3}=0.33\ldots$ , which is rounded down to 0. This means if the user selects formula 1, formula 3 will not be run.
The same logic for $n=1$ applies here.
If $n=3$ , $\frac{3}{3}=1$ , which is rounded down to 1. This means if the user selects formula 3, formula 3 will be run.

This is incredibly ad-hoc and not systematic whatsoever. Worse still, the methods here will not work for more choices. What if we had four choices? Only the very first term will work as expected. What if we had exactly 73 choices? What should the 63rd term be?

I had my own expression before I saw the one above. It’s very computationally expensive, with $O\left(({n-1})^{n-1}\right)$ so it’s more of a novelty than anything, but it generalizes nicely to certain $n$ . I jokingly called it the Patel formula after one of my friends, and then later called it the Herr-Patel formula or HPF.

Again, I think they should just be allowed to use if-statements, but I digress.

$2A = ((n-2)(n-3)\mod{3})f_1(x) + ((n-1)(n-3)\mod{3})f_2(x) + ((n-1)(n-2)\mod{3}f_3(x).$

The idea is for the terms, if our choices are 1-3, and we only want, say, $n=1$ to give a value but the rest to be 0, we can have $(n-2)(n-3)$ as our term. This is trivially 0 for $n=2,3$ but not when $n=1$ . We can then change the factors of this polynomial to filter out different values of $n$ and append those to the specified functions.

The terms are then evaluated modulo 3. This is done for two reasons. (In the original formulation, the $(x-3)$ factors were actually just $x$ . I made the change to make the formula more readable; note that the two factors function identically modulo 3) Note that if one takes an integer modulo $x$ , the set of inputs ranges from 0 to $x-1$ . I could have written the expression to be mapped from 0 to 3, but this would require a total of 4 terms. Instead, I “remapped” the $n=3$ term to the $n=0$ term by taking the expression modulo 3. Doing so means our inputs will now be from 0 to 2 instead of 0 to 3.

The second reason, which actually is not satisfied, is to hold magnitudes constant at 1. So instead of working with $37 f_{2}(x)$ or something, it would just be $f(x)$ . This actually didn’t work out; they all turned out to be 2. At the time, this was good enough. Simply divide by two at the very end, and no harm, no foul.

I actually came up with the equation generalizing from a much simpler case for when $n$ ranged from 1 to 2. A subconscious design goal was to have an expression that generalized easily to however many $n$ was needed.

In the formula presented above, it works for the case where $n = \{1,2,3\}$ . To generalize the formula for a greater number of choices, one needs to add a new term to allow another choice to be made and then give each term a new factor. So for the $n = 5$ case, for instance,

$((x-2)(x-3)(x-4)(x-5) \mod{5})f_1(x) + ((x-1)(x-3)(x-4)(x-5)\mod{5})f_2(x) + \ldots.$

There’s a problem, however. The generation of these expressions require that given a certain choice $n$ , it should output a single function, and have the rest zero out, by creating a polynomial that filters out all other choices. This does not work in general. This formula does not, and can not exist in general for more than five choices. Further, in the $n=3$ case, the entire expression is divided by two. Without blindly testing, how do we know what to divide by?

This is actually a problem in number theory.

The explanation and the mechanics behind it makes use of the fact that integers modulo prime numbers are a field, but integers modulo composite numbers form a ring. These are the same ideas that prove Wilson’s theorem, with the help of Lagrange’s theorem, but this explanation is quite technical and I can’t wrap my head around it myself. Instead, I will give a non-rigorous, incomplete proof, that explains the main ideas specific to this problem.

Consider what happens when we take the first term of the supposed $n = 6$ case, $((x-2)(x-3)(x-4)(x-5)(x-6)\mod{6}) f_(1)x$ and evaluate it at $n=2,3,4,5,6$ . This should give us zero, and it does so trivially. However, what happens if we have $n=1$ ? Writing this term out explicitly gives

$((1-2)(1-3)(1-4)(1-5)(1-6)\mod{6}) f_1(x)$ , which partially simplifies to

$((-1)(-2)(-3)(-4)(-5)\mod{6}) f_1(x)$ , which is equivalent to

$(5 \times 4 \times 3 \times 2 \times 1 \mod{6}) f_1(x)$ . And therein lies the problem. In that expression, we evaluate $2 \times 3$ , which equals six, which becomes zero modulo six. Instantly, the entire expression goes to zero. Boom.

But wait, that’s a problem! It’s not supposed to go to 0. This term is supposed to be 0 when $n\neq 1$ , but be something when $n$ does equal 1. This problem happens for all of the terms; no matter what the choice is for $n$ , the term is zero. The entire expression as a whole, will evaluate to zero, becomes no matter what, a $2 \times 3$ will slip in there somehow, making the entire thing zero.

And like that, the formula breaks. However, this problem can be avoided. In the 6 choices case, we had a problem where no matter what, a $2 \times 3$ slips in and instantly breaks the problem. There were two numbers that, no matter what, multiplied to be the modulus. So, we need to avoid instances where two numbers can possibly multiply to our modulus.

Those numbers are the prime numbers, as they are only divisible by themselves, 1 and no other numbers. So for 2, 3, 5, 7 and so on choices, the formula looks good. I actually don’t know why 4 works.

The last step is to find out what to divide all the numbers by. This is just turns out to be $n - 1$ , or one less than the number of choices. Why? Consider the second term for 3 choices, $(n-1)(n-3) \mod{3}$ . If $n=2$ , then the term becomes $(2-1)(2-3) \mod{3}$ , which simplifies to become $(1)(-1)\mod{3}$ , equivalent to $1\times 2 \mod{3}$ , or $2! \mod{3}$ or $(3-1)! \mod{3}$ . In fact, since each term is just the previous term but just shifted to filter out different values, if a term doesn’t go to zero, it is equivalent to $(n-1)! \mod{n}$ . By Wilson’s theorem, this is $n-1$ .

And like that, we are done. For prime $n$ cases, we have an expression that, when given a variable $n$ that stores a choice of term and a bunch of functions $f_n(x)$ to be evaluated at $x$ , outputs the specific function evaluated at $x$ . In summation form, it is given by

$(n-1)A = \sum_{i=0}^{n} \left( \frac{\prod_{j=1}^{n} (x-j)}{(x-i)}f_{i}(x) \mod{i} \right)$ .

A Disgusting Function

Published by zylitol

Leave a comment Cancel reply

Share this:

Related

Published by zylitol

Leave a comment Cancel reply