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

```

• Prev by Date: 1. Input of screen coordinates; 2. Fast graphics
• Next by Date: Re: Why NestWhile?
• Previous by thread: Why NestWhile?
• Next by thread: Re: Why NestWhile?