Re: Why NestWhile?

*To*: mathgroup at smc.vnet.net*Subject*: [mg26942] Re: [mg26914] Why NestWhile?*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Sat, 27 Jan 2001 20:00:09 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

I am afraid I can't answer the question that is the subject of your posting. But I got intrigued by the idea that one should be able to do much better (as far as speed is concerned) by using neither recursion not pascal-style programming but the unique Mathematica programming style, and I came up with the following: fmath[n_] := Plus @@ Plus @@ Position[Reverse[IntegerDigits[n, 2]], 1, {1}, 1] - 1 Compared with fpas it appears quite a lot faster: fpas[n_] := Block[{m = n, res = 0}, While[EvenQ[m], m = m/2; res = res + 1]; res] In[3]:= fmath[5000!] // Timing Out[3]= {0.0833333 Second, 4995} while In[4]:= fpas[5000!] // Timing Out[4]= {1.58333 Second, 4995} -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/ on 01.1.27 1:29 PM, F.H.Simons at tue.nl at F.H.Simons at tue.nl wrote: > 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 > >