Iterate through digits of a number

how to Iterate through digits of a number using for loop

The general formula for doing this mathematically is num / (base ^ digit) % base. So doing this:

let mut num = 1234;
let base = 10usize;
let mut digit = 0;
while num != 0 {
    println!("{:?}", num % base);
    num /= base;
    digit += 1;
}

This does it progressively by reducing the original number.

2 Likes

You can also convert it to string and iterate through chars:

fn main() {
    let num = 1234;
    for i in num.to_string().chars() {
        println!("{}", i)
    }
}

Unfortunately that iterates in least-significant-first order (or in other words, from the right of the number), which is not what I'd expect from an iterator over digits.

You could always use the for loop to write a type T that impl Iterator<Item=u8>, instantiate T and then just call .rev() on the instance. It's clean, terse, flexible and idiomatic, at the cost of a little work.

@dunnock As for turning it into a String and iterating over the chars: that will work, but it likely less efficient. So ultimately it's a tradeoff between efficiency and ease of implementation.

2 Likes

That's true, but an implementation that uses log base 10 and then works backwards would probably be faster and would definitely use less memory because it doesn't need a Vec.

In principle I agree that slicing off the most significant digit when it's needed is the most performant option.

The only question is: how does one, in a generic manner, slice of the most significant digit of a number of arbitrary length (where the length of a number is defined as the number of digits it has)?

You wouldn't save any work with that, because rev requires the inner iterator to be a DoubleEndedIterator, so you'd need to implement next() as well as next_back() anyway.

Here is how I would implement it:

pub struct DigitsBase10 {
    mask: usize,
    num: usize,
}

impl Iterator for DigitsBase10 {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        if self.mask == 0 {
            return None;
        }

        let digit = self.num / self.mask % 10;
        self.mask /= 10;

        Some(digit as u8)
    }
}

fn closest_smaller_power_of_10(num: usize) -> usize {
    let answer = 10_f64.powf((num as f64).log10().floor()) as usize;

    // these properties need to hold. I think they do, but the float conversions
    // might mess things up...
    debug_assert!(answer <= num);
    debug_assert!(answer > num / 10);
    answer
}

impl DigitsBase10 {
    pub fn new(num: usize) -> Self {
        let mask = if num == 0 {
            1
        } else {
            closest_smaller_power_of_10(num)
        };

        DigitsBase10 { mask, num }
    }
}

fn main() {
    let iter = DigitsBase10::new(12_345_067_890);
    for num in iter {
        println!("{}", num);
    }
}

(playground)

1 Like

Double-precision IEEE-754 reals can represent all integers up to 2^53, after that there's gaps.

As @timotree3 has shown above, one way is to go through floats.

Alternatively, if one wanted to avoid casting between types, we could get a bit creative with bits. Getting the floored log2 of an integer is pretty easy, so we just need to convert it to a log10. Since the base 10 logarithm of 2 is approximately 1233 / 4096:

fn digits_iterator(mut n: u64) -> impl Iterator<Item = u64> {
    let log2 = 0_u64.count_zeros() - n.leading_zeros();
    let log10 = ((log2 + 1) * 1233) >> 12;
    let mut splitter = 10_u64.pow(log10);

    if n < splitter {
        splitter /= 10;
    }
    
    std::iter::from_fn(move || {
        if splitter > 0 {
            let digit = n / splitter;
            n %= splitter;
            splitter /= 10;
            Some(digit)
        } else {
            None
        }
    })
}

fn main() {
    let n = 1234567890;
    
    for digit in digits_iterator(n) {
        println!("{}", digit);
    }
}

playground
This version yields an empty iterator for 0, but modifying it to return 0 once is not very difficult.

To be honest, I have no idea whether the extra work to get the proper log10 and tuning the splitter is faster than going to floats. I just think it's neat. :grinning:

2 Likes

You don't need to allocate String or Vec, but an array of a fixed size ([u8; 20] for u64) is enough. The array is small enough and likely to be efficient (even be faster than directly iterating from the most significant digit, depending on implementation).