[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 bjou...@gmail.com 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