[Factor-talk] Let's fix yosefk's tricky code

[Björn Lindqvist]

Hello everybody,

Here is an interesting blog post from yosefk about Forth and stack machines:

http://yosefk.com/blog/my-history-with-forth-stack-machines.html

It contains a lot of interesting stuff but one part in particular got
my interest. He is trying to write a word to "compute the mean and the
standard deviation of a vector given the sum of its elements, the sum
of their squares, and the inverse of its length" and what he produces
to solve it is:

: mean_std ( sum2 sum inv_len -- mean std )
  \ precise_mean = sum * inv_len;
  tuck u* \ sum2 inv_len precise_mean
  \ mean = precise_mean >> FRAC;
  dup FRAC rshift -rot3 \ mean sum2 inv_len precise_mean
  \ var = (((unsigned long long)sum2 * inv_len) >> FRAC) -
(precise_mean * precise_mean >> (FRAC*2));
  dup um* nip FRAC 2 * 32 - rshift -rot \ mean precise_mean^2 sum2 inv_len
  um* 32 FRAC - lshift swap FRAC rshift or \ mean precise_mean^2 sum*inv_len
  swap - isqrt \ mean std ;

So his code is hideous and I'm wondering if we can do it better in
Factor? I'd love to take a stab at it myself but I have no idea what
mathematical formula he is implementing. Anyone knows? As far as I
understand, given three scalar values: the sum of all elements in a
vector, the sum of all elements squared and the inverse of the length,
you should be able to calculate the mean of the vector and the
standard deviation.


-- 
mvh/best regards Björn Lindqvist

--
___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk

Re: [Factor-talk] Let's fix yosefk's tricky code

[Jon Purdy]

It seems like most of the overhead comes from fixed-point arithmetic,
actually. Here’s a translation to Kitten with locals:




On Wed, Aug 13, 2014 at 12:09 PM, Björn Lindqvist  wrote:

> Hello everybody,
>
> Here is an interesting blog post from yosefk about Forth and stack
> machines:
>
> http://yosefk.com/blog/my-history-with-forth-stack-machines.html
>
> It contains a lot of interesting stuff but one part in particular got
> my interest. He is trying to write a word to "compute the mean and the
> standard deviation of a vector given the sum of its elements, the sum
> of their squares, and the inverse of its length" and what he produces
> to solve it is:
>
> : mean_std ( sum2 sum inv_len -- mean std )
>   \ precise_mean = sum * inv_len;
>   tuck u* \ sum2 inv_len precise_mean
>   \ mean = precise_mean >> FRAC;
>   dup FRAC rshift -rot3 \ mean sum2 inv_len precise_mean
>   \ var = (((unsigned long long)sum2 * inv_len) >> FRAC) -
> (precise_mean * precise_mean >> (FRAC*2));
>   dup um* nip FRAC 2 * 32 - rshift -rot \ mean precise_mean^2 sum2 inv_len
>   um* 32 FRAC - lshift swap FRAC rshift or \ mean precise_mean^2
> sum*inv_len
>   swap - isqrt \ mean std ;
>
> So his code is hideous and I'm wondering if we can do it better in
> Factor? I'd love to take a stab at it myself but I have no idea what
> mathematical formula he is implementing. Anyone knows? As far as I
> understand, given three scalar values: the sum of all elements in a
> vector, the sum of all elements squared and the inverse of the length,
> you should be able to calculate the mean of the vector and the
> standard deviation.
>
>
> --
> mvh/best regards Björn Lindqvist
>
>
> --
> ___
> Factor-talk mailing list
> Factor-talk@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
--
___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk

Re: [Factor-talk] Let's fix yosefk's tricky code

[Jon Purdy]

Sigh. The formatting button in Gmail is directly next to the “Send” button.
Apologies, list.

> It seems like most of the overhead comes from fixed-point arithmetic,
> actually. Here’s a translation to Kitten with locals:

def meanStd (float float float → float float):

  → sum2 sum invLen;

  sum ×. invLen → μ;
  μ (sum2 ×. invLen −. μ square) sqrt

You can write this in postfix:

def meanStd (float float float → float float):

  → sum2 sum invLen;

  sum invLen (×.) → μ;
  μ sum2 invLen (×.) μ square (−.) sqrt

Then easily eliminate μ:

def meanStd (float float float → float float):

  → sum2 sum invLen;

  sum invLen (×.) dup
  { sum2 invLen (×.) } dip
  square (−.) sqrt

I see no need to eliminate the named parameters, and if this were using
fixed-point arithmetic, I would make separate arithmetic words to handle
the shifting. It’s worth noting that swapping “sum” and “sum2” could give a
nicer translation, since “sum” is used first; and that multiplying by the
inverse-length is repeated.

Also, not all Kitten is so Unicode-heavy, but in toy code, why not? :)
--
___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk