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" <
address@hidden> wrote:
On Tue, Oct 13, 2015 at 12:17 PM, Elias Mårtenson <address@hidden> 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