 Don't ask to ask, just ask PerlMonks

Pascal's triangle...

by kiat (Vicar)
 on Jun 19, 2002 at 08:21 UTC 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.

kiat

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

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 \$_ ; \$row  = 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*

Or, to get rid of that nasty "4":
sub PI () { atan2 0, -1 }
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---

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){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

Re: Pascal's triangle...
by Anonymous Monk on Dec 04, 2019 at 04:19 UTC
One more approach:
sub line { my @a1 = @_; my @b; push @b, " 1"; push @b, \$a1[\$_] + \$a1[ \$_ - 1 ] foreach ( 1 .. \$#a1 + 1 ); return @b; } my @b = qw(1 1); my \$s = 100; print " " x (\$s), " 1\n"; foreach ( 2 .. shift ) { my \$l = join " ", @b; print " " x ( \$s - ( length \$l ) / 2 ), "\$l\n"; @b = line(@b); shift @b; }

Create A New User
Domain Nodelet?
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 lurking in the Monastery: (6)
As of 2022-01-20 16:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (57 votes). Check out past polls.

Notices?