Determining if a rational number terminates

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:

print"N",(map{"\rY"if(unpack"b52",pack"d",$=/5**$_)<1}0..log($==pop)),
+$/
[download]

Given $ARGV[0] = a; $ARGV[1] = 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:

my $denom = $ARGV[1];
my $result = "N";
for(my $ex = 0; $ex < log($denom)+1; $ex++){
    my $power = $denom/5**$ex;
    my $ex2 = log($power)/log(2);
    if($ex2 = int($ex2)){
        $result = "Y";
    }
}
print $result;
print "\n";
[download]

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.

Comment on Determining if a rational number terminates Select or Download Code

Replies are listed 'Best First'.
Re: Determining if a rational number terminates by tobyink (Canon) on Nov 29, 2012 at 16:27 UTC
Nicely obfuscated, but this is shorter: `$_=pop;$_/=2until$_%2;print/(5\|^1)$/?Y:N,$/` [download] `$_=pop;for$.(2,5){$_/=$.until$_%$.}print/^1$/?Y:N,$/` [download] Of course, neither of these works for the fraction 3/6 which of course terminates as 0.5. For that to work, you'd need to add an initial step to reduce the fraction to its lowest terms. `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply] [d/l] [select]
Re^2: Determining if a rational number terminates by tobyink (Canon) on Nov 29, 2012 at 16:52 UTC
There are probably shorter ways of doing it, but... `# It is important to clearly comment your code to make it easier # for future maintainers. # # This is the numerator, denominator pair for which we wish to # determine if the decimal expansion terminates. # @ARGV = (33, 660); # Check if it terminates and print "Y" or "N". # sub _{@i=sort{$b-$a}@_;return$i[1]if$i[0]==$i[1];@i=($i[1],$i[0]%$i [1])while$i[1];$i[0]};sub __{$j=_@_;$_/=$j for@_;$_[1]<0and do{$_*= -1for@_}}__(($k,$l)=@ARGV);$l/=2until$l%2;print$l=~/(5\|^1)$/?Y:N,$/` [download] `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply] [d/l]
Re^3: Determining if a rational number terminates by blackle (Beadle) on Nov 29, 2012 at 18:12 UTC
Thanks for that, I didn't even consider that it wouldn't be in lowest form. It's really clever to take advantage of the fact that powers of five always end with five, I suppose then it's better to divide out the powers of two first than the powers of five. Tomorrow I will ++ both of these :D	[reply]
Re^4: Determining if a rational number terminates by tobyink (Canon) on Nov 29, 2012 at 20:13 UTC
Re^3: Determining if a rational number terminates by pemungkah (Priest) on Dec 03, 2012 at 01:34 UTC
+1 for ironic comment on comments. As we all know, the uncommented part is the part that needs the comment here. (And if you say "the code is obvious and needs no comments", it's my sincere opinion you need to get out more.)	[reply]
Re^4: Determining if a rational number terminates by tobyink (Canon) on Dec 03, 2012 at 07:37 UTC
Re^2: Determining if a rational number terminates by trizen (Hermit) on Dec 25, 2012 at 17:26 UTC
Shorter still: `perl -E'$_=10;$_/=5until$_%5;say$_&$_-1?N:Y'`	[reply] [d/l]
Re: Determining if a rational number terminates by herveus (Prior) on Nov 29, 2012 at 19:14 UTC
Howdy! What you really mean is "does this rational number's decimal expansion have a form that ends with zeros?". 1/10 has two forms: 0.1000000000... and 0.099999999999... They are equal. yours, Michael	[reply]
Re^2: Determining if a rational number terminates by tobyink (Canon) on Nov 29, 2012 at 20:14 UTC
They are equal, but one is generally recognised as the more canonical representation. `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply]
Re: Determining if a rational number terminates by ColonelPanic (Friar) on Nov 30, 2012 at 09:36 UTC
Here's a short one: `use bigrat;print((shift()10*1000/shift())=~?/??'N':'Y')` [download] Is this blatant cheating? Perhaps :) When's the last time you used duct tape on a duct? --Larry Wall	[reply] [d/l]
Re^2: Determining if a rational number terminates by tobyink (Canon) on Nov 30, 2012 at 10:07 UTC
This produces a deprecation warning in recent versions of Perl thanks to `?/?`. You can use `'/'` or `"/"` instead to avoid the deprecation warning. Perl is smart enough to know you meant a regexp rather than a string if it follows `=~`. bigrat is in core, so I don't consider it cheating. Now, if you wrote chkrat.pm, and uploaded it to CPAN specifically to help your golf score, that would be cheating. However, I'm disappointed by the lack of a line break. Here's my reinterpretation of your implementation. I've added a line break at the cost of three keystrokes, but managed to save six keystrokes elsewhere... `use bigrat;print((shift()101000/shift)=~"/"?N:Y,$/)` [download] These are also quite cute, though very slightly longer... `use bigrat;print[Y,N]->[(shift()10*1000/shift)=~"/"],$/` [download] `use bigrat;$_=shift()10**1000/shift;print[Y,N]->[m"/"],$/` [download] `perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'`	[reply] [d/l] [select]
Re^3: Determining if a rational number terminates by ColonelPanic (Friar) on Nov 30, 2012 at 10:46 UTC
Thanks for your suggestions. Here is a yet shorter version: `use bigrat;print+(1e1000/pop()*pop)=~"/"?N:Y,$/` [download] When's the last time you used duct tape on a duct? --Larry Wall	[reply] [d/l]


Problems? Is your data what you think it is?
	PerlMonks