```zsh-users
help / color / mirror / code / Atom feed```
```* run time of math problem
@ 2021-03-19 23:18 Ray Andrews
2021-03-19 23:46 ` Lawrence Velázquez
2021-03-19 23:52 ` Oliver Kiddle
0 siblings, 2 replies; 6+ messages in thread
From: Ray Andrews @ 2021-03-19 23:18 UTC (permalink / raw)
To: Zsh Users

This question might not even be answerable and it's only a point of
interest:
I was working out some probabilities and the algorithm looks like this:

for ((level=1; level<100; level++)); do
sum=
remainder=\$(( (level - 1.0) / level ))
for ((terms=level; terms; terms--)); do
sum+=\$(( remainder**(terms - 1) ))
done
divided=\$(( sum * (1.0 / level) ))
echo for level: \$level, survival: \$divided
done

Now if I avoid the 'remainder' variable:

for ((level=1; level<100; level++)); do
sum=
for ((terms=level; terms; terms--)); do

# 'remainder' calculation done directly here:
sum+=\$(( ( (level - 1.0) / level )**(terms - 1) ))
done
divided=\$(( sum * (1.0 / level) ))
echo for level: \$level, survival: \$divided
done

... I'd expect the thing to run a teeny bit faster but in fact it
runs about 15% slower.  Is that explicable?  Does zsh prefer
calculations done in steps with variables for each step?  Or is this
just some little anomaly?  Things might not optimize every time.

• ```* Re: run time of math problem
2021-03-19 23:18 run time of math problem Ray Andrews
@ 2021-03-19 23:46 ` Lawrence Velázquez
2021-03-19 23:51   ` Ray Andrews
2021-03-19 23:52 ` Oliver Kiddle
From: Lawrence Velázquez @ 2021-03-19 23:46 UTC (permalink / raw)
To: Ray Andrews; +Cc: zsh-users

> On Mar 19, 2021, at 7:18 PM, Ray Andrews <rayandrews@eastlink.ca> wrote:
>
> ... I'd expect the thing to run a teeny bit faster but in fact it
> runs about 15% slower.  Is that explicable?  Does zsh prefer
> calculations done in steps with variables for each step?  Or is this
> just some little anomaly?  Things might not optimize every time.

>   for ((level=1; level<100; level++)); do
>        sum=
>        remainder=\$(( (level - 1.0) / level ))
>        for ((terms=level; terms; terms--)); do
>            sum+=\$(( remainder**(terms - 1) ))
>        done
>        divided=\$(( sum * (1.0 / level) ))
>        echo for level: \$level, survival: \$divided
>   done

Here, you evaluate "(level - 1.0) / level" 99 times.

> Now if I avoid the 'remainder' variable:
>
>     for ((level=1; level<100; level++)); do
>         sum=
>         for ((terms=level; terms; terms--)); do
>
>            # 'remainder' calculation done directly here:
>            sum+=\$(( ( (level - 1.0) / level )**(terms - 1) ))
>        done
>        divided=\$(( sum * (1.0 / level) ))
>        echo for level: \$level, survival: \$divided
>   done

Here, you evaluate it 4950 times.

vq

• ```* Re: run time of math problem
2021-03-19 23:46 ` Lawrence Velázquez
@ 2021-03-19 23:51   ` Ray Andrews
0 siblings, 0 replies; 6+ messages in thread
From: Ray Andrews @ 2021-03-19 23:51 UTC (permalink / raw)
To: zsh-users

On 2021-03-19 4:46 p.m., Lawrence Velázquez wrote:
>
> Here, you evaluate it 4950 times.
>
> vq
>
Nuts, it's just that simple.  I'm not as sharp as I once was. Thanks
Lawrence, but that's embarrassing and I'm only 64.

• ```* Re: run time of math problem
2021-03-19 23:18 run time of math problem Ray Andrews
2021-03-19 23:46 ` Lawrence Velázquez
@ 2021-03-19 23:52 ` Oliver Kiddle
2021-03-20  2:40   ` Ray Andrews
From: Oliver Kiddle @ 2021-03-19 23:52 UTC (permalink / raw)
To: Ray Andrews; +Cc: Zsh Users

Ray Andrews wrote:
>      for ((level=1; level<100; level++)); do
>          sum=
>          for ((terms=level; terms; terms--)); do
>
>              # 'remainder' calculation done directly here:
>              sum+=\$(( ( (level - 1.0) / level )**(terms - 1) ))
>          done
>          divided=\$(( sum * (1.0 / level) ))
>          echo for level: \$level, survival: \$divided
>     done
>
> ... I'd expect the thing to run a teeny bit faster but in fact it
> runs about 15% slower.  Is that explicable?  Does zsh prefer

Given that the latter approach has moved the remainder calculation
inside a loop and it needs to be repeated 50 times (on average), it
should be no surprise that it is slower.

If you want to optimise for speed, avoid string conversions and do, e.g.
(( divided = sum * (1.0 / level) ))

You also may want to make sure to declare some of the variables as float
or integer or whatever. The sum+= line might end up being a string
concatenation if not.

Oliver

• ```* Re: run time of math problem
2021-03-19 23:52 ` Oliver Kiddle
@ 2021-03-20  2:40   ` Ray Andrews
2021-03-20  3:59     ` Lawrence Velázquez
From: Ray Andrews @ 2021-03-20  2:40 UTC (permalink / raw)
To: zsh-users

On 2021-03-19 4:52 p.m., Oliver Kiddle wrote:
>
> If you want to optimise for speed, avoid string conversions and do, e.g.
>    (( divided = sum * (1.0 / level) ))
Thanks, that's easy to miss but it makes sense.  One of those invisible
things.
Doing it that way throughout is fully 3X faster.  Running it up to a
billion itterrations it
starts to matter.
As to the rest I was just stupidly forgetting that I'm in a loop. I'm
faking a summation.
We don't have summation do we?
> You also may want to make sure to declare some of the variables as float
> or integer or whatever. The sum+= line might end up being a string
> concatenation if not.
Yeah, I left out the declarations but it was all kosher.

• ```* Re: run time of math problem
2021-03-20  2:40   ` Ray Andrews
@ 2021-03-20  3:59     ` Lawrence Velázquez
0 siblings, 0 replies; 6+ messages in thread
From: Lawrence Velázquez @ 2021-03-20  3:59 UTC (permalink / raw)
To: Ray Andrews; +Cc: zsh-users

> On Mar 19, 2021, at 10:40 PM, Ray Andrews <rayandrews@eastlink.ca> wrote:
>
> As to the rest I was just stupidly forgetting that I'm in a loop.
> I'm faking a summation. We don't have summation do we?

Not that I'm aware of, but you're computing partial sums of geometric
series [*], so you have a closed-form expression available to you:

for (( level = 1; level < 100; level++ )); do
((
remainder = (level - 1.0) / level,
sum = level - level * remainder**level,
divided = sum * (1.0 / level)
))
echo for level: \$level, survival: \$divided
done

[*]: https://mathworld.wolfram.com/GeometricSeries.html

--
vq

```end of thread, other threads:[~2021-03-20  4:00 UTC | newest]

2021-03-19 23:18 run time of math problem Ray Andrews
2021-03-19 23:46 ` Lawrence Velázquez
2021-03-19 23:51   ` Ray Andrews
2021-03-19 23:52 ` Oliver Kiddle
2021-03-20  2:40   ` Ray Andrews
2021-03-20  3:59     ` Lawrence Velázquez
```

```Code repositories for project(s) associated with this public inbox

https://git.vuxu.org/mirror/zsh/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).```