Puzzle for programmers

Cerebral distractions of every kind, mostly but not exclusively Countdown-related.

Moderator: Michael Wallace

Post Reply
Robert Lozyniak
Newbie
Posts: 17
Joined: Tue Aug 27, 2013 5:37 am

Puzzle for programmers

Post by Robert Lozyniak »

Here is a "trippy" function of my own invention.
Because I don't know your preferred programming language, I am posting in pseudocode.
(Here, hexadecimal constants end with an h, so Fh is fifteen and 10h is sixteen.)

Code: Select all

function trippy (int32 ball) {
  int32 bat = ball * 5
  bat = BitwiseOr(bat, CCCCCCCFh)
  bat = bat - ball
  bat = BitwiseAnd(bat, 33333330h)
  bat = IntegerDivide(bat, 8)
  bat = ball + bat
  bat = 3 * bat
  output bat
}
The puzzle: what does this function do? (Bonus points if you can explain how it does it.)

In case you're wondering, no, this is not homework.
I have a solution. The MD5 hash of my solution is 6dc3f8339e9f9b60b5f925968bc63ef4.
Dave Preece
Devotee
Posts: 621
Joined: Thu Feb 21, 2013 11:50 pm

Re: Puzzle for programmers

Post by Dave Preece »

11?
Robert Lozyniak
Newbie
Posts: 17
Joined: Tue Aug 27, 2013 5:37 am

Re: Puzzle for programmers

Post by Robert Lozyniak »

What the "trippy" function does:

Give it a binary-coded decimal number and it will triple it.
Example: Give it 75h, get 225h.


How it works:

Multiplication works the same in any base, except for the carries.

Example:
123 * 3 = 369 (decimal), and 123h * 3h = 369h (hexadecimal)
In this case, the digits come out exactly the same, because there are no carries.

Another example:
126 * 3 = 378 (decimal), and 126h * 3h = 372h (hexadecimal)
The only reason the digits do not come out the same here is that hexadecimal "waits" for 6 additional units before carrying.

Yet another example:
128 * 3 = 384 (decimal), and 128h * 3h = 378h (hexadecimal)
You can see here that the hexadecimal needs an additional twelve units to catch up to the decimal. This is because the decimal carry here is 2. In general, six additional hexadecimal units are required for each decimal carry. This suggests that, if we only knew the decimal carry in each place, we could add in the missing units as a correction.

Even though this is an entirely integer-based function, it has at its heart these facts of "floating-point" arithmetic:

1/5 in hexadecimal looks exactly like 1/3 in decimal: 0.333333...
2/5 in hexadecimal looks exactly like 2/3 in decimal: 0.666666...

Thus, multiplication by 5 in hexadecimal carries into each hexadecimal digit whatever multiplication by 3 would carry into the corresponding decimal digit.

Also note that multiplying a number by 5 does not change its residue modulo 4. Thus, during hexadecimal multiplication by 5, any change in the two low bits of each digit is entirely due to carries from the lower-order digits. We isolate these carries using bit-masks and subtraction.

Finally, a bit of algebra: we rewrite (3*x)+(6*(y/16)) as 3*(x+(y/8)).
Post Reply