Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Determining if a rational number terminates

by blackle (Beadle)
on Nov 29, 2012 at 15:56 UTC ( #1006283=obfuscated: print w/ replies, xml ) 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:

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

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
Re: Determining if a rational number terminates
by tobyink (Abbot) on Nov 29, 2012 at 16:27 UTC

    Nicely obfuscated, but this is shorter:

    $_=pop;$_/=2until$_%2;print/(5|^1)$/?Y:N,$/
    $_=pop;for$.(2,5){$_/=$.until$_%$.}print/^1$/?Y:N,$/

    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'

      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,$/
      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'

        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

        +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.)

      Shorter still:

      perl -E'$_=10;$_/=5until$_%5;say$_&$_-1?N:Y'
Re: Determining if a rational number terminates
by herveus (Parson) 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

      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'
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')
    Is this blatant cheating? Perhaps :)


    When's the last time you used duct tape on a duct? --Larry Wall

      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()*10**1000/shift)=~"/"?N:Y,$/)

      These are also quite cute, though very slightly longer...

      use bigrat;print[Y,N]->[(shift()*10**1000/shift)=~"/"],$/
      use bigrat;$_=shift()*10**1000/shift;print[Y,N]->[m"/"],$/
      perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
        Thanks for your suggestions. Here is a yet shorter version:
        use bigrat;print+(1e1000/pop()*pop)=~"/"?N:Y,$/


        When's the last time you used duct tape on a duct? --Larry Wall

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: obfuscated [id://1006283]
Approved by tobyink
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (2)
As of 2014-09-20 18:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (160 votes), past polls