Wherein Pavel wastes Harry's time
Apr. 5th, 2006 11:58 amGAH.
So our assignment for yesterday in CS was to write an absolute value function for integers in as few operations as possible - no conditionals or loops, no multiplication or division, no comparisons. To make it as assemblish as possible, all statements (aside from the final return x) had to be either of the form
variable = variable op variable; or
varaible = variable op constant;
where op is one of +,-,&,|,^,<<,>>,>>> (at this point you say, "What? There's no such operator in C!" So, yes, it didn't actually have to be legal (or even compilable) C code, it just had to be right, making the assumption that >> and >>> act like they do in Java). We were allowed to assume 32-bit integers.
My initial solution was 6 operations. Then Pavel came and told me he had done it in 2.
2?! That didn't seem possible! Well, I soon got it down to 4, and then 3. But 2? I spent several hours trying to get it, as well as asking Pavel and others if, really, it worked - if he had tested on such-and-such cases, if he had actually *proved* it works, etc. Well, Lucas said he saw it tested too, and it worked. It was about 3:00 before I finally gave up. I had decided it was almost certainly impossible. I had no idea what Pavel did. I figured I would hand in the 3-operation version.
So I saw Pavel's code today, of course. He wasn't computing the absolute value at all, he was computing the negation. Turns out, though, in testing it, he was calling the standard abs() function. Professor Rogers warned us that might happen if we named the function abs(), and we ought to call it something else, but I suppose he didn't see that email, or think to not include <stdlib.h>. Gah!
-Sniffnoy
So our assignment for yesterday in CS was to write an absolute value function for integers in as few operations as possible - no conditionals or loops, no multiplication or division, no comparisons. To make it as assemblish as possible, all statements (aside from the final return x) had to be either of the form
variable = variable op variable; or
varaible = variable op constant;
where op is one of +,-,&,|,^,<<,>>,>>> (at this point you say, "What? There's no such operator in C!" So, yes, it didn't actually have to be legal (or even compilable) C code, it just had to be right, making the assumption that >> and >>> act like they do in Java). We were allowed to assume 32-bit integers.
My initial solution was 6 operations. Then Pavel came and told me he had done it in 2.
2?! That didn't seem possible! Well, I soon got it down to 4, and then 3. But 2? I spent several hours trying to get it, as well as asking Pavel and others if, really, it worked - if he had tested on such-and-such cases, if he had actually *proved* it works, etc. Well, Lucas said he saw it tested too, and it worked. It was about 3:00 before I finally gave up. I had decided it was almost certainly impossible. I had no idea what Pavel did. I figured I would hand in the 3-operation version.
So I saw Pavel's code today, of course. He wasn't computing the absolute value at all, he was computing the negation. Turns out, though, in testing it, he was calling the standard abs() function. Professor Rogers warned us that might happen if we named the function abs(), and we ought to call it something else, but I suppose he didn't see that email, or think to not include <stdlib.h>. Gah!
-Sniffnoy
