run time of math problem

run time of math problem

[Ray Andrews]

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

[Lawrence Velázquez]

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

Think about how your change affects your algorithm.

>   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

[Ray Andrews]

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

[Oliver Kiddle]

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

[Ray Andrews]

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

[Lawrence Velázquez]

> 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