# Compilers, purity, and variance computation

**URL:** https://discourse.julialang.org/t/compilers-purity-and-variance-computation/119254
**Category:** Numerics
**Tags:** statistics, float, compiler
**Created:** [September 10, 2024, 3:20pm UTC](https://discourse.julialang.org/t/compilers-purity-and-variance-computation/119254 "2024-09-10T15:20:07Z")
**Posts on this page:** 1
**Showing post:** 4

<div class="post-metadata">

### Author: ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [September 10, 2024, 4:32pm UTC](https://discourse.julialang.org/t/compilers-purity-and-variance-computation/119254/4 "2024-09-10T16:32:56Z")

</div>

> [@Functional programming is not capable of achieving absolute top performance](https://discourse.julialang.org/t/functional-programming-is-not-capable-of-achieving-absolute-top-performance/119233/13):
>
> > [@stevengj](#):
> >
> > A single-pass algorithm looks fundamentally different than the two-pass algorithm […]
> 
> Why is that exactly?

There are plenty of articles on single-pass numerically stable algorithms for the variance, some of which are linked in the Wikipedia article I linked above.

> [@Functional programming is not capable of achieving absolute top performance](https://discourse.julialang.org/t/functional-programming-is-not-capable-of-achieving-absolute-top-performance/119233/13):
>
> I mean why can’t the loops be merged into one _in theory_ (at least when same direction kept for both, then merging wouldn’t change semantic meaning?!)?

Because a stable two-pass calculation of the variance _uses_ the result of the first sum (the mean) in the second sum (the variance).

> [@Functional programming is not capable of achieving absolute top performance](https://discourse.julialang.org/t/functional-programming-is-not-capable-of-achieving-absolute-top-performance/119233/13):
>
> should Julia provide a `sumstd` function that provides a tuple of both

It might be nice to have a `meanstd(x)` algorithm in Statistics.jl that returns both.

(Statistics.jl _does_ provide a [stable single-pass (“streaming”) `std` algorithm](https://github.com/JuliaStats/Statistics.jl/blob/128dc11f1694f10053d508e9aada33b5544a423b/src/Statistics.jl#L222-L235) that it uses for iterables that maybe only allow you to loop over them once.)

> [@Functional programming is not capable of achieving absolute top performance](https://discourse.julialang.org/t/functional-programming-is-not-capable-of-achieving-absolute-top-performance/119233/13):
>
> it seems like opposite directions would help many:

If it fits in the cache then you don’t need to reverse the order either.

> [@Functional programming is not capable of achieving absolute top performance](https://discourse.julialang.org/t/functional-programming-is-not-capable-of-achieving-absolute-top-performance/119233/13):
>
> Assuming you wouldn’t get _totally_ wrong answers: Kahan summation helps already, so wouldn’t opposite orders be in practice any issue?

Nope, Kahan summation doesn’t help here. Even if the \sum x\_k and \sum x\_k^2 are _exactly_ rounded — which is _better_ than Kahan and requires something like Xsum.jl — you can still lose _all_ the significant digits when you subtract them.

> [@Functional programming is not capable of achieving absolute top performance](https://discourse.julialang.org/t/functional-programming-is-not-capable-of-achieving-absolute-top-performance/119233/13):
>
> Yes, for traditional floats, but not a problem for Posits

Nope. If you round to a posit on each operation you still lose associativity (because the _order of the rounding_ changes). Gustafson only claims associativity for “quire” arithmetic that uses arbitrary precision.

But I don’t want to go down the rabbit-hole of debating the promises of posits here. We’ve already had long threads on this, e.g.: [Posits - a new approach could sink floating point computation - #17 by simonbyrne](https://discourse.julialang.org/t/posits-a-new-approach-could-sink-floating-point-computation/26176/17)

---

_[View the full topic](https://discourse.julialang.org/t/compilers-purity-and-variance-computation/119254)._