Why NestWhile?
- To: mathgroup at smc.vnet.net
- Subject: [mg26914] Why NestWhile?
- From: F.H.Simons at tue.nl
- Date: Fri, 26 Jan 2001 23:29:54 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Finding the number of factors 2 of a positive integer is one of my favourite
examples in courses in Mathematica. The recursive solution is very elegant.
frec[n_] := If[EvenQ[n], 1+frec[n/2], 0]
My general advice is to avoid recursion unless it is very undeep. Here is a
straightforward Pascal-style solution without recursion:
fpas[n_] := Block[ {m=n, res = 0},
While[EvenQ[m],
m=m/2; res=res+1];
res]
fpas[2^15000] // Timing
{4.45 Second,15000}
Two variables are involved and during this loop 30000 assignments are done.
We might expect that iteration will be faster: no variables, no assignments.
fnest[n_] := NestWhile[{#[[1]]/2, #[[2]]+1}&,{n, 0}, EvenQ[#[[1]]]&, 1][[2]]
fnest[2^15000] // Timing
{8.35 Second,15000}
But it turns out to be slower! Let us look at the old FixedPoint
construction:
ffix[n_] := FixedPoint[ {#[[1]]/2, #[[2]]+1}&, {n,
0},SameTest->(OddQ[#2[[1]]]&) ] [[2]]
ffix[2^15000] // Timing
{5.16 Second,15000}
Not quite so fast as the Pascal implementation, but faster than the
relatively new NestWhile. Why do we have NestWhile when it is slower (and
more complicated) than While?
Fred Simons
Eindhoven University of Technology