3 ms·

The author links to another blog post called "A nice approximation of the norm of a 2D vector" [1], Recently I learnt from Youtube about the Alpha max plus beta

The author links to another blog post called "A nice approximation of the norm of a 2D vector" [1], Recently I learnt from Youtube about the Alpha max plus beta min algorithm [2] which is a better approximation, it uses 1 max and linear combination to achieve 3.96% largest error compared to the approximation in the blog post which uses 2 max and has 5.3% error. I also wrote a comment on his blog so hopefully he will see it. [1]: https://klafyvel.me/blog/articles/approximate-euclidian-norm/ https://klafyvel.me/blog/articles/approximate-euclidian-norm... [2]: https://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm https://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algori...

rocqua 4y ago
From wikipedia it looks like both the article's approximation and this method have octagonal level sets. I was wondering what the actual difference was. Looking into it a bit, I came across the error graph [2] from the article[1]. The main difference seems to be that the octagon used by the article is 'too small'. The maximum error would be smaller with a larger octagon. Currently there is an undershoot of 5.2 % and an overshoot of 2.5%. To reduce the maximum error, you need undershoot and overshoot to be equal. Another notable difference is that the article's octagons have a different rotation than the alpha plus max beta algorithm. The article's octagons cross the axes perpendicularly, whilst the alternative algorithm is rotated by 360/16=22.5 degrees so it has vertices at the axes. That certainly changes at which angles the approximations are better, which might matter in practice. What I wasn't able to find quickly is the average error for the article's approximation. Would be interesting to compare that to the 2.41% for the better algorithm. [1] https://klafyvel.me/blog/articles/approximate-euclidian-norm/ https://klafyvel.me/blog/articles/approximate-euclidian-norm... [2] https://klafyvel.me/assets/blog/articles/approximate-euclidian-norm/code/output/illustration10.svg https://klafyvel.me/assets/blog/articles/approximate-euclidi...
- adgjlsfhk1 4y ago
  the difference is error metric. the article is minimizing L2 error instead of maximum error.

rocqua 4y ago

From wikipedia it looks like both the article's approximation and this method have octagonal level sets. I was wondering what the actual difference was. Looking into it a bit, I came across the error graph [2] from the article[1]. The main difference seems to be that the octagon used by the article is 'too small'. The maximum error would be smaller with a larger octagon. Currently there is an undershoot of 5.2 % and an overshoot of 2.5%. To reduce the maximum error, you need undershoot and overshoot to be equal. Another notable difference is that the article's octagons have a different rotation than the alpha plus max beta algorithm. The article's octagons cross the axes perpendicularly, whilst the alternative algorithm is rotated by 360/16=22.5 degrees so it has vertices at the axes. That certainly changes at which angles the approximations are better, which might matter in practice. What I wasn't able to find quickly is the average error for the article's approximation. Would be interesting to compare that to the 2.41% for the better algorithm. [1] https://klafyvel.me/blog/articles/approximate-euclidian-norm/ https://klafyvel.me/blog/articles/approximate-euclidian-norm... [2] https://klafyvel.me/assets/blog/articles/approximate-euclidian-norm/code/output/illustration10.svg https://klafyvel.me/assets/blog/articles/approximate-euclidi...

adgjlsfhk1 4y ago
the difference is error metric. the article is minimizing L2 error instead of maximum error.