Alex Mizrahi wrote:

> than version you've wrote in CL. i would write it like this:
>
> (defun factorial (n)
> (loop with p = 1
> for i from 1 to n
> do (setf p (* p i))
> finally (return p)))
>
> IMHO that's cleaner. or if i absolutely must use recursion:

(define (factorial n)
(if (zero? n) 1 (* n (factorial (- n 1)))))

(factorial 5)
===>
120

(factorial 20)
===>
2432902008176640000

Robert L. <No_spamming@noWhere_7073.org> wrote:

> [terrible non-TR factorial function]
>

Troll is not only troll, he is stupid troll.

--
the small snake

On 2022-02-20, Zyni Moë <no_email@invalid.invalid> wrote:
> Robert L. <No_spamming@noWhere_7073.org> wrote:
>
>> [terrible non-TR factorial function]
>>
>
> Troll is not only troll, he is stupid troll.

Wow, that person is still posting? How old are they now.

I remember when they posted some Scheme code that was doing something
like:

(some-function (inc var) (inc var) (inc var))

Where inc is an increment macro, not realizing that Scheme has
unspecified order of argument evaluation, similarly to C.

The macro didn't take care of multiple evaluation, either, I think.

It's worth avoiding stack-consuming recursion in factorial because it
can conceivably produce a bignum value that itself fits into memory, yet
requires so many factors that the stack is blown. If the number of
factors, and thus stack frames, were like logarithmic in the size of
that number, it would be a different story.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

On 2/20/2022 10:17 AM, Kaz Kylheku wrote:
> On 2022-02-20, Zyni Moë <no_email@invalid.invalid> wrote:
>> Robert L. <No_spamming@noWhere_7073.org> wrote:
>>
>>> [terrible non-TR factorial function]
>>>
>>
>> Troll is not only troll, he is stupid troll.
>
> Wow, that person is still posting? How old are they now.
>
> I remember when they posted some Scheme code that was doing something
> like:
>
> (some-function (inc var) (inc var) (inc var))
>
> Where inc is an increment macro, not realizing that Scheme has
> unspecified order of argument evaluation, similarly to C.
>
> The macro didn't take care of multiple evaluation, either, I think.
>
> It's worth avoiding stack-consuming recursion in factorial because it
> can conceivably produce a bignum value that itself fits into memory, yet
> requires so many factors that the stack is blown. If the number of
> factors, and thus stack frames, were like logarithmic in the size of
> that number, it would be a different story.
The memory allocation for a number is, roughly, proportional to the
logarithm of the SIZE (i.e., the value) of the number; It is linearly
proportional to the LENGTH (i.e., number of digits in a base > 1) of the
number representation. This is a quibble as is the fact that many
implementations put big numbers in the heap. not the stack. In any
event, the/your point is that that factorial can produce lots of
computational garbage. It's a great function to introduce recursion as a
pedagogical tool. If you are doing serious combinatorial computations,
you probably need a junior Knuth to hack up the support tool, e.g., the
one who can write the a decent number package in the first place.
--
Jeff Barnett

On 2022-02-20, Jeff Barnett <jbb@notatt.com> wrote:
> On 2/20/2022 10:17 AM, Kaz Kylheku wrote:
>> On 2022-02-20, Zyni Moë <no_email@invalid.invalid> wrote:
>>> Robert L. <No_spamming@noWhere_7073.org> wrote:
>>>
>>>> [terrible non-TR factorial function]
>>>>
>>>
>>> Troll is not only troll, he is stupid troll.
>>
>> Wow, that person is still posting? How old are they now.
>>
>> I remember when they posted some Scheme code that was doing something
>> like:
>>
>> (some-function (inc var) (inc var) (inc var))
>>
>> Where inc is an increment macro, not realizing that Scheme has
>> unspecified order of argument evaluation, similarly to C.
>>
>> The macro didn't take care of multiple evaluation, either, I think.
>>
>> It's worth avoiding stack-consuming recursion in factorial because it
>> can conceivably produce a bignum value that itself fits into memory, yet
>> requires so many factors that the stack is blown. If the number of
>> factors, and thus stack frames, were like logarithmic in the size of
>> that number, it would be a different story.
> The memory allocation for a number is, roughly, proportional to the
> logarithm of the SIZE (i.e., the value) of the number; It is linearly
> proportional to the LENGTH (i.e., number of digits in a base > 1) of the

I'm a C programmer; size is length plus 1 (for null termination). :)

> number representation. This is a quibble as is the fact that many
> implementations put big numbers in the heap. not the stack. In any
> event, the/your point is that that factorial can produce lots of
> computational garbage.

I don't mean that at all. I mean that, for instance, (fac 100)
produces (O 100) decimal digits. (Lisp version of big-Oh notation.)

(expt 100 n) produces a (+ (* 2 n) 1)
digit decimal number; for (expt 100 100) that is 201.

(expt n n) has a number of digits that is an upper bound
on the number of digits of (fac n), and that is proportional to n.
The number of recursive frames of (fac n) is also proprtional to n.

The value of the argument to fac approximately specifies how much
storage the resulting number will require, and how much stack storage
the ordinary recursion will require.

That's a Kinda Bad Thing, since available stack space is often smaller
than available heap.

> pedagogical tool. If you are doing serious combinatorial computations,
> you probably need a junior Knuth to hack up the support tool, e.g., the
> one who can write the a decent number package in the first place.

Doing it yourself, without being a complete idiot, will go a long way,
too, though! Particularly if you "know what you don't know" and research
it.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Kaz Kylheku <480-992-1380@kylheku.com> wrote:

>
> Wow, that person is still posting? How old are they now.

I don't know if they are the same one as ?WJ? but they smell like they are.

--
the small snake