Is there a computationally optimal way to determine the number of digits in a range of natural numbers?

Question

Assume the numbers are in base 10 and each subsequent number is 1 more than the previous.

A naïve solution would be:

fn range_digits(start: usize, end: usize) -> usize {
    (start..=end).fold(0, |a, b| a + b.to_string().len())
}

Which gives the output 88915 for the inputs 5 for start and 20005 for end.

The best solution I could come up with was:

use std::convert::TryInto;

fn digits(a: usize) -> usize {
    ((a as f64).log10() as usize) + 1
}

// Present conversions and type casts could be problematic for certain inputs.
fn range_digits(start: usize, end: usize) -> usize {
    let (start_digits, end_digits) = (digits(start), digits(end));
    if start_digits == end_digits {
        (end - start + 1) * start_digits
    } else {
        let (a, b) = (
            10_usize.pow(start_digits.try_into().unwrap()) - 1,
            10_usize.pow((end_digits - 1).try_into().unwrap()) as usize,
        );
        (digits(a + 1)..=digits(b - 1)).fold(0, |acc, elem| {
            acc + 9 * elem * 10_usize.pow((elem - 1).try_into().unwrap())
        }) + ((a - start + 1) * start_digits)
            + ((end - b + 1) * end_digits)
    }
}

But I'm wondering if there's a yet more computationally efficient/optimal solution/formula.

Answer 1

The fastest approach probably is to do this completely with integer arithmetic. Switching between floats and integers is expensive. Here's a simple implementation. I didn't perform any benchmarks on it.

fn digits_in_range(base: usize, range: Range<usize>) -> usize {
    let mut result;
    let mut power = 1;
    let mut current_digits = 0;
    while power <= range.start {
        power *= base;
        current_digits += 1;
    }
    result = (power - range.start) * current_digits;
    while power <= range.end {
        let last_power = power;
        power *= base;
        current_digits += 1;
        result += (power - last_power) * current_digits;
    }
    result -= (power - range.end) * current_digits;
    result
}

This takes the number system base as the first argument, and a Range as the second argument. Note that a Range excludes its endpoint, so it's not included in the count. You can change this to RangeInclusive with a small correction to the code if you prefer.