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

```

• Prev by Date: Re: Why NestWhile?
• Next by Date: Compression Algorithm Notebook
• Previous by thread: Re: Why NestWhile?