zsh-users
 help / color / mirror / 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.





^ permalink raw reply	[flat|nested] 6+ messages in thread

* 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
  1 sibling, 1 reply; 6+ messages in thread
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.

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


^ permalink raw reply	[flat|nested] 6+ messages in thread

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



^ permalink raw reply	[flat|nested] 6+ messages in thread

* 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
  1 sibling, 1 reply; 6+ messages in thread
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


^ permalink raw reply	[flat|nested] 6+ messages in thread

* 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
  0 siblings, 1 reply; 6+ messages in thread
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.



^ permalink raw reply	[flat|nested] 6+ messages in thread

* 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


^ permalink raw reply	[flat|nested] 6+ messages in thread

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

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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

zsh-users

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://inbox.vuxu.org/zsh-users

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V1 zsh-users zsh-users/ http://inbox.vuxu.org/zsh-users \
		zsh-users@zsh.org
	public-inbox-index zsh-users

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.zsh.users


code repositories for the project(s) associated with this inbox:

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

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git