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...  [reply] [d/l] [select] 

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  [reply] [d/l] 

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
 [reply] [d/l] [select] 


Hello! AbigailII,
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
 [reply] 


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
 [reply] 
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).
 [reply] 
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.  [reply] [d/l] 
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));
}
 [reply] [d/l] 

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*
 [reply] [d/l] [select] 

Or, to get rid of that nasty "4":
sub PI () { atan2 0, 1 }
 Randal L. Schwartz, Perl hacker  [reply] [d/l] 

use Math::Complex;
use constant PI => pi();
# or just
pi();
jeffa
LLLLLLLLLLLL
RRRRRRRRRRRR
BBBBBBBB
HHHHHH
(the triplet paradiddle with highhat)
 [reply] [d/l] 

use constant PI => 3;
;P
~Particle *accelerates*
 [reply] [d/l] [select] 


use constant PI => 4 * atan2 1, 1;
I can recall from memory more than 700 digits of pi ;)  [reply] [d/l] 

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
 [reply] 

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)(1eps)log_2(1eps) 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).
 [reply] 
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"}
 [reply] [d/l] 
Re: Pascal triange...
by Zaxo (Archbishop) on Jun 19, 2002 at 09:16 UTC

sub pascal {
my ($rows) = @_
return $rows * ( $rows + 1 ) / 2;
}
</score>Update: Nevermind, I missed your intent.
After Compline, Zaxo  [reply] [d/l] 