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
>
>