Ok, I did mean that. My solution wastes on average one bit of RAM for the duration of the execution of the function. Not much, but I agree it's ugly. ☺ On 13 Oct 2015 6:53 p.m., "Kacper Gutowski" <mwgam...@gmail.com> wrote:
> On Tue, Oct 13, 2015 at 12:17 PM, Elias Mårtenson <loke...@gmail.com> > wrote: > > It should be new set_size/8+1 on both the like with new and the > subsequent > > memset() one. > > You mean (set_size+7)/8 :) > > I was almost expecting this to be related to that this algorithm's > termination probability converges to 1 very slowly when A is close to B, > but 100 is small and 100?100 worked for me from time to time regardless > of ⎕RL so that's not it. Good catch, Jay! > > > While this isn't related to the bug reported, this algorithm saves a lot > of memory when A << B, but otherwise it doesn't buy us anything because > A cells need to be allocated for the result anyway. I think it might > be a good idea to switch to standard Fisher-Yates shuffle at some point > when A gets close to B (i.e. allocate B IntCells, shuffle in place and > return first A of them; this terminates deterministically in linear time). > > -k >
