|Perl: the Markov chain saw|
Determining if a rational number terminatesby blackle (Beadle)
|on Nov 29, 2012 at 15:56 UTC||Need Help??|
Hello all. A friend of mine had participated in a programming competition for his school. He did pretty well, but he couldn't get one question. The question was, given the numerator and denominator of a rational number, determine if the decimal expansion terminates. This is to say, if I gave you 1/3, you would say it doesn't because the expansion is "0.3333..." Likewise, if I gave you 1/10, you would say it does terminate because the expansion is "0.1"
My friend had tried to solve this problem with string operations, but I found a better way. According to the Wikipedia article for repeating decimals, rational numbers that terminate are in the form a/b -> b = 2^c*5^d where c and d are natural numbers. Given this identity, I developed the following (obfu) one-liner:
Given $ARGV = a; $ARGV = b the program will say "Y" if the decimal terminates and "N" if it doesn't.
The spoiler below reveals how the program works:
Here is an expansion of the script so it's readable:
Essentially, the script iterates through every possible exponent for 5 and checks if denom/5^ex is a power of two. If it finds an exponent where this is the case, the decimal must terminate so it sets the result variable to "Y". In the obfu version the for loop is replaced with a map and the printing of "Y" and "N" takes advantage of the non-printing character "\r". The "\r" brings the cursor to the start of the line and overwrites the previously printed "N" with a "Y". This means the script only works on media that supports "\r" like a terminal.
Another big difference is the way the obfu version checks if denom/5^ex is a power of two. For this I took advantage of the IEEE-754 floating point specification, which states that the first 52 bits of a double is the "mantissa" while the next 11 is the "exponent". If the mantissa is equal to zero the number must be a power of two.
I'm not too familiar with pack/unpack to understand why saying "b52" gives the 52 bits of the mantissa rather than the sign, the exponent and 40 bits of the mantissa. I had expected unpack to read the bits from left to right, but I guess it starts at the least significant bit and goes up.