[Factor-talk] Let's fix yosefk's tricky code
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
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
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