I know this isn't chat but I had to observe:  you guys hang around
some very unusual bars.

On Thu, Mar 6, 2014 at 10:34 AM, Roger Hui <rogerhui.can...@gmail.com> wrote:
>> Suppose x is a vector of bits (such as they have in APL).
>> How do you sort x?
>
> Yes, the algorithmically interesting aspect is m=:+/x, because /:~x ←→
> ((m-~#x),m)#0 1.
>
> +/x for bit vector x has an interesting history, celebrated in story and
> song.  See http://www.jsoftware.com/jwiki/Essays/Sum_of_a_Bit_Array and the
> links therein.  The essay needs to be updated because nowadays the fastest
> way in C is:
>
> I4 *w=(I4*)x;
> q=n/32;
> for(i=sum=0;i<q;++i)sum+=popcnt(*w++);
>
>
> // the case where n is not a multiple of 32 is
> // left as an exercise for the reader
>
>
> where popcnt <https://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT> is a
> machine instruction available in SSE4 and the instruction set of other CPUs.
>
>
>
>
> On Thu, Mar 6, 2014 at 6:27 AM, David Lambert <b49p23t...@stny.rr.com>wrote:
>
>> NB. In c I'd use an algorithm such as
>>
>> BS =: 8    NB. block size
>> BLOCK =: 2^BS
>>
>> NB. convert to blocks with padding
>> BLOCKED_DATA =: BS (#.\~ -)~ BINARY_DATA
>>
>> count_bits =: +/"1@:#:
>> assert 0 1 5-:count_bits 2b0 2b1000 2b110010010100
>>
>> NB. crucial idea, use known time for bit counting
>> COUNTS =: ([: count_bits i.) BLOCK
>>
>> HIGHS =: BLOCKED_DATA ([: +/ {) COUNTS
>>
>>
>>
>> NB. Maybe we're just looking for
>>
>> HIGHS =: +/BINARY_DATA
>> LOWS =: (HIGHS -~ #) BINARY_DATA
>> SORTED_BINARY_DATA =: (LOWS , HIGHS) # 0 1
>>
>>
>> On 03/06/2014 07:00 AM, programming-requ...@forums.jsoftware.com wrote:
>>
>>> Date: Wed, 5 Mar 2014 20:52:35 -0800
>>> From: Roger Hui<rogerhui.can...@gmail.com>
>>> To: Programming forum<programm...@jsoftware.com>
>>>
>>> Subject: Re: [Jprogramming] a good bar bet!
>>> Message-ID:
>>>         <CAMZ_i_BYHHGPQkvMbufbfx3g9292SC2XvHZk
>>> qjcovhhwbdi...@mail.gmail.com>
>>> Content-Type: text/plain; charset=UTF-8
>>>
>>>
>>> How about an extreme version of the sort problem.  Suppose x is a vector
>>> of
>>> bits (such as they have in APL).  How do you sort x?
>>>
>>> This would have been one way to solve the sorting small integers problem:
>>> figure out how to sort 0-1 vectors and then work your way up from that.  I
>>> once posed the 88 Hats
>>> Problem<http://www.jsoftware.com/jwiki/Essays/88_Hats>to a very smart
>>>
>>> and very persistent intern.  He solved it by generalizing a
>>> solution to the 2 Hats problem.
>>>
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm



-- 
 - michael dykman
 - mdyk...@gmail.com

 May the Source be with you.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm

Reply via email to