 Perl-Sensitive Sunglasses 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) = @_;
while (\$factorial) {
\$factorial--;
\$answer *= \$factorial unless (\$factorial == 0);
}
}
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 drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2023-10-03 07:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?