Search code examples
mathbigintegerlogarithm

What is the fastest way to find if a large integer is power of ten?

I could just use division and modulus in a loop, but this is slow for really large integers. The number is stored in base two, and may be as large as 2^8192. I only need to know if it is a power of ten, so I figure there may be a shortcut (other than using a lookup table).

Solution

  • If your number x is a power of ten then

    x = 10^y

    for some integer y, which means that

    x = (2^y)(5^y)

    So, shift the integer right until there are no more trailing zeroes (should be a very low cost operation) and count the number of digits shifted (call this k). Now check if the remaining number is 5^k. If it is, then your original number is a power of 10. Otherwise, it's not. Since 2 and 5 are both prime this will always work.