Finding the number of digits of an integer

Question

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

I found this 3 main methods:

• conversion to string

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

• for the cycle

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

• logarithmic calculation

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

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

At first I thought that the string method is the dirtiest, but the more I think about it, the more I think this is the fastest way. Or that?

Answer 1

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; } 

Answer 2

I do not know, and the answer may be different depending on how your individual language is implemented.

So, the stress test! Implement all three solutions. Run them at 1-1000000 (or some other huge set of numbers that represent the numbers for which the solution will work) and the time during which each of them takes.

Use your decisions against each other and let them fight it. Like intelligent gladiators. Three algorithms come in! One algorithm goes away!

Answer 3

Well, the correct answer is to measure it, but you should be able to guess the number of processor steps involved in converting strings and going through them to find the end marker.

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

edit: spend some more time alone in the morning :-)

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

One of the problems with high-level languages ​​is to guess what kind of work the system does behind the scenes of a clearly simple operator. Mandatory Joel Link

This statement involves allocating memory for the string, and possibly a couple of temporary copies of the string. It should parse the integer and copy its numbers into a string, perhaps reallocate and move the existing memory if the number is large. You may need to check your locale settings to see if your country uses "," or ".". You may have to make a bunch of conversions in Unicode.
Then the length search should check the entire string, again looking at unicode and any local specific settings, such as - are you in the right-left language ?.

Alternatively:

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

Just because it will be harder for you to do this on paper does not mean that it is difficult for a computer! In fact, a good rule in high-performance computing, apparently, was - if something is difficult for a person (liquid dynamics, 3D rendering), it is easy for a computer, and if it is easy for a person (face recognition, voice detection in noisy room) it's hard for a computer!

You can usually assume that the built-in math functions are log / sin / cos, etc. have been an important part of computer design for 50 years. Therefore, even if they do not map directly to the hardware function in the FPU, you can bet that an alternative implementation is quite effective.

Answer 4

This algorithm may also be good, assuming that:

• Integer and binary encoding (<< operation is cheap)

• We do not know the bounds of number

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

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

As for the Log10 algorithm, it will give you only an approximate answer (which is close to real, but still), since the analytical formula for calculating the Log function has an infinite loop and cannot be accurately calculated in the Wiki .

Answer 5

Test conditions

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

results

digits: [1,10],

no. mileage: 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

LINE CONVERSION: 724 ms

LOGIC CALCULATION: 349 ms

DIV 10 Iteration: 229 ms

MANUAL AIR CONDITIONING: 136 ms

Note. The author refrains from 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)); } } } 

Answer 6

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

• for-loop: performs 2 mathematical operations: dividing the number by 10 and increasing the counter. Will work in O (n) for n = # digits.

• Logarithmic: it will call log10 and gender and add 1. It looks like O (1), but I'm not sure how fast the log10 or floor functions work. My knowledge of such things was atrophied with a lack of use, so there might be hidden complexity in these functions.

So, I guess what it comes down to: looking for digital mappings faster than a few math operations or something else in log10 ? The answer is likely to change. There may be platforms where character matching is faster, while others where calculations are performed are faster. You should also keep in mind that the first method will create a new String object that exists only for the purpose of obtaining the length. This will probably use more memory than the other two methods, but it may or may not matter.

Answer 7

Obviously, you can exclude method 1 from the competition because the atoi / toString algorithm used will be similar to method 2.

The speed of method 3 depends on whether the code is compiled for a system whose instruction set contains database 10.

Answer 8

Use the simplest solution in any programming language that you use. I can’t think of a case where counting integers would be a 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 

Answer 9

For very large integers, the log method is much faster. For example, with the number of the number 2491327 (the number 11920928 of the Fibonacci number, if you are interested), Python takes several minutes to execute the "divide by 10" algorithm and milliseconds to execute 1+floor(log(n,10)) .

Answer 10

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

Answer 11

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

Your method No. 1 (strings): Everything related to the round-trip conversion between strings and numbers is usually very slow.

Repeat your method # 2 (temp / = 10): this is a fatal flaw, since it is assumed that x / 10 always means "x divided by 10". But in many programming languages ​​(for example, C, C ++), if "x" is an integer type, then "x / 10" means "integer division", which is not the same as floating point division, and it introduces errors rounding off at each iteration, and they accumulate in a recursive formula, such as your solution # 2.

Recall your method # 3 (logs): it is buggy for large numbers (at least in C, and possibly in other languages), because floating-point data types tend to not be as accurate as 64-bit integers numbers.

Therefore, I do not like all 3 of these methods: # 1 works, but it works slowly, # 2 does not work, and # 3 is buggy for large numbers. Instead, I prefer this, which works for numbers from 0 to 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; } 

Answer 12

Keep it simple:

 long long int a = 223452355415634664; int x; for (x = 1; a >= 10; x++) { a = a / 10; } printf("%d", x); 

Answer 13

You can use a recursive solution instead of a loop, but something like this:

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

With long images, the picture can change - measure small and long numbers regardless of different algorithms and choose 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 for a simple 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 about code size optimization, but I know premature optimization ...

Answer 14

Here is a dimension in Swift 4.

Algorithm 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))") 

Exit

timeInterval0: 1.92149806022644

timeInterval1: 0.557608008384705

timeInterval2: 2.83262193202972

Based on this, String Conversion is the best option for Swift.

Answer 15

I was curious to know the results of @ daniel.sedlacek, so I did some testing using Swift for numbers having more than 10 digits. I ran the following script on 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 items

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

Answer 16

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

Where x is the base and n is the number.