Finding the number of digits of an integer

Question

What is the best method to find the number of digits of a positive integer?

I have found this 3 basic methods:

• conversion to string

  String s = new Integer(t).toString(); 
  int len = s.length();
  

• for loop

  for(long long int temp = number; temp >= 1;)
  {
      temp/=10;
      decimalPlaces++;
  } 
  

• logaritmic calculation

  digits = floor( log10( number ) ) + 1;
  

where you can calculate log10(x) = ln(x) / ln(10) in most languages.

First I thought the string method is the dirtiest one but the more I think about it the more I think it's the fastest way. Or is it?

Megasporophyll

Define "best", first. Then picking the "best" algorithm is easy. – Mcclees

Use the source, Luke: docjar.com/html/api/java/lang/Integer.java.html – Karsten

This question probably belongs on codegolf. – Excitor

It seems nobody here has any consideration for non-base-10 integers. Not using Integer.toString(t, radix), temp /= radix; (and correspondingly, numDigits++;, as it's generalizing from decimal), or ln(x) / ln(radix)... – Blankly

I can't imagine anything would beat using logarithms. No data conversion, no loops, just a simple, straightforward calculation. – Aufmann

@TMN: It's not straightforward when you don't have a log10 function, or when you have to think about the effects of precision loss and prove that your formula will always return the correct result for values in a given range. – Almuce

How can you expect to solve the question with thinking? You should think about measuring. – Alejandraalejandrina

You are right in many aspects, I didn't define the "best" condition and I should have done the comparison firs (later I did my homework, see below), however this discussion brought lots of good ideas ;) – Megasporophyll

@Joey Adams: Any logarithm will do. For example, log10(x) = ln(x)/ln(10). – Britneybritni

@Jean-François Corbett: Indeed, that's correct in a mathematical sense. But are you 100% confident it will work correctly with the machine's floating point arithmetic? – Almuce

@Joey Adams: Good point... well, I'm floating point ln(e) confident. – Britneybritni

for integers: floor(ln(n + 0.5) / ln(10)) might help with precision loss... – Sonde

Answer 1

There's always this method:

n = 1;
if ( i >= 100000000 ) { n += 8; i /= 100000000; }
if ( i >= 10000     ) { n += 4; i /= 10000; }
if ( i >= 100       ) { n += 2; i /= 100; }
if ( i >= 10        ) { n += 1; }

Quintile

If you know something about the range of integers that need to be supported, this can be very efficient. – Gorgonzola

@jimreed: Right. You need to know ceil(log2(log10(MAXINT))). Then it does at most that number of truncating divisions. – Quintile

Or if this is a real coding issue and not just a puzzle, and you know your integer is always less than 10,000 then you don't even need the first two if statements. – Gorgonzola

Answer 2

Well the correct answer would be to measure it - but you should be able to make a guess about the number of CPU steps involved in converting strings and going through them looking for an end marker

Then think how many FPU operations/s your processor can do and how easy it is to calculate a single log.

edit: wasting some more time on a monday morning :-)

String s = new Integer(t).toString(); 
int len = s.length();

One of the problems with high level languages is guessing how much work the system is doing behind the scenes of an apparently simple statement. Mandatory Joel link

This statement involves allocating memory for a string, and possibly a couple of temporary copies of a string. It must parse the integer and copy the digits of it into a string, possibly having to reallocate and move the existing memory if the number is large. It might have to check a bunch of locale settings to decide if your country uses "," or ".", it might have to do a bunch of unicode conversions.
Then finding the length has to scan the entire string, again considering unicode and any local specific settings such as - are you in a right->left language?.

Alternatively:

digits = floor( log10( number ) ) + 1;

Just because this would be harder for you to do on paper doesn't mean it's hard for a computer! In fact a good rule in high performance computing seems to have been - if something is hard for a human (fluid dynamics, 3d rendering) it's easy for a computer, and if it's easy for a human (face recognition, detecting a voice in a noisy room) it's hard for a computer!

You can generally assume that the builtin maths functions log/sin/cos etc - have been an important part of computer design for 50years. So even if they don't map directly into a hardware function in the FPU you can bet that the alternative implementation is pretty efficient.

Hurling

@PMF …or ValueError or nasal demons. So the answer is floor(log10(number || 1)) + 1 or, more explicitly: (number == 0) ? 1 : (floor(log10(number)) + 1) – Ignorant

why not use ceil() rather than floor() + 1? – Paulsen

@JosieThompson ceil(0) = 0 while floor(0)+1 = 1. – Hurling

I created a little script in OCaml to test different methods (string, recursion, loop, log) and it came out that log is fastest. In order from fastest to slowest: (1) log, (2) string, (3) recursion, (4) loop. – Rojas

Answer 3

I don't know, and the answer may well be different depending on how your individual language is implemented.

So, stress test it! Implement all three solutions. Run them on 1 through 1,000,000 (or some other huge set of numbers that's representative of the numbers the solution will be running against) and time how long each of them takes.

Pit your solutions against one another and let them fight it out. Like intellectual gladiators. Three algorithms enter! One algorithm leaves!

Bacteriology

Answer 4

This algorithm might be good also, assuming that:

• Number is integer and binary encoded (<< operation is cheap)

• We don't known number boundaries

  var num = 123456789L;
  var len = 0;
  var tmp = 1L;
  while(tmp < num)
  {
      len++;
      tmp = (tmp << 3) + (tmp << 1);
  }
  

This algorithm, should have speed comparable to for-loop (2) provided, but a bit faster due to (2 bit-shifts, add and subtract, instead of division).

As for Log10 algorithm, it will give you only approximate answer (that is close to real, but still), since analytic formula for computing Log function have infinite loop and can't be calculated precisely Wiki.

Sw

We only need the integer part of the logarithm here, which makes the "infinite loop" void. – Ciaracibber

Yes, you are right, it makes computation finite, but still it seems expensive for small numbers. – Sw

Should not that be: tmp += (tmp << 3) + (tmp << 1); ? – Collimator

This actually doesn't calculate correctly if the input number is divisible by 10. To fix it, you should increment the digit length by 1 if the number is divisible by 10. – Kenaz

If anyone is wondering about the << shifts, it is similar to tmp = tmp * 8 + tmp * 2. Multiplication used to cost few times more than basic operations but on modern processors it can take about the same time, so tmp *= 10; might end up a tiny bit faster lemire.me/blog/2010/07/19/… – Bracteate

@mmstick No not for numbers divisible by 10, this algorithm fails only for all powers of 10 (including 1) and 0. It gives correct answer for 20, 30, 40 etc. – Bedsore

Answer 5

Test conditions

• Decimal numeral system
• Positive integers
• Up to 10 digits
• Language: ActionScript 3

Results

digits: [1,10],

no. of runs: 1,000,000

random sample: 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2

result: 7,8,6,6,3,8,3,4,6,1

CONVERSION TO STRING: 724ms

LOGARITMIC CALCULATION: 349ms

DIV 10 ITERATION: 229ms

MANUAL CONDITIONING: 136ms

Note: Author refrains from making any conclusions for numbers with more than 10 digits.

---

Script

package {
    import flash.display.MovieClip;
    import flash.utils.getTimer;
    /**
     * @author Daniel
     */
    public class Digits extends MovieClip {
        private const NUMBERS : uint = 1000000;
        private const DIGITS : uint = 10;

        private var numbers : Array;
        private var digits : Array;

        public function Digits() {
            // ************* NUMBERS *************
            numbers = [];
            for (var i : int = 0; i < NUMBERS; i++) {
                var number : Number = Math.floor(Math.pow(10, Math.random()*DIGITS));
                numbers.push(number);
            }   
            trace('Max digits: ' + DIGITS + ', count of numbers: ' + NUMBERS);
            trace('sample: ' + numbers.slice(0, 10));

            // ************* CONVERSION TO STRING *************
            digits = [];
            var time : Number = getTimer();

            for (var i : int = 0; i < numbers.length; i++) {
                digits.push(String(numbers[i]).length);
            }

            trace('\nCONVERSION TO STRING - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* LOGARITMIC CALCULATION *************
            digits = [];
            time = getTimer();

            for (var i : int = 0; i < numbers.length; i++) {
                digits.push(Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1);
            }

            trace('\nLOGARITMIC CALCULATION - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* DIV 10 ITERATION *************
            digits = [];
            time = getTimer();

            var digit : uint = 0;
            for (var i : int = 0; i < numbers.length; i++) {
                digit = 0;
                for(var temp : Number = numbers[i]; temp >= 1;)
                {
                    temp/=10;
                    digit++;
                } 
                digits.push(digit);
            }

            trace('\nDIV 10 ITERATION - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* MANUAL CONDITIONING *************
            digits = [];
            time = getTimer();

            var digit : uint;
            for (var i : int = 0; i < numbers.length; i++) {
                var number : Number = numbers[i];
                if (number < 10) digit = 1;
                else if (number < 100) digit = 2;  
                else if (number < 1000) digit = 3;  
                else if (number < 10000) digit = 4;  
                else if (number < 100000) digit = 5;  
                else if (number < 1000000) digit = 6;  
                else if (number < 10000000) digit = 7;  
                else if (number < 100000000) digit = 8;  
                else if (number < 1000000000) digit = 9;  
                else if (number < 10000000000) digit = 10;  
                digits.push(digit);
            }

            trace('\nMANUAL CONDITIONING: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));
        }
    }
}

Megasporophyll

Thanks for running all these tests; it was very helpful! Of course the exact speed will vary between environments, but this is a great overview of what to expect and how to go about doing it. – Maximamaximal

You're missing the option of calculating the digits by using a loop of bit shifts instead of division. – Kenaz

Answer 6

Regarding the three methods you propose for "determining the number of digits necessary to represent a given number in a given base", I don't like any of them, actually; I prefer the method I give below instead.

Re your method #1 (strings): Anything involving converting back-and-forth between strings and numbers is usually very slow.

Re your method #2 (temp/=10): This is fatally flawed because it assumes that x/10 always means "x divided by 10". But in many programming languages (eg: C, C++), if "x" is an integer type, then "x/10" means "integer division", which isn't the same thing as floating-point division, and it introduces round-off errors at every iteration, and they accumulate in a recursive formula such as your solution #2 uses.

Re your method #3 (logs): it's buggy for large numbers (at least in C, and probably other languages as well), because floating-point data types tend not to be as precise as 64-bit integers.

Hence I dislike all 3 of those methods: #1 works but is slow, #2 is broken, and #3 is buggy for large numbers. Instead, I prefer this, which works for numbers from 0 up to about 18.44 quintillion:

unsigned NumberOfDigits (uint64_t Number, unsigned Base)
{
   unsigned Digits = 1;
   uint64_t Power  = 1;
   while ( Number / Power >=  Base )
   {
      ++Digits;
      Power *= Base;
   }
   return Digits;
}

Fatigue

Answer 7

• conversion to string: This will have to iterate through each digit, find the character that maps to the current digit, add a character to a collection of characters. Then get the length of the resulting String object. Will run in O(n) for n=#digits.

• for-loop: will perform 2 mathematical operation: dividing the number by 10 and incrementing a counter. Will run in O(n) for n=#digits.

• logarithmic: Will call log10 and floor, and add 1. Looks like O(1) but I'm not really sure how fast the log10 or floor functions are. My knowledge of this sort of things has atrophied with lack of use so there could be hidden complexity in these functions.

So I guess it comes down to: is looking up digit mappings faster than multiple mathematical operations or whatever is happening in log10? The answer will probably vary. There could be platforms where the character mapping is faster, and others where doing the calculations is faster. Also to keep in mind is that the first method will creats a new String object that only exists for the purpose of getting the length. This will probably use more memory than the other two methods, but it may or may not matter.

Meritorious

The conversion to string will likely also do something like the second loop internally. – Ciaracibber

Answer 8

You can obviously eliminate the method 1 from the competition, because the atoi/toString algorithm it uses would be similar to method 2.

Method 3's speed depends on whether the code is being compiled for a system whose instruction set includes log base 10.

Gladwin

Answer 9

Use the simplest solution in whatever programming language you're using. I can't think of a case where counting digits in an integer would be the bottleneck in any (useful) program.

C, C++:

char buffer[32];
int length = sprintf(buffer, "%ld", (long)123456789);

Haskell:

len = (length . show) 123456789

JavaScript:

length = String(123456789).length;

PHP:

$length = strlen(123456789);

Visual Basic (untested):

length = Len(str(123456789)) - 1

Almuce

If the number of digits is known and relatively low then I can only agree with you. – Megasporophyll

R: nchar(123456789) – Ignorant

Answer 10

For very large integers, the log method is much faster. For instance, with a 2491327 digit number (the 11920928th Fibonacci number, if you care), Python takes several minutes to execute the divide-by-10 algorithm, and milliseconds to execute 1+floor(log(n,10)).

Sincere

Answer 11

import math
def numdigits(n):
    return ( int(math.floor(math.log10(n))) + 1 )

Dogcatcher

you mean int(math.floor(math.log10(n or 1))) + 1, as log10(0) raises ValueError and ceil(log10(1)), ceil(log10(10)), ... is 0, 1, ... while floor(...) + 1 is the correct value. – Ignorant

It does not work for for 999999999999999 (15 digits), return 16 – Kobarid

Answer 12

Keep it simple:

long long int a = 223452355415634664;

int x;
for (x = 1; a >= 10; x++)
{
   a = a / 10;
}

printf("%d", x);

Camarillo

Answer 13

You can use a recursive solution instead of a loop, but somehow similar:

@tailrec
def digits (i: Long, carry: Int=1) : Int =  if (i < 10) carry else digits (i/10, carry+1)

digits (8345012978643L)

With longs, the picture might change - measure small and long numbers independently against different algorithms, and pick the appropriate one, depending on your typical input. :)

Of course nothing beats a switch:

switch (x) {
  case 0:  case 1:  case 2:  case 3:  case 4:  case 5:  case 6:  case 7:  case 8:  case 9: return 1;
  case 10: case 11: // ...
  case 99: return 2;
  case 100: // you get the point :) 
  default: return 10; // switch only over int
}

except a plain-o-array:

   int [] size = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,... };
   int x = 234561798;
   return size [x];

Some people will tell you to optimize the code-size, but yaknow, premature optimization ...

Alejandraalejandrina

Answer 14

log(x,n)-mod(log(x,n),1)+1

Where x is a the base and n is the number.

Shaunda

I used this formula in my experiment "Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1" and there were much faster methods. – Megasporophyll

Answer 15

Here is the measurement in Swift 4.

Algorithms code:

extension Int {
    var numberOfDigits0: Int {
        var currentNumber = self
        var n = 1
        if (currentNumber >= 100000000) {
            n += 8
            currentNumber /= 100000000
        }
        if (currentNumber >= 10000) {
            n += 4
            currentNumber /= 10000
        }
        if (currentNumber >= 100) {
            n += 2
            currentNumber /= 100
        }
        if (currentNumber >= 10) {
            n += 1
        }
        return n
    }

    var numberOfDigits1: Int {
        return String(self).count
    }

    var numberOfDigits2: Int {
        var n = 1
        var currentNumber = self
        while currentNumber > 9 {
            n += 1
            currentNumber /= 10
        }
        return n
    }

}

Measurement code:

var timeInterval0 = Date()
for i in 0...10000 {
    i.numberOfDigits0
}
print("timeInterval0: \(Date().timeIntervalSince(timeInterval0))")

var timeInterval1 = Date()
for i in 0...10000 {
    i.numberOfDigits1
}
print("timeInterval1: \(Date().timeIntervalSince(timeInterval1))")

var timeInterval2 = Date()
for i in 0...10000 {
    i.numberOfDigits2
}
print("timeInterval2: \(Date().timeIntervalSince(timeInterval2))")

Output

timeInterval0: 1.92149806022644

timeInterval1: 0.557608008384705

timeInterval2: 2.83262193202972

On this measurement basis String conversion is the best option for the Swift language.

Cathrine

Answer 16

I was curious after seeing @daniel.sedlacek results so I did some testing using Swift for numbers having more than 10 digits. I ran the following script in the playground.

let base = [Double(100090000000), Double(100050000), Double(100050000), Double(100000200)]
var rar = [Double]()
for i in 1...10 {
    for d in base {
        let v = d*Double(arc4random_uniform(UInt32(1000000000)))
        rar.append(v*Double(arc4random_uniform(UInt32(1000000000))))
        rar.append(Double(1)*pow(1,Double(i)))
    }
}

print(rar)

var timeInterval = NSDate().timeIntervalSince1970

for d in rar {
    floor(log10(d))
}

var newTimeInterval = NSDate().timeIntervalSince1970

print(newTimeInterval-timeInterval)


timeInterval = NSDate().timeIntervalSince1970
for d in rar {
    var c = d
    while c > 10 {
        c = c/10
    }
}

newTimeInterval = NSDate().timeIntervalSince1970

print(newTimeInterval-timeInterval)

Results of 80 elements

0.105069875717163 for floor(log10(x))
0.867973804473877 for div 10 iterations

Selmore

Answer 17

Adding one more approach to many of the already mentioned approaches. The idea is to use binarySearch on an array containing the range of integers based on the digits of the int data type.
The signature of Java Arrays class binarySearch is :
binarySearch(dataType[] array, dataType key) which returns the index of the search key, if it is contained in the array; otherwise, (-(insertion point) – 1).
The insertion point is defined as the point at which the key would be inserted into the array.
Below is the implementation:

    static int [] digits = {9,99,999,9999,99999,999999,9999999,99999999,999999999,Integer.MAX_VALUE};
    static int digitsCounter(int N)
    {
        int digitCount = Arrays.binarySearch(digits , N<0 ? -N:N);
        return 1 + (digitCount < 0 ? ~digitCount : digitCount);
    }

Please note that the above approach only works for : Integer.MIN_VALUE <= N <= Integer.MAX_VALUE, but can be easily extended for Long data type by adding more values to the digits array.

---

For example,
I) for N = 555, digitCount = Arrays.binarySearch(digits , 555) returns -3 (-(2)-1) as it's not present in the array but is supposed to be inserted at point 2 between 9 & 99 like [9, 55, 99].
As the index we got is negative we need to take the bitwise compliment of the result. At last, we need to add 1 to the result to get the actual number of digits in the number N.

Cabanatuan

Answer 18

In Swift 5.x, you get the number of digit in integer as below :

1. Convert to string and then count number of character in string

    let nums = [1, 7892, 78, 92, 90]
    for i in nums {
      let ch = String(describing: i)
      print(ch.count)
    }

2. Calculating the number of digits in integer using loop

    var digitCount = 0
   for i in nums {
     var tmp = i
     while tmp >= 1 {
       tmp /= 10
       digitCount += 1
     }
     print(digitCount)
   }

Selhorst

Answer 19

let numDigits num =
    let num = abs(num)
    let rec numDigitsInner num =
        match num with
        | num when num < 10 -> 1
        | _ -> 1 + numDigitsInner (num / 10)
    numDigitsInner num

F# Version, without casting to a string.

Seurat