3
$\begingroup$

I implemented the factorial function:

fact[0] = 1
fact[x_Integer?Positive ] := x*fact[x - 1];

f[4] yields 24 as expected

I tried a different version of the factorial function using FixedPoint. I added factAlt[1] = 1 to help SameTest (or rather Equal) conclude that the same result has been produced (when reaching factAlt[1] and factAlt[0]).

factAlt[0] = 1
factAlt[1] = 1
factAlt[n_ /; n >= 1] := n*factAlt[n - 1]
FixedPoint[factAlt, 4, SameTest -> Equal]

This version does not seem to terminate.

I am new to FixedPoint in Mathematica (and have some mileage in lambda calculus).

Can you advise on how to implement factorial correctly using FixedPoint?

Could the issue be that when factAlt[1] is reached, SameTest does not access factAlt[1] = 1 (which is listed separately) and thus SameTest given will not conclude that factAlt[1] and factAlt[0] are the same (?).

ETA. I clearly misinterpreted the function of FixedPoint. Accepted Lukas Lang's answer which is closest to the spirit of the question.

$\endgroup$
6
  • 2
    $\begingroup$ Read the documentation for FixedPoint. Or try this: FixedPoint[factAlt, 4, 2]. It keeps applying factAlt to the result, so it just explodes. $\endgroup$
    – lericr
    Aug 8 at 15:19
  • 2
    $\begingroup$ Are you really asking "how to implement factorial correctly using FixedPoint"? Or are you just trying to understand why your FixedPoint expression doesn't terminate? $\endgroup$
    – lericr
    Aug 8 at 15:21
  • $\begingroup$ Yes, clearly I was entirely on the wrong track here. The question is how to implement factorial using FixedPoint. $\endgroup$
    – Michel
    Aug 8 at 15:26
  • 1
    $\begingroup$ Let's say we had fact[n_]:=FixedPoint[fun,n]. Given, say, 4, we're saying that at some point fun[fun[...fun[fun[4]]...]] becomes fixed at 4!. In particular, f[24]==24. But this must be true for every n, so f[n!]==n! in general. But if f[24]==24, then fact[24]==24 and therefore fact[24] =!= 24!. $\endgroup$
    – lericr
    Aug 8 at 15:42
  • 2
    $\begingroup$ Now, there are other ways we could use FixedPoint. Like maybe we use a different structure that keeps track of the level of nesting. E.g. fact[n_]:=First[FixedPoint[fun,{n,n}]] where fun somehow decremented the second element of its argument and continued building the product in its first argument. I haven't worked out the details, but I suspect you could define fun so that it appropriately stayed fixed for {x,0} such that x==n!. $\endgroup$
    – lericr
    Aug 8 at 15:51

4 Answers 4

6
$\begingroup$

FixedPoint is not doing what you think it does: It evaluates the sequence facAlt[4], facAlt[facAlt[4]], etc. This yields $4!=24$, $24!=620448401733239000000000$, etc. which will never reach a fixed point. Unfortunately, I don't see a good way to use FixedPoint to define the factorial.

One way to try and find an explicit FixedPoint is the following:

  1. Instead of relying on Mathematica's evaluation, we implement it ourselves using ReplaceRepeated:

    factAlt[4] //. {factAlt[0] -> 1, factAlt[n_] :> n*factAlt[n - 1]}
    (* 24 *)
    
  2. We can now note that ReplaceRepeated is effectively ReplaceAll with FixedPoint:

    FixedPoint[
     ReplaceAll@{factAlt[0] -> 1, factAlt[n_] :> n*factAlt[n - 1]},
     factAlt[4]
     ]
    (* 24 *)
    
$\endgroup$
6
  • $\begingroup$ Thanks, I rephrased the question. You answer shows where I went wrong. I want to implement the factorial function using the FixedPoint operator (if possible). $\endgroup$
    – Michel
    Aug 8 at 15:28
  • $\begingroup$ @Michel Please don't edit questions like that. It invalidates all the existing answers & comments. Instead, simply mark this question as answered and ask a new one $\endgroup$
    – Lukas Lang
    Aug 8 at 15:46
  • 1
    $\begingroup$ @Michel Also, see my edit for a way to force an explicit FixedPoint into the picture, but it really doesn't gain you anything $\endgroup$
    – Lukas Lang
    Aug 8 at 15:50
  • $\begingroup$ thanks. Appreciate the comments and the solution. I added a comment to the question as I'm interested in a broader interpretation as well. $\endgroup$
    – Michel
    Aug 8 at 16:04
  • 1
    $\begingroup$ @Michel Is there a reason why you are not simply asking a new question? While you now preserved the original content of your question, your "broader question" is so far removed from the original that all answers/comments are worthless in regards to answering it. I am not saying your new question isn't a good question to ask, simply that it doesn't belong inside this question. The goal of Stackexchange is to produce Q&A posts for single, isolated questions, not constantly evolving discussions. $\endgroup$
    – Lukas Lang
    Aug 8 at 16:07
5
$\begingroup$

Here's an attempt:

factStep[{0, _}] := {1, 0};
factStep[{f_, 0}] := {f, 0};
factStep[{f_, n_}] := factStep[{n f, n - 1}];

myFact[n_Integer?NonNegative] := First[FixedPoint[factStep, {n, n - 1}]]
$\endgroup$
1
  • $\begingroup$ Thanks, just noticed your answer. Kept my original vote for Lang as it came close to what I asked originally. $\endgroup$
    – Michel
    Aug 8 at 16:14
4
$\begingroup$
Clear["Global`*"]

fac[n_Integer?Positive] :=
 FixedPoint[{#[[1]] - 1, Times @@ #} &, {n, 1}, 
   SameTest -> (#1[[2]] == #2[[2]] &)][[-1]]

Test:

And @@ Table[fac[n] == n!, {n, 1, 10}]

(* True *)
$\endgroup$
3
$\begingroup$

There is no need for FixedPoint. The definition alone will do what you want:

factAlt[0] = 1
factAlt[1] = 1
factAlt[n_ /; n >= 1] := n*factAlt[n - 1]
factAlt[4]

(* 24 *)
$\endgroup$
1
  • $\begingroup$ I realise this. I just wonder if it can be done. $\endgroup$
    – Michel
    Aug 8 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.