Re: Why NestWhile?
- To: mathgroup at smc.vnet.net
- Subject: [mg26944] Re: [mg26914] Why NestWhile?
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 27 Jan 2001 20:00:11 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Having reflected a bit on what I had just sent, it seems clear that the theoretical time complexity of the algorithm used by the Pascal style program, which uses only division by 2, should be smaller than that of my fmath, which needs to compute the expansion of n in base 2 (this, I think, has time complexity log(n)^2). But in practice the advantage of using an optimised built-in function seems to easily outweigh this (as is often the case with Mathematica programs). -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/ on 01.1.27 11:05 PM, Andrzej Kozlowski at andrzej at tuins.ac.jp wrote: > 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} >