Skip to content

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

@pineapplemachine

Description

@pineapplemachine

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);
        }
    }
}

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions