the most efficient way to calculate the number of digits from 1 to n

[Duthomhas]

Fair enough.

[JLBorges]

Had overlooked Fredllman's post when I made mine, or I wouldn't have made it. The same idea, and the Fredllman implementation is clearly better than mine.

[histrungalot]

Duoas: BOOM! Enjoyed!

[ascii]

Duoas, that is... what is that?

[Duthomhas]

What "that"?
That awful bignum I scrambled up so no one would consider it a work of art?
Or the fun thinking about how to calculate the answer to the OP's question?

Come to think of it, the log10() is not necessary, since we already know it from the user's input... and there are efficient integer pow() functions...

Let me check this out...


OK

//----------------------------------------------------------------------------
// JLBorges
unsigned long ndigits( unsigned long number )
{
    unsigned long digits = 0 ;
    unsigned long nd = 1 ;

    for( unsigned long i = 9 ; number > i ; i *= 10 )
    {
        digits += i*nd ; ++nd ; number -= i ;
    }

    return digits + number*nd ;
}

//----------------------------------------------------------------------------
// Fredllman
unsigned long numDigits( unsigned long n ) {
    unsigned long result = 0;
    
    for (unsigned long p = 1; p <= n; p *= 10) {
        result += n - p + 1;
    }
    
    return result;
}

//----------------------------------------------------------------------------
// Duoas
unsigned long ipow( unsigned long base, unsigned long exp )
  {
  unsigned long result = 1;
  while (exp)
    {
    if (exp & 1)
      result *= base;
    exp >>= 1;
    base *= base;
    }
  return result;
  }

unsigned long digits_in_1_to_N( unsigned long n, unsigned long w )
  {
  if (n == 0) return 0;

  n *= w;
  w -= 1;
  n -= (((ipow( 10, w ) - 1) / 9) * 10) - w;

  return n;
  }

D:\prog\nines\times> a
Calculate the number of digits needed to count from 1 to n.
n? 489564266
iterations? 100000000
JLBorges
489564266 --> 4294967292
time = 0:05.3663 = 0:00.0000 per iteration
Fredllman
489564266 --> 4294967292
time = 0:04.9295 = 0:00.0000 per iteration
Duoas
489564266 --> 4294967292
time = 0:03.0107 = 0:00.0000 per iteration

D:\prog\nines\times>

input digit count > 7: I win!
input digit count < 8: Fredllman wins!

Hmm... I suppose a "most efficient" program would choose which algorithm to apply based upon the digit-width of the input and/or failure due to machine word limitations.

...

[JLBorges]

I suppose a "most efficient" program would do a table look up based on the number of digits for the sum of the first n-1 terms and then another table lookup to help compute the last term. It would have no loops at all.

Edit: Come to think of it, how does one compute the number of digits without a loop? Unroll it, I suppose.

[JLBorges]

By using a lookup table we can reduce it to just (standard integral types)

a. O( log₃(D) ) integral comparisons where D is the maximum number of digits
b. One each of integral multiplication, addition and subtraction.

Example: For N < ten billion: 2 to 4 (average 3) comparisons, 1 subtraction, 1 multiplication, 1 addition (The rest of it is done at compile time).

#include <iostream>
#include <limits>

enum : long long { MAXDIGITS = std::numeric_limits<unsigned int>::digits10 } ;

template< unsigned int N > struct nines { enum : long long { value = nines<N-1>::value * 10 + 9 } ; } ;
template<> struct nines<1> { enum : long long { value = 9 } ; } ;
template<> struct nines<0> { enum : long long { value = 0 } ; } ;

template< unsigned int N > struct tens { enum : long long { value = tens<N-1>::value * 10 } ; } ;
template<> struct tens<1> { enum : long long { value = 10 } ; } ;
template<> struct tens<0> { enum : long long { value = 1 } ; } ;

template< unsigned int N > struct term { enum : long long { value = N * 9 * tens<N-1>::value } ; };
template<> struct term<1> { enum : long long { value = 9 } ; } ;

template< unsigned int N > struct sum_terms
{ enum : long long { value = sum_terms<N-1>::value + term<N>::value } ; };
template<> struct sum_terms<0> { enum : long long { value = 0 } ; } ;

template< unsigned int N > struct last_term
{
    unsigned long long operator() ( unsigned int n ) const
    { return ( n - nines<N-1>::value ) * N ; } };

template< unsigned int N > struct sum_plus_last_term
{
    unsigned long long operator() ( unsigned int n ) const
    { return sum_terms<N-1>::value + last_term<N>()(n) ; }
};

unsigned long long ndigits( unsigned int number )
{
    static_assert( std::numeric_limits<unsigned int>::digits10 < 10,
                   "this is example code for numbers smaller than 10 billion." ) ;

    if( number > nines<6>::value ) // 7,8,9 digits
        if( number > nines<8>::value ) // 9 digits
              return sum_plus_last_term<9>()(number) ;
        else if( number > nines<7>::value ) // 8 digits
              return sum_plus_last_term<8>()(number) ;
        else return sum_plus_last_term<7>()(number) ; // 7 digits

    else if( number > nines<3>::value ) // 4,5,6 digits
        if( number > nines<5>::value ) // 6 digits
              return sum_plus_last_term<6>()(number) ;
        else if( number > nines<4>::value ) // 5 digits
              return sum_plus_last_term<5>()(number) ;
        else return sum_plus_last_term<4>()(number) ; // 4 digits

    else // 1,2,3 digits
        if( number > nines<2>::value ) // 3 digits
              return sum_plus_last_term<3>()(number) ;
        else if( number > nines<1>::value ) // 2 digits
              return sum_plus_last_term<2>()(number) ;
        else return number ; // 1 digit
}

int main()
{
    std::cout << ndigits( std::numeric_limits<unsigned int>::max() ) << '\n' ;
}

[Duthomhas]

Nice!

[histrungalot]

JLBorges, I can't get that to build. What am I missing?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

g++ 1toN.cpp - - - - - - - - - - - - - > g++ -v Using built-in specs. Target: i686-apple-darwin10 Configured with: /var/tmp/gcc/gcc-5664~105/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 Thread model: posix gcc version 4.2.1 (Apple Inc. build 5664)

1toN.cpp:4: error: expected identifier before ‘:’ token 1toN.cpp:4: error: expected unqualified-id before ‘:’ token 1toN.cpp:6: error: expected identifier before ‘:’ token 1toN.cpp:6: error: expected primary-expression before ‘long’ 1toN.cpp:6: error: expected ‘;’ before ‘long’ 1toN.cpp:7: error: expected identifier before ‘:’ token 1toN.cpp:7: error: expected primary-expression before ‘long’ etc...

EDIT: Changed so line number matches yours

[Duthomhas]

You need to use the C++11 standard (-std=c++11 on the command line).

Your GCC is too old, so you can just hack out the stuff you don't need:
1 - get rid of the typed enum stuff enum : long long { ... } --> enum { ... }
2 - get rid of the static_assert

Good luck!

[histrungalot]

I thought it was that.
Done.
Thanks.

$ ./a.out
Calculate the number of digits needed to count from 1 to n.
n? 4294967295
(notice how n is now too big for the machine method to work properly?)
unsigned int calculated --> 41838561849
bignum calculated       --> 41838561849
$ g++ 1toN.cpp 
$ ./a.out
4183856185

They are not equal? Is that because of me?
EDIT: Should the bignum be correct?

[JLBorges]

If you have changed enum : long long { ... } to enum { ... }, you are creating an integer overflow. The number 41838561849 is outside the range of the C++98 enum.

#include <iostream>
#include <limits>

int main()
{
    std::cout << "max possible: " << std::numeric_limits<unsigned int>::max() << '\n' ;
    unsigned long result = 41838561849ULL ;
    // *** warning: large integer implicitly truncated to unsigned type [-Woverflow]
    std::cout << result << " (how could we expect the result to be 41838561849)\n" ;
}