Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

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

Search the Archive

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?
  • Next by thread: Napoleon ...no more emails please!