是否有一种计算上最优的方法来确定自然数范围内的位数？

Question

假设数字以 10 为底，每个后续数字都比前一个数字多 1。

一个天真的解决方案是：

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

对于start的输入5和end的20005输出88915。

我能想到的最佳解决方案是：

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

但我想知道是否还有更多的计算方法 efficient/optimal solution/formula。

Answer 1

最快的方法可能是完全使用整数运算来完成此操作。在浮点数和整数之间切换是昂贵的。这是一个简单的实现。我没有对其执行任何基准测试。

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
}

这将数字系统基数作为第一个参数，Range 作为第二个参数。请注意，Range 排除了它的端点，因此它不包括在计数中。如果您愿意，可以将其更改为 RangeInclusive，并对代码进行小的更正。

Answer 2

这是一个解决方案：

硬编码 [0, 10**k - 1];
使用极其简单的整数算法推导出任何区间的值 [a, b]。

下面是假设 0 <= a <= b < 10**10.

的代码

我不懂生锈，所以这是python；但是算法很简单，我相信代码的逻辑很好理解。

def get_next_power_of_10(n):
  v, p = 10, 1
  while v <= n:
    v *= 10
    p += 1
  return (v, p)

# d[k] = number of digits in interval [0, 10**k - 1]
d = [1, 10, 190, 2890, 38890, 488890, 5888890, 68888890, 788888890, 8888888890, 98888888890]

def get_number_of_digits_in_0_n(n):
  (v, p) = get_next_power_of_10(n)
  return d[p] - p * (v - 1 - n)

def get_number_of_digits_in_interval(a, b):
  return get_number_of_digits_in_0_n(b) - get_number_of_digits_in_0_n(a-1)

是否有一种计算上最优的方法来确定自然数范围内的位数？

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

math

numbers

formula

string-length

rust