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