Skip to content

base_convert: If we keep track of leading zero limbs we can half iterations. #69

@github-actions

Description

@github-actions

On 2022-05-28 @recmo wrote in b0b5d54 “Mod names”:

If we keep track of leading zero limbs we can half iterations.

    #[allow(clippy::cast_possible_truncation)] // Doesn't truncate
    fn next(&mut self) -> Option<Self::Item> {
        // Knuth Algorithm S.
        let mut zero: u64 = 0_u64;
        let mut remainder = 0_u128;
        // OPT: If we keep track of leading zero limbs we can half iterations.
        for limb in self.limbs.iter_mut().rev() {
            zero |= *limb;
            remainder <<= 64;
            remainder |= u128::from(*limb);
            *limb = (remainder / u128::from(self.base)) as u64;

From src/base_convert.rs:122

Metadata

Metadata

Assignees

Labels

optimizePotential optimization opportunitytrackerIssue tracked by bot

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions