10
$\begingroup$

C source code at: http://pastebin.com/6Bywk5mf
Will also function in Java. Note that in C this won't work for values above 127 unless you change char to unsigned char.

Two questions:

  1. Easy - What does the function do? This shouldn't require more than two words explanation.
  2. Hard - How does it work? Of course this is slightly ill-defined, what "how" constitutes; you could just say "it executes this series of operations". I would consider that, if you can understand how this function was written, then you understand how it works.
$\endgroup$
  • 3
    $\begingroup$ this function return the value of v21 $\endgroup$ – lois6b Nov 3 '16 at 8:42
  • $\begingroup$ Good grief what a long body that procedure has. It'd be slicker to implement the function as a look-up table. $\endgroup$ – Rosie F Nov 3 '16 at 8:49
  • 2
    $\begingroup$ This function makes the guy who replaces you want to hang himself when he realises the mess he just got himself into. More than two words, but accurate :) $\endgroup$ – Joe Nov 3 '16 at 8:54
  • 6
    $\begingroup$ I'm curious why people are downvoting. I don't use this site often and perhaps I don't understand the style of puzzle people enjoy here. Many of my friends really enjoyed this puzzle when I shared it with them, and a few of them encouraged me here. Is there a way this puzzle could be improved? $\endgroup$ – Alex Meiburg Nov 3 '16 at 8:55
  • 5
    $\begingroup$ I'm still trying to figure out what the code is doing with all the values it computes. This is not a code question, there's a real puzzle embedded in all that arithmetic. $\endgroup$ – Rubio Nov 3 '16 at 9:17
7
$\begingroup$

Ok, So I have a pretty good idea of what is going on but I can't tell you how you came up with one crucial number in this thing.

First things first

This function returns non 0 for all primes and 1 (specifically 1540723609 when ints are 32bits)

The hard thing

You are finding patterns in the bits of prime numbers to create a list of all the primes pretty much by hand

Simplified code

http://pastebin.com/h4Z0enYC

How it works

Now onto the important bits (pun definitely intended). First we notice that the function is broken up into 3 sections.

Section 1: Lines 1-17 - We can call this "Set up"

Section 2: Lines 18-334 - Call this "the workhorse"

Section 3: Lines 355-366 - Call this "clean up"

As @Rubio mentioned

Section 3 really doesn't do much, the result is determined before this point. All these lines do is cause an integer overflow so if the result was even - it is now 0. If it was odd - it is still odd and more importantly not 0. This whole section can be replaced with

 v21 = v21 & 1;

After realizing that - we can quickly discover this whole thing is

based on integer overflow! The beauty of overflow (or at least how it is most often implemented with negative numbers being stored as 2's compliment) is that some mathematical properties still hold. The one that we will use the most is

odd + odd = even
even + even = even
odd + even = odd
and the corollaries for multiplication
odd * odd = odd
even * even = even
odd * even = even

And with the beauty of math we can replace all the hard coded numbers in section 2 with

 odds => 1
 evens => 0

Drilling down even further into section 2 we realize

It is made up of multiple sections of the form

      v20 = 32579;
      v14 = v0 + 183840;
      v20 *= v14;
      v15 = v1 + 92055;
      v20 *= v15;
      v16 = v6 + 31344;
      v20 *= v16;
      v17 = v7 + 156091;
      v20 *= v17;
      v18 = v8 + 95882;
      v20 *= v18;
      v19 = v12 + 45047;
      v20 = v19;
      v21 = (v20 + 34185)(v21 + 177757) + 126015;
 

After we make the odds/even replacement it is simplified down to

      v20 = 1;
      v14 = v0;
      v20 *= v14;
      v15 = v1 + 1;
      v20 *= v15;
      v16 = v6;
      v20 *= v16;
      v17 = v7 + 1;
      v20 *= v17;
      v18 = v8;
      v20 *= v18;
      v19 = v12 + 1;
      v20 = v19;
      v21 = (v20 + 1)(v21 + 1) + 1;
 

Lets pause for a moment before we go down the rabbit hole of section 2 and tackle Section 1 - this part is easy now that we understand what is going on.

Section 1 is essentially breaking some number into its first 14 bits and storing them in the variables v thru v13 All the lines can be re-written to the form
vX = (v >> X) & 1

(I am avoiding that stupid first line that sets v to a silly number for a reason, ill get back to it later)

Lines 3-16 are all similar - divide v by a power of 2 which is just a bitshift to the right.

v1 = v/2 becomes v1 = v >> 1
v2 = v/4 becomes v2 = v >> 2

and so on. Keeping in mind this all based on overflow and the rules of math outlined above, we can safely say that we only care if the result is odd or even (if the last bit is a 1 a 0). Therefore all the lines in this section get rewritten as
v1 = v/2 becomes v1 = (v >> 1) & 1

We need one more piece of information before we go back to section 2. We need a few rules of the logic operators ~, & and |. When dealing a single bit (1 or 0) these equivalences hold true:

result = a & b is the same as result = a * b. 
result = ~a is the same as result = a + 1 (due to overflow in a single bit world
result = a | b is logically equivalent to result = ~(~a & ~b)
result = ~(~a & ~b) which is 1 + ((1+a) * (1+b))

Back to section 2 again now that we are armed with this new information. Lets keep making replacements in the part of section 2 we were working on.

      v20 = 1;
      v14 = v0;
      v20 &= v14;
      v15 = ~v1;
      v20 &= v15;
      v16 = v6;
      v20 &= v16;
      v17 = ~v7;
      v20 &= v17;
      v18 = v8;
      v20 &= v18;
      v19 = ~v12;
      v20 &= v19;
      v21 = v20 | v21
 

Now it is easy to see we don't need the variables v14-v21 at all. They are completely useless

      v20 = 1;
      v20 &= v0;
      v20 &= ~v1
      v20 &= v6;
      v20 &= ~v7;
      v20 &= v8;
      v20 &= ~v12;
      v21 = v20 | v21
 
simplifying one more step we get a one liner
 v21 |= v0 & ~v1 & v6 & ~v7 & v8 & ~v12
 

After we replace all the lines in section 2 with the one line above we can see a little clearer what is happening.

You Found patterns in the bits to create a list, in this case a list of known primes

The part I don't know

Line 2 - int v = a0 + ((a0*151)%256)/4*256;

What it does:

sets the first 8 bits of v to a0 and bits 8-13 to a number between 0 and 64 shifted left by 8. I assume this makes each number between 0 and 255 more unique (essentially a hash that adds more bits) and easier to target individual groups of numbers that have similar bit patterns.

Why 151?

Because it works? (I have no idea how you came up with this formula)

$\endgroup$
  • $\begingroup$ Nice analysis. I didn't have the time or patience to dig through what bits the various obfuscations were diddling by forcing overflows, just knew that's what was happening $\endgroup$ – Rubio Nov 3 '16 at 19:13
  • $\begingroup$ Great! The bit patterns were calculated using the Quine McCluskey algorithm. The multiplication by 151 was to give 6 "extra" bits to train the bit patterns off of, in order to get shorter cleaner answers, with some redundancy in the pattern as the price. Why 151? Not much reason. It would mix the bits well :P $\endgroup$ – Alex Meiburg Nov 3 '16 at 19:53
5
$\begingroup$

partial answer

Easy answer: the function

in two words "finds primes". not exactly, but close enough; it returns non-zero only if the input is 1 or a prime, for inputs between 0 and 255.

Hard answer:

I haven't the slightest idea what the mechanism here is. The computations are wrapping around MAXINT in a way that pushes the result to zero for composite input values, based on the binary-esque decomposition of "v" into v0..v13, but neither the meaning of "v" nor the choice of the magic constants make any sense to me.
I do know that the last 16 manipulations of v21 are superfluous; the result is already determined after
v21 = v21*(v21 + 14878);
(all that changes after that line is the specific value returned).

$\endgroup$
  • 2
    $\begingroup$ explanation coming? XD $\endgroup$ – lois6b Nov 3 '16 at 8:57
  • $\begingroup$ It actually tests if the number can be divided by itself and 1, so it will return non-zero for 1 as well. $\endgroup$ – w l Nov 3 '16 at 8:59
  • $\begingroup$ If the computations wrap around maxint, the correct answer should be "this function does whatever the compiler wants", because that's undefined behavior. $\endgroup$ – ffao Nov 3 '16 at 12:09
  • $\begingroup$ ffao, good point, made me chuckle :D would be curious to see if this has any interesting behavior on strange systems then, E.g one's complement $\endgroup$ – Alex Meiburg Nov 3 '16 at 12:16
  • 1
    $\begingroup$ Looking at the code again, there seems to be no input that does not make v20 overflow, so the optimizer may compile this as return 0 (nihilistic compiler), return 23 (illuminated compiler), return 42 (hitchhiking compiler), return 47 (enterprise compiler) or abort() (suicidal conpiler) or an endless loop (indecisive compiler). $\endgroup$ – Michael Karcher Nov 5 '16 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.