What's the quickest way to get the length of an integer?

help
1

S'pose I have some integer type, T.
The obvious way would be to get the length of of the string of that integer:

fn get_len_of_int<T>(i: T) -> usize
    where T: std::string::ToString
{
    i.to_string().len()
}

But is that the fastest way?
playground

Meta-questions:

  1. There are methods in the std library for quickly getting the binary representation of the integer, but I see no obvious conversion from binary to base 10. I may simply be uncreative though.
  2. I wonder how fast converting things to strings really is. I could test this (am doing that now), but I could bother other smart people too. Could it be that for some small cases, that a looping mod 10 method is faster?
2

If you don't care for precision up to 2^53 or so, then I'd look into logarithms. Specifically log base 10. It might not be the fastest way, that'd need some testing.

You can convert from base 2 to base 10 using the from_str_radix in the number types:

let my_str = "110101101";
let my_number = usize::from_str_radix(my_str, 2);

Converting to a string is realistically a loop and mod ten method, so it would have a time complexity of O(log10(n)) I believe.

1 Like
3

While trying to implement this a different way, I ran into a situation where I think I need a trait bound, but I'm not quite sure how to find what trait bound I need to satisfy. How would I accomplish this?

fn get_len_of_int2<T>(i: T) -> usize
where T: std::ops::Rem + std::cmp::PartialOrd
{
    std::iter::repeat_with({
        let mut len = 0_u32;
        move || {
            len+=1;
            i % (10 as T).pow(len)>0
        }
    }).take_while(|&x| x).count()
}
4

I would just do

fn int_log10<T>(mut i: T) -> u32
where T: std::ops::DivAssign + std::cmp::PartialOrd + From<u8> + Copy
{
    let mut len = 0;
    let zero = T::from(0);
    let ten = T::from(10);

    while i > zero {
        i /= ten;
        len += 1;
    }
    
    len
}
6 Likes
5

You might like the bithacks version of integer log 10:
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10

2 Likes
6

The fastest way generally involves knowing more about what you're actually trying to accomplish with this number, and whether you can lose some accuracy for speed. One can get an approximate log2 using leading_zeros quite efficiently -- there's an instruction for it -- so rephrasing the problem to use that is generally the fastest option.

3 Likes
7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.