Thursday, February 12, 2015

2 to the power of N has X digits.

Tested with Visual Studio 2012

// std::pow (2, pow) has number_of_digits (pow) digits.
// Despite the recursive step, this is an O(1) operation.
auto number_of_digits (unsigned long long pow) -> unsigned long long
{
    if (pow < 4) {
        return 1 ;
    }

    else if (pow < 7) {
        return 2 ;
    }

    else if (pow < 10) {
        return 3 ;
    }

    else {
        unsigned long long n = pow / 10 ;
        unsigned long long least_significant_digit = pow - (n * 10) ;
        return n * 3 + number_of_digits (least_significant_digit) ;
    }
}


And here's a test Driver:

#include <iostream>

int main ()
{
    for (int n = 0; n < 10; ++n) {
        std::cout << "pow (2, " << n << ") has " << number_of_digits (n) << " digits." "\n" ;
    }

    for (int n = 10; n <= 100; n += 10) {
        std::cout << "pow (2, " << n << ") has " << number_of_digits (n) << " digits." "\n" ;
    }

    std::cout << "pow (2, 1000) has " << number_of_digits (1000) << " digits." "\n" ;
    std::cout << "pow (2, 1024) has " << number_of_digits (1024) << " digits." "\n" ;
    std::cout << "pow (2, 2000) has " << number_of_digits (2000) << " digits." "\n" ;
    std::cout << "pow (2, 2048) has " << number_of_digits (2048) << " digits." "\n" ;
   
    for (int n = 10000; n <= 100000; n += 10000) {
        std::cout << "pow (2, " << n << ") has " << number_of_digits (n) << " digits." "\n" ;
    }

    return 0 ;
}


If you want a templated version for some reason, you could try this:

#include <type_traits>

template <typename T>
auto number_of_digits (T pow)
    -> typename std::enable_if <std::is_integral <T>::value, T>::type
{
    if (pow <= 3) {
        return 1 ;
    }

    else if (pow <= 6) {
        return 2 ;
    }

    else if (pow <= 9) {
        return 3 ;
    }

    else {
        T n = pow / 10 ;
        T least_significant_digit = pow - (n * 10) ;
        return n * 3 + number_of_digits (least_significant_digit) ;
    }
}

No comments:

Post a Comment