Function scaled_work 

fn scaled_work(factor: u128, work: u128) -> u128

Examples found in repository

crates/competitive/src/math/min_plus_convolution/selector.rs (lines 182-185)

fn select_algorithm<T>(
    a_len: usize,
    b_len: usize,
    a_characteristics: &InputCharacteristics<T>,
    b_characteristics: &InputCharacteristics<T>,
) -> Algorithm
where
    T: Signed + TryFrom<usize>,
    T::Unsigned: TryInto<usize>,
{
    let output = a_len.saturating_add(b_len).saturating_sub(1) as u128;
    let mut selected = ((a_len as u128) * (b_len as u128), Algorithm::Naive);
    let mut consider = |work: u128, algorithm| {
        if work < selected.0 {
            selected = (work, algorithm);
        }
    };

    consider(
        // min_plus/sparse: 50% finite inputs are already over 10% faster than
        // the INF-skipping naive scan, while dense pair enumeration loses.
        scaled_work(
            3,
            (a_characteristics.finite_count as u128) * (b_characteristics.finite_count as u128),
        ),
        Algorithm::Sparse,
    );
    if let (Some(a_extrema), Some(b_extrema)) =
        (a_characteristics.extrema, b_characteristics.extrema)
        && let Some(requirements) =
            bounded_requirements_from_extrema(a_len, b_len, a_extrema, b_extrema)
    {
        // min_plus/bounded: small transforms need a wider margin for encoding
        // overhead; at 2^20 and above the NTT wins from a lower work ratio.
        consider(
            scaled_work(
                if requirements.transform_len < 1 << 20 {
                    8
                } else {
                    6
                },
                (requirements.transform_len as u128) * (requirements.transform_len.ilog2() as u128),
            ),
            Algorithm::BoundedNtt,
        );
    }

    if a_characteristics.is_convex && b_characteristics.is_convex {
        consider(output, Algorithm::ConvexMerge);
    } else if a_characteristics.is_convex {
        consider(
            scaled_work(2, output),
            Algorithm::ConvexDivideAndConquerLeft,
        );
    } else if b_characteristics.is_convex {
        consider(
            scaled_work(2, output),
            Algorithm::ConvexDivideAndConquerRight,
        );
    }
    if a_characteristics.is_concave && b_characteristics.is_concave {
        consider(output, Algorithm::ConcaveBoth);
    } else if a_characteristics.is_concave || b_characteristics.is_concave {
        consider(
            scaled_work(8, output.saturating_mul(output.max(1).ilog2() as u128 + 1)),
            if a_characteristics.is_concave {
                Algorithm::ConcaveEnvelopeLeft
            } else {
                Algorithm::ConcaveEnvelopeRight
            },
        );
    }
    let increasing = a_characteristics.is_nondecreasing && b_characteristics.is_nondecreasing;
    let decreasing = a_characteristics.is_nonincreasing && b_characteristics.is_nonincreasing;
    if increasing || decreasing {
        consider(
            scaled_work(
                4,
                a_characteristics
                    .run_count
                    .saturating_mul(b_characteristics.run_count) as u128,
            ) + output,
            if decreasing {
                Algorithm::MonotoneRunsDecreasing
            } else {
                Algorithm::MonotoneRunsIncreasing
            },
        );
    }
    let piecewise = match (
        a_characteristics.finite_count == a_len,
        b_characteristics.finite_count == b_len,
    ) {
        (true, true) if a_characteristics.piece_count < b_characteristics.piece_count => {
            Some((a_characteristics.piece_count, true))
        }
        (true, true) => Some((b_characteristics.piece_count, false)),
        (true, false) => Some((a_characteristics.piece_count, true)),
        (false, true) => Some((b_characteristics.piece_count, false)),
        (false, false) => None,
    };
    if let Some((pieces, structured_is_left)) = piecewise {
        if pieces == 1 {
            consider(
                output,
                if structured_is_left {
                    Algorithm::LinearLeft
                } else {
                    Algorithm::LinearRight
                },
            );
        } else {
            consider(
                scaled_work(4, (pieces as u128).saturating_mul(output)),
                if structured_is_left {
                    Algorithm::PiecewiseLinearLeft
                } else {
                    Algorithm::PiecewiseLinearRight
                },
            );
        }
    }
    selected.1
}