[33133] in Perl-Users-Digest
Perl-Users Digest, Issue: 4411 Volume: 11
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Fri Apr 10 03:09:20 2015
Date: Fri, 10 Apr 2015 00:09:04 -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 Fri, 10 Apr 2015 Volume: 11 Number: 4411
Today's topics:
Re: "Deep Recursion" warning on factorial script. <kaz@kylheku.com>
Re: "Deep Recursion" warning on factorial script. <lionslair@consolidated.net>
Re: "Deep Recursion" warning on factorial script. <lionslair@consolidated.net>
Re: "Deep Recursion" warning on factorial script. <jblack@nospam.com>
Re: "Deep Recursion" warning on factorial script. <jblack@nospam.com>
Re: "Deep Recursion" warning on factorial script. <jurgenex@hotmail.com>
Re: "Deep Recursion" warning on factorial script. <ben.usenet@bsb.me.uk>
Re: "Deep Recursion" warning on factorial script. <rweikusat@mobileactivedefense.com>
Re: "Deep Recursion" warning on factorial script. <bauhaus@futureapps.invalid>
Re: Regex replace line breaks (Seymour J.)
Re: Regex replace line breaks <lionslair@consolidated.net>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Thu, 9 Apr 2015 01:31:15 +0000 (UTC)
From: Kaz Kylheku <kaz@kylheku.com>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <20150408182227.699@kylheku.com>
On 2015-04-08, Jürgen Exner <jurgenex@hotmail.com> wrote:
> Rainer Weikusat <rweikusat@mobileactivedefense.com> wrote:
>>But this doesn't help at all when the usage pattern is not such that
>>older results can be re-used as intermediate results in newer
>>calculations and outside of "beginner's examples of recursive
>>implementation", a factorial should never be calculated in this way.
>
> I disagree.
> A recursive implementation of the factorial function is the most obvious
> way, just mirror its mathematical definition. That makes it easy to
> implement and easy to maintain, saving on developer cost which is the
> most relevant for any project.
> Converting such a trivial tail recursion into a loop is the task of an
> optimizing compiler, not of the programmer. And that has been true for
> at least the past 25 years.
The ordinary recursive definition of factorial is not tail recursive.
fac(0) -> 1
fac(n) -> n * fac(n - 1)
See, the fac(n - 1) call is not in a tail position. It has to return,
so that its result can be multiplied by n, and returned to the caller.
You can make it tail recursive with an accumulator:
rfac(0, a) -> a
rfac(n, a) -> fac(n - 1, n * a)
fac(n) -> rfac(n, 1)
Is that the still the task of an optimizing compiler?
(Could be; I'm undecided myself.)
Anyway, if you want reliable stack free recursion, you don't want an optimizing
compiler; rather you want a compiler which is required by the language
semantics to recognize and implement tail recursion (whether or not it is
an optimizing compiler).
If it's regarded as an optimization, then your program is wrong when
optimization is turned off, which is rather bad for debugging.
------------------------------
Date: Wed, 08 Apr 2015 22:34:08 -0500
From: Martin Eastburn <lionslair@consolidated.net>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <jrmVw.208717$sB1.138569@fx22.iad>
I calculated 1000! back in the micro world days - maybe 76 or 77.
To full precision.
The process or methodology as they say now was to make an array the size
of the answer (a little larger) and store integers within. Then
you are dealing with small numbers and when an element gets larger than
ten, you carry the digit in the array and so forth.
Staying out of floating point that gives you errors in large
calculations and when done only gives you a smaller value. I want to
say that when I got this machine, I generated 10,000!
The first time it took me 11 1/2 hours. I was able to compile the
program and it went down to 3 + hours.
Nice when the printer prints the number out for you when done. I had
a line printer at the time and had tractor paper - 1 full page was there.
But using arrays to process integers is the best way.
Martin
On 4/8/2015 1:54 PM, John Black wrote:
> In article <mg3ko6$or1$1@speranza.aioe.org>, gamo@telecable.es says...
>> Memoize solves the problem mapping each call with its results in
>> memory. It costs some memory, but the gain in speed it's considerable.
>> When it's not used you call the function 100 times for n=100, 99 for
>> n=99 so if you call it for (1..100) it's around 5050 calls, dropped
>> to just 100 with memoize.
>>
>
> Wow, thanks.
>
> John Black
>
------------------------------
Date: Wed, 08 Apr 2015 22:38:53 -0500
From: Martin Eastburn <lionslair@consolidated.net>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <MvmVw.166629$Ek3.148781@fx13.iad>
found my numbers -
Factorial 10k to integers.
Pi 5000 and 10000 full array of digits.
Martin
On 4/8/2015 2:52 PM, Rainer Weikusat wrote:
> gamo <gamo@telecable.es> writes:
>> El 08/04/15 a las 21:23, Rainer Weikusat escribió:
>>> But this doesn't help at all when the usage pattern is not such that
>>> older results can be re-used as intermediate results in newer
>>> calculations and outside of "beginner's examples of recursive
>>> implementation", a factorial should never be calculated in this way.
>>
>> Well I have calculated up to factorial(1000) with no problems at all.
>>
>> real 0m2.978s
>> user 0m0.439s
>> sys 0m0.012s
>
> [rw@doppelsaurus]~#time perl -Mbigint -e '$s = 1; $s *= $_ for 2 .. 1000; print $s' >/dev/null
>
> real 0m0.069s
> user 0m0.072s
> sys 0m0.000s
>
------------------------------
Date: Wed, 8 Apr 2015 22:41:12 -0500
From: John Black <jblack@nospam.com>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <MPG.2f8fb0d52c40b1fe989821@news.eternal-september.org>
In article <mg41bh$t9u$1@news.grnet.gr>, gravitalsun@hotmail.foo says...
>
> On 8/4/2015 4:08 pµ, Robbie Hatley wrote:
> >
> > I cooked-up and ran the following script today and it worked fine,
>
> make a favor to you computer and yourself and never use recursion when
> you can do it with a flat iterator like a for
I'm sure Robbie knows that just as I doubt he actually needed a factorial sub at the moment.
He seems to be experimenting with Perl to better understand its capabilities and limits.
I'm curious myself, how deep would you feel comfortable going with in recursion? Hundreds
obviously. Thousands? More?
In my programming, the most natural uses I've found for recursion was when traversing a
hierarchy (in VHDL for example). Like any language, a top level calls modules, which call
other modules and so on. Recursion is a natural way to walk the hierarchy. But I was never
worried about blowing through the stack because while there is no real limit on how deep the
hierarchy could go, no actual design would go deeper than a dozen or so levels.
John Black
------------------------------
Date: Wed, 8 Apr 2015 22:47:18 -0500
From: John Black <jblack@nospam.com>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <MPG.2f8fb24666787023989822@news.eternal-september.org>
In article <mg4082$mlo$1@speranza.aioe.org>, gamo@telecable.es says...
> Well I have calculated up to factorial(1000) with no problems at all.
This example has been an eye opener for how big integers can actually be with BIGINT.
Impressive...
John Black
------------------------------
Date: Thu, 09 Apr 2015 00:17:09 -0700
From: Jürgen Exner <jurgenex@hotmail.com>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <qp9ciadnn7pqago00trqrjklievpbmhrf4@4ax.com>
Kaz Kylheku <kaz@kylheku.com> wrote:
>On 2015-04-08, Jürgen Exner <jurgenex@hotmail.com> wrote:
>> Rainer Weikusat <rweikusat@mobileactivedefense.com> wrote:
>>>But this doesn't help at all when the usage pattern is not such that
>>>older results can be re-used as intermediate results in newer
>>>calculations and outside of "beginner's examples of recursive
>>>implementation", a factorial should never be calculated in this way.
>>
>> I disagree.
>> A recursive implementation of the factorial function is the most obvious
>> way, just mirror its mathematical definition. That makes it easy to
>> implement and easy to maintain, saving on developer cost which is the
>> most relevant for any project.
>> Converting such a trivial tail recursion into a loop is the task of an
>> optimizing compiler, not of the programmer. And that has been true for
>> at least the past 25 years.
>
>The ordinary recursive definition of factorial is not tail recursive.
>
> fac(0) -> 1
> fac(n) -> n * fac(n - 1)
You are right, my mistake, sorry
Pulling foot out of mouth
jue
------------------------------
Date: Thu, 09 Apr 2015 11:10:42 +0100
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <87oamx393x.fsf@bsb.me.uk>
Kaz Kylheku <kaz@kylheku.com> writes:
> On 2015-04-08, Jürgen Exner <jurgenex@hotmail.com> wrote:
>> Rainer Weikusat <rweikusat@mobileactivedefense.com> wrote:
>>>But this doesn't help at all when the usage pattern is not such that
>>>older results can be re-used as intermediate results in newer
>>>calculations and outside of "beginner's examples of recursive
>>>implementation", a factorial should never be calculated in this way.
>>
>> I disagree.
>> A recursive implementation of the factorial function is the most obvious
>> way, just mirror its mathematical definition. That makes it easy to
>> implement and easy to maintain, saving on developer cost which is the
>> most relevant for any project.
>> Converting such a trivial tail recursion into a loop is the task of an
>> optimizing compiler, not of the programmer. And that has been true for
>> at least the past 25 years.
>
> The ordinary recursive definition of factorial is not tail recursive.
>
> fac(0) -> 1
> fac(n) -> n * fac(n - 1)
>
> See, the fac(n - 1) call is not in a tail position. It has to return,
> so that its result can be multiplied by n, and returned to the caller.
>
> You can make it tail recursive with an accumulator:
>
> rfac(0, a) -> a
> rfac(n, a) -> fac(n - 1, n * a)
>
> fac(n) -> rfac(n, 1)
>
> Is that the still the task of an optimizing compiler?
> (Could be; I'm undecided myself.)
Even in the quasi-tail position, it is one the compilers are happy to
undertake. Given:
unsigned f(unsigned n) { return n == 0 ? 1 : n * f(n - 1); }
gcc -O2 produces (edited for clarity):
f: testl %edi, %edi
movl $1, %eax
je .L4
.L3:
imull %edi, %eax
subl $1, %edi
jne .L3
rep ret
.L4:
rep ret
> Anyway, if you want reliable stack free recursion, you don't want an optimizing
> compiler; rather you want a compiler which is required by the language
> semantics to recognize and implement tail recursion (whether or not it is
> an optimizing compiler).
Yup. It's all very well to get such an optimisation, but if you can't
rely on it you can't use that style.
<snip>
--
Ben.
------------------------------
Date: Thu, 09 Apr 2015 12:42:37 +0100
From: Rainer Weikusat <rweikusat@mobileactivedefense.com>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <87d23dplxu.fsf@doppelsaurus.mobileactivedefense.com>
Jürgen Exner <jurgenex@hotmail.com> writes:
> Rainer Weikusat <rweikusat@mobileactivedefense.com> wrote:
>>But this doesn't help at all when the usage pattern is not such that
>>older results can be re-used as intermediate results in newer
>>calculations and outside of "beginner's examples of recursive
>>implementation", a factorial should never be calculated in this way.
>
> I disagree.
> A recursive implementation of the factorial function is the most obvious
> way, just mirror its mathematical definition. That makes it easy to
> implement and easy to maintain, saving on developer cost which is the
> most relevant for any project.
Provided the developer is much more versed in the very limited language
called 'mathematics'[*] and less familiar with the properties/
possibilities of the device he is trying to control, this may be
regarded as true. If this isn't the case, the recursive definition is
just a queer workaround for the problem that straight-forward loops with
changing state variables can't be expressed in 'math' and one people who
have no difficulties dealing with the latter find difficult to
understand.
5! is defined as 1 * 2 * 3 * 5 and n! as 1 * 2 ... * n. This can be
written down in any imperative programming language almost as is
sub sillyfac2
{
my $r;
$r = 1;
$r *= $_ for 2 .. $_[0];
$r;
}
while it takes a certain amount of ingenuity to come up with the
'backward' recursive definition.
[*] This isn't even true as a mathematical operator expressing a
multiplication from n = 1 to some upper bound actually exists, ie,
there's a straight-forward 'iterative' definition of a factorial in
'math', too.
BTW, something else which ought to be mentioned here: In case one
happens to use code repeatedly performing some 'idempotent' calculation
and this ends up taking so much time that it becomes a performance
problem, the sensible way to deal with this is to calculate all the
values offline ones and put them into a table the program can then use
(and reuse!) at runtime. That's the practical lession behind 'memoize'
(which is conceptually interesting because of the features it employs,
eg, the symbol table manipulations which cause the existing code to call
the intermediate function transparently, but not something suitable 'for
production use').
------------------------------
Date: Thu, 09 Apr 2015 15:20:50 +0200
From: "G.B." <bauhaus@futureapps.invalid>
Subject: Re: "Deep Recursion" warning on factorial script.
Message-Id: <mg5u9o$cob$1@dont-email.me>
On 09.04.15 13:42, Rainer Weikusat wrote:
> Jürgen Exner <jurgenex@hotmail.com> writes:
>> Rainer Weikusat <rweikusat@mobileactivedefense.com> wrote:
>>> But this doesn't help at all when the usage pattern is not such that
>>> older results can be re-used as intermediate results in newer
>>> calculations and outside of "beginner's examples of recursive
>>> implementation", a factorial should never be calculated in this way.
>>
>> I disagree.
>> A recursive implementation of the factorial function is the most obvious
>> way, just mirror its mathematical definition. That makes it easy to
>> implement and easy to maintain, saving on developer cost which is the
>> most relevant for any project.
>
> Provided the developer is much more versed in the very limited language
> called 'mathematics'[*] and less familiar with the properties/
> possibilities of the device he is trying to control, this may be
> regarded as true.
Mathematicians never talk publicly about their private
parts (operations). Knuth is an exception.
------------------------------
Date: Wed, 08 Apr 2015 19:08:21 -0400
From: Shmuel (Seymour J.) Metz <spamtrap@library.lspace.org.invalid>
Subject: Re: Regex replace line breaks
Message-Id: <5525b4e5$7$fuzhry+tra$mr2ice@news.patriot.net>
In <mg0416$19e$1@speranza.aioe.org>, on 04/07/2015
at 10:20 AM, gamo <gamo@telecable.es> said:
>As far as you must find a non-ASCII compatible computer,
Or a computer whose software can handle ASCII but normally uses a
different character set, e.g., EBCDIC. Of course, the use of EBCDIC
would imply an older Perl, e.g., 5.8.7.
--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>
Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spamtrap@library.lspace.org
------------------------------
Date: Wed, 08 Apr 2015 22:21:46 -0500
From: Martin Eastburn <lionslair@consolidated.net>
Subject: Re: Regex replace line breaks
Message-Id: <JfmVw.240687$Op6.213226@fx16.iad>
TTY's have been out of normal use for quite a while. CR, CR, LF
allowed the carriage to return from a long line, index and start
printing. Without the double CR's the LF would be mid-line and
printing would start in a sloppy margin and looks bad.
EBi was used in IBM machines and hobbyist ran into them with translators.
Martin - former founder member of the North Texas Computer Association
back in the middle 70's.
The Pacific group was cranking out code and hardware, as we were.
A member and his wife, both notable in Mainframe level programming
developed a method to write digital on audio tape. It was later
improved and he made it a standard at Kansas city. The old KCS.
Martin
On 4/8/2015 4:54 PM, Shmuel (Seymour J.) Metz wrote:
> In <3NKdnfwD5t1XPb3InZ2dnUVZ5sqdnZ2d@giganews.com>, on 04/04/2015
> at 07:41 PM, "Robert Crandal" <noreply2me@yahoo.com> said:
>
>> My goal is to replace all line feed (LF) or carriage return (CR)
>> characters with a single CR character.
>
> Not single LF?
>
>> The problem is, I am reading text files from different sources,
>
> How different? Depending on the answe, you may also have to deal with
> new line characters.
>
>> This seems to be a job for regular expressions, especially since
>> there are different ways to represent line breaks. For my purposes,
>> assume that a single line break may be any of these: CR, CF LF,
>
> LF CR?
>
>> or CR CR LF.
>
> That's questioable at best.
>
>> How can I single-space my string with regular expressions?
>
> Does this do what you want, assuming that $_ is set?
>
> s/[\x0d\x0a]+/\x0d/g;
>
------------------------------
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 4411
***************************************
