[33140] in Perl-Users-Digest
Perl-Users Digest, Issue: 4418 Volume: 11
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Mon Apr 20 03:09:18 2015
Date: Mon, 20 Apr 2015 00:09:02 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Mon, 20 Apr 2015 Volume: 11 Number: 4418
Today's topics:
Re: Fast Factorial Script: 10000! in 1.5sec. <rweikusat@mobileactivedefense.com>
Re: format file <rweikusat@mobileactivedefense.com>
Re: Uninitialized value, but it shouldn't be <whynot@pozharski.name>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Sun, 19 Apr 2015 15:23:39 +0100
From: Rainer Weikusat <rweikusat@mobileactivedefense.com>
Subject: Re: Fast Factorial Script: 10000! in 1.5sec.
Message-Id: <87zj642o44.fsf@doppelsaurus.mobileactivedefense.com>
Rainer Weikusat <rweikusat@mobileactivedefense.com> writes:
> Robbie Hatley <see.my.sig@for.my.address> writes:
>> Speed race: my script computes 10000! in 1.5sec. (No recursion
>> this time.) Can you make a script that's faster? :-)
>
> [...]
>
>> I wonder how BigInt's "bfac()" achieves such speed?
>> I tried iterative multiplication ($f *= $_ for 1..$x)
>
> http://blogten.blogspot.co.uk/2007/01/calculating-n.html?showComment=1169930940000#c1563328965910785064
>
> The Calc.pm source code also provides an instructive example why
> 'comments' are a double-edged sword,
>
> # Calculate (k-j) * (k-j+1) ... k .. (k+j-1) * (k + j)
> # See http://blogten.blogspot.com/2007/01/calculating-n.html
> # The above series can be expressed as factors:
> # k * k - (j - i) * 2
Since I was curious, I spent some time thinking about how to implement
this because I wanted to know if it's actually faster than just
multiplying the numbers. The first thing to do here is to simplify this
description somewhat, ie, reduce the amount of single-letter variables.
Let n be some odd number. Considering that n! is defined as
1 * 2 ... * n,
it's possible to select a number m (for 'middle') which is just in the
middle of the sequence of factors above. This m can be calculated as
n / 2 + 1
(provided / is an integer division). The sequence of factors can then be
rewritten as
1 * 2 ... * (m - 1) * m * (m + 1) ... * n
'We' can now perform a cleavage and start eating the onion from the
inside. The above can be rewritten as
m * (m + 1) * (m - 1) * (m + 2) * (m - 2) ... * (m - m + 1) * (m + m - 1)
after having thus gotten rid of the irritating j, it's immediately clear
that there's a sequence of pairs
(m + k) * (m - k)
with each to these pairs being equal to
m ** 2 - k ** 2
Since m ** 2 appears in all of these terms, it only needs to be
calculated once. What remains is calculating a sequence of squares 1 **
2, 2 ** 2, 3 ** 3 up to (m - 1) ** 2. As noted in the orginal text, k **
2 is equal to the sum of the first k odd numbers. This leads to the
following implementation:
----------
sub odd_fac
{
my ($accu, $left, $right, $odd, $cur);
$accu = int($_[0] / 2) + 1;
$left = $accu * $accu;
$right = $odd = 1;
while ($cur = $left - $right) {
$accu *= $cur;
$odd += 2;
$right += $odd;
}
return $accu;
}
----------
Conveniently the difference of the left and right squares will be zero
once the caluclation is done, so this can be used as termination
condition for the loop.
This scheme can be extended to the even n as follows:
----------
sub fac
{
$_[0] & 1 ? odd_fac($_[0]) : $_[0] * odd_fac($_[0] - 1);
}
----------
ie, if n is even, calculate (n - 1)! and multiply that by n. As I
expected, the odd_fac algorithm is much slower than just multiplying
all of the factors if 'native operations' are being used. However, when
using the bigint module and suitably large numbers, it is significantly
faster.
------------------------------
Date: Sun, 19 Apr 2015 14:41:49 +0100
From: Rainer Weikusat <rweikusat@mobileactivedefense.com>
Subject: Re: format file
Message-Id: <874moc44ma.fsf@doppelsaurus.mobileactivedefense.com>
Jim Gibson <JimSGibson@gmail.com> writes:
> Rainer Weikusat <rweikusat@mobileactivedefense.com> wrote:
>
>> Jim Gibson <JimSGibson@gmail.com> writes:
>> > In article <e6d6d6c7-f173-463b-8e4b-955ebd5e1553@googlegroups.com>,
>> > <lancerset@gmail.com> wrote:
>> >> this is works perfectly. One more question. Sorry to be annoying. i'm
>> >> opening the end result in excel. Is there a way in this script that
>> >> the entries would be considered 1 column
>> >
>> > You can use Perl to write Excel spreadsheets directly. Use the
>> > Excel::Writer::XLSX. The module is a little complex, but the
>> > documentation is excellent.
>>
>> That's a serious overkill for such a simple task: Just do away with all
>> of the fancy text formatting and write a comma-separated ('CSV') file
>> Excel can then import.
>
> Well, I disagree. It only takes a few statements to create a simple
> Excel spreadsheet file. Once you have the basics down, you can start
> adding niceties such as text alignment, bolding, italics, etc.
I didn't claim that the 'simple solution for the simple task' would be
adequate for any much more complicated task you're capable of inventing.
Considering the Excel can also import HTML, it would be an interesting
question to which degree the desire of someone who is weded to Excel as
table formatting engine cannot still be satisfied by generating input
files in some other format ...
NB: I don't know this and I probably won't ever find this out. People
who want to import data from a database into Excel (and vice versa)
usually ask for CSV files, hence, I have reason to believe that they're
generally suitable for this task.
------------------------------
Date: Sun, 19 Apr 2015 09:48:27 +0300
From: Eric Pozharski <whynot@pozharski.name>
Subject: Re: Uninitialized value, but it shouldn't be
Message-Id: <slrnmj6jtr.3qn.whynot@orphan.zombinet>
with <mgulok$fnv$1@speranza.aioe.org> gamo wrote:
*CUT*
Thanks, now I feel much better.
--
Torvalds' goal for Linux is very simple: World Domination
Stallman's goal for GNU is even simpler: Freedom
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
Back issues are available via anonymous ftp from
ftp://cil-www.oce.orst.edu/pub/perl/old-digests.
#For other requests pertaining to the digest, send mail to
#perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
#sending perl questions to the -request address, I don't have time to
#answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V11 Issue 4418
***************************************
