mach.d icon indicating copy to clipboard operation
mach.d copied to clipboard

Investigate more efficient length function for UnorderedCartPowerRange in mach.range.cartpower

Open pineapplemachine opened this issue 8 years ago • 0 comments

The current implementation relies on this recursive function; however it seems likely that it should be possible to compute without recursion, or at least with less of it:

static private size_t unorderedlength(size_t size)(in size_t ilen){
    static if(size == 0){
        return ilen > 0 ? 1 : 0;
    }else static if(size == 1){
        return ilen;
    }else static if(size == 2){
        // Same as `ilen + unorderedlength!size(ilen - 1)`
        // And as `ilen * (ilen + 1) / 2`, but without overflow
        immutable x = ilen + 1;
        return (ilen / 2) * x + ((ilen & 1) * x) / 2;
    }else{
        if(ilen <= 1){
            return ilen;
        }else{
            return unorderedlength!(size)(ilen - 1) + unorderedlength!(size - 1)(ilen);
        }
    }
}

pineapplemachine avatar Mar 03 '17 21:03 pineapplemachine