 We don't bite newbies here... much 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

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 exploiting the Monastery: (5)
As of 2019-07-23 05:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
If you were the first to set foot on the Moon, what would be your epigram?

Results (24 votes). Check out past polls.

Notices?