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:

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]


P is for Practical
	PerlMonks