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