TheAlgorithms/Rust · error

Encountered NaN

Error message

Encountered NaN

What it means

fractional_knapsack panics with this .expect() message while sorting items by value/weight ratio (src/dynamic_programming/fractional_knapsack.rs:10). Ratios are computed as v / w, so a weight of 0.0 (with value 0.0) produces NaN, and NaN can also arrive directly in the weights or values vectors; f64::partial_cmp returns None whenever either operand is NaN, and the code expects a Some, aborting the thread. This is the classic float-ordering pitfall: NaN violates total order, so every partial_cmp-based sort must handle None. (Infinity alone does NOT trigger this — inf is orderable; only NaN does.)

Source

Thrown at src/dynamic_programming/fractional_knapsack.rs:10

pub fn fractional_knapsack(mut capacity: f64, weights: Vec<f64>, values: Vec<f64>) -> f64 {
    // vector of tuple of weights and their value/weight ratio
    let mut weights: Vec<(f64, f64)> = weights
        .iter()
        .zip(values.iter())
        .map(|(&w, &v)| (w, v / w))
        .collect();

    // sort in decreasing order by value/weight ratio
    weights.sort_unstable_by(|a, b| b.1.partial_cmp(&a.1).expect("Encountered NaN"));
    dbg!(&weights);

    // value to compute
    let mut knapsack_value: f64 = 0.0;

    // iterate through our vector.
    for w in weights {
        // w.0 is weight and w.1 value/weight ratio
        if w.0 < capacity {
            capacity -= w.0; // our sack is filling
            knapsack_value += w.0 * w.1;
            dbg!(&w.0, &knapsack_value);
        } else {
            // Multiply with capacity and not w.0
            dbg!(&w.0, &knapsack_value);
            knapsack_value += capacity * w.1;
            break;
        }

View on GitHub (pinned to 2c53ddfa4b)

Solutions

1. Validate inputs before calling: every weight must be finite and > 0.0, every value finite, and weights.len() == values.len(); handle zero-weight items separately (they are taken for free).
2. If you control the code, sort with the NaN-tolerant total order: weights.sort_unstable_by(|a, b| b.1.total_cmp(&a.1)) — removes the panic entirely and is the idiomatic float sort.
3. Or filter non-finite ratios before sorting: weights.retain(|&(w, r)| w.is_finite() && r.is_finite());
4. If NaN inputs are expected in your domain, decide the policy explicitly (treat as lowest priority, or return an error) instead of relying on the panic.
5. If you fork the file, also delete the leftover dbg!() calls — they print the whole item list to stderr on every run.

Example fix

// before
let mut weights: Vec<(f64, f64)> = weights
    .iter()
    .zip(values.iter())
    .map(|(&w, &v)| (w, v / w))
    .collect();
weights.sort_unstable_by(|a, b| b.1.partial_cmp(&a.1).expect("Encountered NaN"));

// after
let mut weights: Vec<(f64, f64)> = weights
    .iter()
    .zip(values.iter())
    .map(|(&w, &v)| (w, v / w))
    .filter(|&(w, r)| w.is_finite() && w > 0.0 && r.is_finite())
    .collect();
weights.sort_unstable_by(|a, b| b.1.total_cmp(&a.1));

fn valid_knapsack_input(capacity: f64, weights: &[f64], values: &[f64]) -> bool {
    weights.len() == values.len()
        && capacity.is_finite()
        && capacity >= 0.0
        && weights.iter().zip(values.iter()).all(|(&w, &v)| {
            w.is_finite() && w > 0.0 && v.is_finite()
        })
}

if valid_knapsack_input(capacity, &weights, &values) {
    let total = fractional_knapsack(capacity, weights, values); // sort cannot see NaN
}

// fractional_knapsack panics rather than returning Err; validation is the
// primary defense, but untrusted pipelines can fence the panic:
let total = match std::panic::catch_unwind(move || {
    fractional_knapsack(capacity, weights, values)
}) {
    Ok(total) => total,
    Err(_) => {
        // NaN reached the sort: clean the data set and retry
        0.0
    }
};

When it happens

Trigger: A weight of 0.0 with value 0.0 (0/0 → NaN ratio); passing f64::NAN anywhere in values — the crate's own test_nan does exactly this; a NaN weight (v / NaN → NaN); NaNs propagated from upstream math such as missing CSV/JSON fields parsed as 0.0 or NaN, or earlier 0.0/0.0 computations.

Common situations: Datasets with missing numeric fields defaulted to 0.0 (zero-weight items) fed straight into the function; inventory problems where items legitimately have zero weight; reusing floats from log/sqrt of negative inputs that already became NaN; assuming sort_unstable_by with partial_cmp is a total order and unwrap/expect-ing it in code review.

Related errors

• InvalidData
• Failed to compute modular inverse

AI-assisted analysis of TheAlgorithms/Rust@2c53ddfa4b (2026-08-16). Data as JSON: /api/errors/c67fda856aacd130. Report an issue: GitHub.