3
$\begingroup$

I have three function computing Fibonacci numbers which return correct answers when directly called with e.g. fib1[10]:

fib1[n_] := Nest[{#[[2]], #[[1]] + #[[2]]} &, {0, 1}, n - 1] // Last

fib2[n_] := Module[{a = 0, b = 1, q},
  If[n == 0, Return[0]]; 
     bits = IntegerDigits[n, 2]; 
     Do[{a, b} = {a^2 + b^2, b (2 a + b)}; 
     If[bits[[q]] != 0, 
        {a, b} = {b, a + b}], 
        {q, 2, Length[bits]}]; 
     Return[b] 
]

fib3[n_] := Round[(((1 + Sqrt[5])/2)^n - ((1 - Sqrt[5])/2)^n)/Sqrt[5]]

However, if I try to execute them like this:

{fib1[n], fib2[n], fib3[n], Fibonacci[n]} /. n -> 10

I expect to obtain

{55, 55, 55, 55}

But in instead, I obtain:

{9, 2, 55, 55}

with a warning : Nest: non negative machine integer expected

(The warning seems to be related to the evaluation of the function fib1)

Why do fib1 and fib2 return an incorrect answer whereas fib3 and Fibonacci returns the right answer in the replacement case?

$\endgroup$
1
  • $\begingroup$ For your fib3 use fib3[n_] := (((1/2)*(1 + Sqrt[5]))^n - (2/(1 + Sqrt[5]))^n*Cos[n*Pi])/ Sqrt[5] then it is valid for all n. You can get this from Fibonacci[n] // FunctionExpand $\endgroup$
    – Bob Hanlon
    Nov 28, 2023 at 19:52

4 Answers 4

4
$\begingroup$

The /. infix form is just syntactic sugar. The expression that gets evaluated here is

ReplaceAll[{fib1[n], fib2[n], fib3[n], Fibonacci[n]}, n -> 10]

There's nothing profound in showing that, but hopefully it makes clear that the arguments must be evaluated before the overall expression can be evaluated. Some functions have various Hold* attributes which allow them to subvert the normal order of evaluation, but ReplaceAll isn't one of those. Thus, the first argument will be fully evaluated before the n->10 rule gets applied. When the rule does eventually get applied, it gets applied to this expression:

{-1 + n, 2, Round[(-((1 - Sqrt[5])/2)^n + ((1 + Sqrt[5])/2)^n)/Sqrt[5]], Fibonacci[n]}

So, to answer your question about how ReplaceAll works, there's nothing special going on here. We're just churning through the evaluation process.

To answer the implied question of how this kind of operation should be done, I would suggest this:

Through[{fib1, fib2, fib3, Fibonacci}[10]]

The concept of "applying several functions to the same argument" has already been thought of and implemented by the Wolfram team, and so you might as well take advantage of it.

$\endgroup$
4
$\begingroup$

fib1 should be limited not to evaluate unless $n$ is an explicit integer number, so let's redefine it as such (in the following I've also used a version with numbered slots and Apply that looks more readable to me):

ClearAll[fib1]
fib1[n_Integer?Positive] := Nest[Apply[{#2, #1 + #2} &], {0, 1}, n - 1] // Last

{fib1[n]} /. n -> 10
(* Out: {55} *)

You should do the same with fib2 as well.

$\endgroup$
2
  • $\begingroup$ The definition should be restricted to positive integers since Nest must be given a nonnegative argument, i.e., fib1[n_Integer?Positive] := ... $\endgroup$
    – Bob Hanlon
    Nov 28, 2023 at 19:59
  • $\begingroup$ @BobHanlon Good point. I added that too. Thank you. $\endgroup$
    – MarcoB
    Nov 28, 2023 at 21:10
3
$\begingroup$

Look at:

fib1[n]

-1 + n

fib1[n] /. n->10

9

And for fib2:

fib2[n]

2

Here the ReplaceAll does nothing.

$\endgroup$
4
  • $\begingroup$ is there a way (i tried with RuleDelayed with no success) to ask Mathematica to evaluate fib etc after the replacement? $\endgroup$
    – youyou
    Nov 28, 2023 at 16:21
  • $\begingroup$ @youyou Yes. See my answer below. $\endgroup$
    – MarcoB
    Nov 28, 2023 at 16:23
  • $\begingroup$ btw I obtain the good behavior by changing fib1[n_] to fib1[n_Integer], but i'd like also to understand how ReplaceAll works $\endgroup$
    – youyou
    Nov 28, 2023 at 16:24
  • $\begingroup$ @youyou I think the part about ReplaceAll is well addressed in Daniel's answer. First, fib1 was evaluated evaluation to return $n-1$; then ReplaceAll operates on that result by replacing $n$ with 10; then 10-1 is evaluated to return 9. $\endgroup$
    – MarcoB
    Nov 28, 2023 at 16:28
0
$\begingroup$

Using Hold and ReleaseHold does the job as well:

Hold[{fib1[n], fib2[n], fib3[n], Fibonacci[n]}] /. n -> 10 // ReleaseHold
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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