Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Pascal's triangle...

by kiat (Vicar)
on Jun 19, 2002 at 08:21 UTC ( #175586=perlquestion: print w/ replies, xml ) Need Help??
kiat has asked for the wisdom of the Perl Monks concerning the following question:

Hi Monks,

I've coded a program to print out Pascal Triangle numbers and would like to find out how the code can be improved or whether there's a more efficient way to write it.

I hope you won't laugh at my code :)

#!/usr/local/bin/perl print "Enter number of rows...\n"; chomp (my $rows = <>); print "You entered $rows for rows\n"; pascal($rows); sub pascal { my ($rows) = @_; print "1\n"; for (my $outer = 1; $outer <= $rows; $outer++) { my $inner = $outer; print "1" unless ($outer == 1); for ($i = 1; $i <= $inner; $i++) { my $denominator = factorial($i)*(factorial($inner-$i)); my $pascalnum = factorial($inner)/$denominator if ($denominator +!= 0); print " $pascalnum" if ($outer > 1); } print "1\n" unless ($outer == 1); } } sub factorial { my ($factorial) = @_; my $answer = $factorial; while ($factorial) { $factorial--; $answer *= $factorial unless ($factorial == 0); } return $answer; }
I look forward to your comments and suggestions on how to improve the code.

Thanks in advance.

kiat

Edit kudra, 2002-06-19 Corrected spelling in title

Comment on Pascal's triangle...
Download Code
Replies are listed 'Best First'.
Re: Pascal triange...
by ton (Friar) on Jun 19, 2002 at 08:46 UTC
    Hey kiat,
    I noticed that your algorithm skips the "1 1" row. I made some changes to fix that bug:
    sub pascal { my ($rows) = @_; print "1\n"; for (my $outer = 1; $outer < $rows; $outer++) { my $inner = $outer; print "1"; for ($i = 1; $i < $inner; $i++) { my $denominator = factorial($i)*(factorial($inner-$i)); my $pascalnum = factorial($inner)/$denominator if ($denominator +!= 0); print " $pascalnum" if ($outer > 1); } print " 1\n"; } }
    I also think that using the Binomial Theorem when printing out an entire Pascal's triangle is inefficient. I would rather add numbers from the previous row, as this is much, much faster for large numbers of rows. So I wrote up some code to do this:
    sub ton_pascal { my $rows = shift; my $last_row = [ ]; my $this_row = [ 1 ]; last unless ($rows > 0); print "1\n"; for (my $i = 1; $i < $rows; ++$i) { $last_row = $this_row; $this_row = [ 1 ]; for (my $j = 1; $j < $i; $j++) { push(@$this_row, $last_row->[$j - 1] + $last_row->[$j]); } push(@$this_row, 1); print join(' ', @$this_row) . "\n"; } }
    I'm using array references instead of arrays for extra speed (when we copy the results of $this_row into $last_row), but the references could be removed without affecting the algorithm.

    Hope this was helpful... I had fun coding up ton_pascal, so thanks for the problem!

    -Ton
    -----
    Be bloody, bold, and resolute; laugh to scorn
    The power of man...

      No need to copy rows. Here's a much smaller function:
      sub pascal { my @row; foreach (1 .. shift) { push @row => 1; $row [$_] += $row [$_ - 1] for reverse 1 .. @row - 2; print "@row\n"; } }

      Abigail

        Here's a variation on the theme. The difference is that this version doesn't change @row using pushes. It's going to be sized right the first time.
        sub pascal { my @row = (0) x $_ [0]; $row [0] = 1; foreach (1 .. shift) { print "@row[0 .. $_ - 1]\n"; $row [$_] += $row [$_ - 1] for reverse 1 .. @row; } }

        Abigail

        Hello! Abigail-II,

        I like your smaller function (it's really elegant) but I don't understand how it works, even though it's only a few lines. Could you explain the parts to me?

        Thanks in anticipation :)

        kiat
      Hello! Ton,

      Thanks for the correction on the double '1' !

      I just ran your code and it works perfectly - it's not only more elegant but also more efficient. It helps me see how the same problem can be solved by looking at it another way. Thanks!!

      kiat
Re: Pascal triange...
by ariels (Curate) on Jun 19, 2002 at 09:09 UTC
    As mentioned above, it's better to use Pascal's recurrence than the binomial formula. See this writeup (tye's).
Re: Pascal's triangle...
by gumby (Scribe) on Jun 19, 2002 at 13:33 UTC
    #!/usr/bin/perl -wl sub pascal { while (s/\d+(?= (\d+))/$&+$1/eg < shift) { s/^/1 /; print; } }
    Which is basically Re: Pascal triange... in essence.
Re: Pascal triange...
by gumby (Scribe) on Jun 19, 2002 at 09:10 UTC
    Using an approximation to Stirling's series:
    use constant PI => 3.141592653589793238; ... sub factorial { my $n = shift; return (sqrt((2*$n + 1/3)*PI)*($n**$n)*exp(-$n)); }
      use constant PI => 3.141592653589793238;
      since you're only calculating pi once, and inlining it, take advantage of the operating system's precision...

      use constant PI => 4 * atan 1, 1; ## or as i prefer # sub PI() { 4 * atan 1, 1 }

      ~Particle *accelerates*

        Yet another way:
        use Math::Complex; use constant PI => pi(); # or just pi();

        jeffa

        L-LL-L--L-LL-L--L-LL-L--
        -R--R-RR-R--R-RR-R--R-RR
        B--B--B--B--B--B--B--B--
        H---H---H---H---H---H---
        (the triplet paradiddle with high-hat)
        
        or in kansas...

        use constant PI => 3;
        ;-P

        ~Particle *accelerates*

        use constant PI => 4 * atan2 1, 1;
        I can recall from memory more than 700 digits of pi ;-)

        BTW, that's the FPU's precision, not the OS's. (On machines that have an FPU, anyway.)

        /me is pedantic sometimes


        We are using here a powerful strategy of synthesis: wishful thinking. -- The Wizard Book

      Ok, it's been communicated that using the entropy function would provide a better approximation to nCr. So here is such a formula:

      Let H(eps) := -eps.log_2(eps)-(1-eps)log_2(1-eps) be a binary entropy function.

      Then binom(n, eps.n) is approximately equal to 2^(n.H(eps)).

      Where eps is short for epsilon.

      Update: Note that this uses the more common Stirling formula which is slightly less accurate as it truncates terms in the series (instead of approximating them like the formula i posted before).

Re: Pascal's triangle...
by YuckFoo (Abbot) on Jun 20, 2002 at 19:59 UTC
    I dug this nugget out of my snippets directory. It's not mine and I don't know who to credit.

    YuckFoo

    #!/usr/bin/perl while((@_=(1,map$_[$_-1]+$_[$_],1..@_))<=$ARGV[0]){print"@_\n"}
Re: Pascal triange...
by Zaxo (Archbishop) on Jun 19, 2002 at 09:16 UTC
    <score>
    sub pascal { my ($rows) = @_ return $rows * ( $rows + 1 ) / 2; }
    </score>

    Update: Nevermind, I missed your intent.

    After Compline,
    Zaxo

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://175586]
Approved by ariels
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (2)
As of 2016-05-02 00:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?