pc88mxer has asked for the wisdom of the Perl Monks concerning the following question:

Recently while at my local bookstore I found myself browsing through this book. and one of the exercises that caught my eye was to write a program to compute this sum:
30 29 1 ---- + ---- + ... + ---- 1 2 30
I immediately thought it would be interesting to compute this exactly as a fraction and also to generalize the problem by replacing 30 with an arbitrary integer n. I knew perl had support for arbitrary precision integers, and I was curious to find out if the numerators or denominators formed any recognizable pattern.

So when I got home I consulted the documentation for bigrat, and naively coded up this loop:

use strict; use warnings; use bigrat; for my $n (1..30) { my $s = 0; for my $k (1..$n-1) { $s += $k / ($n-$k); } print "n = $n, s = $s\n"; }
Needless to say, it didn't work as I expected - I got output like this:
n = 1, sum = 0 n = 2, sum = 1 n = 3, sum = 2.5 n = 4, sum = 4.333333333333333
I expected to get 5/2 for n = 3 and 13/3 for n = 4, etc. After reconsulting the docs and some more experimentation, I finally came up with this solution:
for my $n (1..30) { my $s = 0; for my $k (1..$n-1) { $s += 1/1 * $k / ($n-$k); } print "n = $n, s = $s\n"; }
which gave what I wanted:
n = 1, sum = 0 n = 2, sum = 1 n = 3, sum = 5/2 n = 4, sum = 13/3
Having tackled that problem, I went on to extract the numerator and denominator sequences so I could plug them into The On-Line Encyclopedia of Integer Sequences. Again, my naive approach was to simply call ->numerator and ->denominator on each sum:
for my $n (1..30) { ... push(@nums, $s->numerator); push(@denoms, $s->denominator); }
Alas, I ran into problems on the very first term:
Can't locate object method "numerator" via package "Math::BigInt" at . +/frac line ...
Indeed, this program illustrates the problem:
use bigrat; my $x = 1; print $x->numerator, "\n";
So I guess my questions are:
  1. Why didn't bigrat figure out that the expression $k/($n-$k) should produce a bigrat and not a floating point number?
  2. Why can't I call numerator and denominator on a rational that's actually an integer? Should those methods should be added to Math::BigInt or somehow enabled when bigrat is used?
I'm using 5.8.8 if that's of any consequence.

Update 1: fixed typo with expected results.

Replies are listed 'Best First'.
Re: issues using bigrat
by ikegami (Patriarch) on May 11, 2008 at 18:04 UTC

    Why didn't bigrat figure out that the expression $k/($n-$k) should produce a bigrat and not a floating point number?

    The only things that get converted to big num objects are constants. Everything else is done through operator overload, which only affects operators whose operands are big num objects.

    However, the range operator cannot be overloaded, so using a bigXXX as an operand to a range operator collapses it into a plain integer.

    use bigrat; $i = 2; print("i: ", ref($i), "\n"); ($j) = ($i .. $i); print("j: ", ref($j), "\n");
    i: Math::BigInt j:

    Since you converted the constants from big num objects into plain numbers, you needed to convert them back to big num objects to get the desired output.

    You can continue to explicitly convert the loop counters to big nums (using "1 *", "1/1 *" is overkill), or you can use a C-style loop instead of using the range operator.

    use bigrat; for (my $n=1; $n<=30; ++$n) { my $s = 0; for (my $k=1; $k<$n; ++$k) { $s += $k / ($n-$k); } print "n = $n, s = $s\n"; }

    Why can't I call numerator and denominator on a rational that's actually an integer?

    You can't call a Math::BigRat method on something that's not a Math::BigRat. Nowhere does bigrat say it produces Math::BigRat objects. It actually says "Integer and floating-point constants are created as proper BigInts or BigFloats". If you want a Math::BigRat object, you'll need to create it.

    $x = Math::BigRat->new($x);
Re: issues using bigrat
by perl-diddler (Chaplain) on May 11, 2008 at 21:03 UTC
    Works for me...?

    I read the problem description you gave (summing the series), and wrote a "1-liner" (iterative 'bashing') which seems to work exactly as you describe. I am using the ".." operator just as you are, so I don't think you need to use the "C" style "for" loop. Not yet sure why things aren't working the same for you (am using 5.8.8, here, as well). Original "1-liner format:"

    perl -e 'use bigrat;for my $n (1..5){my $s=0;for my $i (1..$n) {$s+=($ +n+1-$i)/$i} push @nums, $s->numerator; push @dens, $s->denominator; $ +num=$s->numerator; $den=$s->denominator; print "n = $n, s = $s, num=$ +num, den=$den\n";} print "nums=",(join ", ",@nums), "\n"; print "dens +=",(join ", ",@dens),"\n";'
    Or pretty-i-fied:
    #!/usr/bin/perl -w use bigrat; for my $n (1 .. 5) { my $s = 0; for my $i (1 .. $n) {$s += ($n + 1 - $i) / $i} push @nums, $s->numerator; push @dens, $s->denominator; $num = $s->numerator; $den = $s->denominator; print "n = $n, s = $s, num=$num, den=$den\n"; } print "nums=", (join ", ", @nums), "\n"; print "dens=", (join ", ", @dens), "\n";
    Did you convert some 'bignum' type to an integer somewhere? I'll have to study your code more closely to find out where it's breaking, but thought I'd at least offer something that seemed to do what you wanted in the way you wanted...:-)
    -Linda

      You changed
      $s += $k / ($n-$k);
      to
      $s += ($n + 1 - $i) / $i;

      The "+ 1" has the same effect as the "1 *" the OP used in his fixed version. Just like him, your $n and $i are plain integers, not big ints.

        Yeah, you might think so, but if my code has the same problem, why does it not suffer the same problem calling numerator or denominator on "$s"?

        I mean the output is, I believe, what would expect if it was working correctly:

        n = 1, s = 1, num=1, den=1 n = 2, s = 5/2, num=5, den=2 n = 3, s = 13/3, num=13, den=3 n = 4, s = 77/12, num=77, den=12 n = 5, s = 87/10, num=87, den=10 nums=1, 5, 13, 77, 87 dens=1, 2, 3, 12, 10
        Hmmm...not sure but it may that the original example that "worked" didn't really produce the right output or wasn't doing the right computation.
Re: issues using bigrat
by perl-diddler (Chaplain) on May 11, 2008 at 21:38 UTC
    I don't understand something in your logic/description. It seems to be a minor "typo" type thing, but I'm not sure which statement is correct:

    First you said:

    "I expected to get 5/2 for n = 2 and 13/3 for n = 3, etc."

    But then you said that:

    n = 2, sum = 1 n = 3, sum = 5/2
    was correct. Did you want "n=2 to equal 1" or "n=2 to equal 5/2"? (though I can't see how this would mangle the output like it does. I haven't quite figured that part out...*grumble*...:-).

    But I sorta mentally ran the 1st loop for n=1. That starts with the inner loop being

    "for my $k (1 .. 0) {"
    which isn't horrible by itself, but certainly isn't what I'd expect for a 1st iteration of your series:
    "Sumof(Num/Denom) for Num=(1..n) and Denom='(n..1)'[=>'n+1-Num']"
Re: issues using bigrat
by perl-diddler (Chaplain) on May 11, 2008 at 21:57 UTC
    PC88mxer -- could you fix your code to correspond with the original formula? I think, if you do, the problem 'goes away', and that it's when "numerator" or "denominator" are called with "$s==0" that the unknown methods pop out...

    At least that's my best guess at this point...:-)

    Linda

      could you fix your code to correspond with the original formula?
      There really wasn't an original formula - I just created one. In fact, that probably was the point of the original exercise. I realize that I'm really computing the sum for n-1, but sometimes you discover something interesting when you try something different.
        Sorry I was unclear. By "original formula", I mean the formula that generated the series you gave as an example of what you wanted to generate. I.e.:
        (Series 1) 30 29 1 ---- + ---- + ... + ---- 1 2 30
        From that, you said that you wanted to be able to compute the "general case for 'n', where n is the number of items in a series that looks similar to the example above I.e:
        (Formula for Series 1) ( (n+1-k) ) Sum ( ------- ) for k = (1..n); ( k )
        If you were computing the sum for 'n-1', wouldn't you want the sum:
        (Series 2) 29 28 1 ---- + ---- + ... + ---- 1 2 29
        That's not what your code generates, either. That's what I meant by 'fixing' the code -- making it consistent with which-ever series you wanted (top one for 'n' or bottom one for 'n-1'). But the program you implemented doesn't generate either series because it doesn't implement the formula to generate that series but instead, for n=30, generates the series:
        (Series 3) 1 2 30 ---- + ---- + ... + ---- 29 28 0
        That series is backwards from your original example, the code always divides by zero at the end the inner "for-loop", and skips the inner for-loop entirely, on the first iteration through the outer for-loop, making the sum, "$s", equal to "0". So the first time through the outer loop, you try to call $s->numerator & $s->denominator, but you've called them when $s=0 and no calculations have been done, thus the exception.

        Where you wanting to discover something different? :-)