Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
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:

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";

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
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 scrutinizing the Monastery: (10)
As of 2014-10-02 07:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (49 votes), past polls