MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Napoleon
  • Next by Date: Re: Re: exporting animations
  • Previous by thread: Re: Mathematica 4.1 + Linux + gnome/sawfish
  • Next by thread: Re: Why NestWhile?