Shahid Pathan

Greenhorn

Posts: 23

Loic Beylot

Greenhorn

Posts: 8

Campbell Ritchie

Marshal

Posts: 56562

172

posted 6 years ago

you should not go around at this early stage worrying too much about performance. The best way to improve the performance, making the loop run hundreds of times faster, is to remove the print instructions from it. Add the Strings to a StringBulider and then the loop will run in a few microseconds rather than anything up to a second. You will of course need a few milliseconds afterwards to print the result.

I like the idea of a logarithm, however. That is a much better idea which will generalise the loop and allow it to accept numbers of any size.

I like the idea of a logarithm, however. That is a much better idea which will generalise the loop and allow it to accept numbers of any size.

posted 6 years ago

Using a floating point logarithm to count integer digits happens to work for ints in Java using the Math.log10() method, but this approach is not theoretically sound e.g. it fails on corner cases for Longs (see bolded results at bottom):

Results:

Results:

`i - 1 = 9 has 1 digits`

(int)log10(i - 1) + 1 = 1

i = 10 has 2 digits

(int)log10(i) + 1 = 2

i - 1 = 99 has 2 digits

(int)log10(i - 1) + 1 = 2

i = 100 has 3 digits

(int)log10(i) + 1 = 3

i - 1 = 999 has 3 digits

(int)log10(i - 1) + 1 = 3

i = 1000 has 4 digits

(int)log10(i) + 1 = 4

i - 1 = 9999 has 4 digits

(int)log10(i - 1) + 1 = 4

i = 10000 has 5 digits

(int)log10(i) + 1 = 5

i - 1 = 99999 has 5 digits

(int)log10(i - 1) + 1 = 5

i = 100000 has 6 digits

(int)log10(i) + 1 = 6

i - 1 = 999999 has 6 digits

(int)log10(i - 1) + 1 = 6

i = 1000000 has 7 digits

(int)log10(i) + 1 = 7

i - 1 = 9999999 has 7 digits

(int)log10(i - 1) + 1 = 7

i = 10000000 has 8 digits

(int)log10(i) + 1 = 8

i - 1 = 99999999 has 8 digits

(int)log10(i - 1) + 1 = 8

i = 100000000 has 9 digits

(int)log10(i) + 1 = 9

i - 1 = 999999999 has 9 digits

(int)log10(i - 1) + 1 = 9

i = 1000000000 has 10 digits

(int)log10(i) + 1 = 10

i - 1 = 9999999999 has 10 digits

(int)log10(i - 1) + 1 = 10

i = 10000000000 has 11 digits

(int)log10(i) + 1 = 11

i - 1 = 99999999999 has 11 digits

(int)log10(i - 1) + 1 = 11

i = 100000000000 has 12 digits

(int)log10(i) + 1 = 12

i - 1 = 999999999999 has 12 digits

(int)log10(i - 1) + 1 = 12

i = 1000000000000 has 13 digits

(int)log10(i) + 1 = 13

i - 1 = 9999999999999 has 13 digits

(int)log10(i - 1) + 1 = 13

i = 10000000000000 has 14 digits

(int)log10(i) + 1 = 14

i - 1 = 99999999999999 has 14 digits

(int)log10(i - 1) + 1 = 14

i = 100000000000000 has 15 digits

(int)log10(i) + 1 = 15

i = 1000000000000000 has 16 digits

(int)log10(i) + 1 = 16

i = 10000000000000000 has 17 digits

(int)log10(i) + 1 = 17

i = 100000000000000000 has 18 digits

(int)log10(i) + 1 = 18(int)log10(i - 1) + 1 = 1

i = 10 has 2 digits

(int)log10(i) + 1 = 2

i - 1 = 99 has 2 digits

(int)log10(i - 1) + 1 = 2

i = 100 has 3 digits

(int)log10(i) + 1 = 3

i - 1 = 999 has 3 digits

(int)log10(i - 1) + 1 = 3

i = 1000 has 4 digits

(int)log10(i) + 1 = 4

i - 1 = 9999 has 4 digits

(int)log10(i - 1) + 1 = 4

i = 10000 has 5 digits

(int)log10(i) + 1 = 5

i - 1 = 99999 has 5 digits

(int)log10(i - 1) + 1 = 5

i = 100000 has 6 digits

(int)log10(i) + 1 = 6

i - 1 = 999999 has 6 digits

(int)log10(i - 1) + 1 = 6

i = 1000000 has 7 digits

(int)log10(i) + 1 = 7

i - 1 = 9999999 has 7 digits

(int)log10(i - 1) + 1 = 7

i = 10000000 has 8 digits

(int)log10(i) + 1 = 8

i - 1 = 99999999 has 8 digits

(int)log10(i - 1) + 1 = 8

i = 100000000 has 9 digits

(int)log10(i) + 1 = 9

i - 1 = 999999999 has 9 digits

(int)log10(i - 1) + 1 = 9

i = 1000000000 has 10 digits

(int)log10(i) + 1 = 10

i - 1 = 9999999999 has 10 digits

(int)log10(i - 1) + 1 = 10

i = 10000000000 has 11 digits

(int)log10(i) + 1 = 11

i - 1 = 99999999999 has 11 digits

(int)log10(i - 1) + 1 = 11

i = 100000000000 has 12 digits

(int)log10(i) + 1 = 12

i - 1 = 999999999999 has 12 digits

(int)log10(i - 1) + 1 = 12

i = 1000000000000 has 13 digits

(int)log10(i) + 1 = 13

i - 1 = 9999999999999 has 13 digits

(int)log10(i - 1) + 1 = 13

i = 10000000000000 has 14 digits

(int)log10(i) + 1 = 14

i - 1 = 99999999999999 has 14 digits

(int)log10(i - 1) + 1 = 14

i = 100000000000000 has 15 digits

(int)log10(i) + 1 = 15

i - 1 = 999999999999999 has 15 digits

(int)log10(i - 1) + 1 = 16i - 1 = 999999999999999 has 15 digits

(int)log10(i - 1) + 1 = 16

i = 1000000000000000 has 16 digits

(int)log10(i) + 1 = 16

i - 1 = 9999999999999999 has 16 digits

(int)log10(i - 1) + 1 = 17i - 1 = 9999999999999999 has 16 digits

(int)log10(i - 1) + 1 = 17

i = 10000000000000000 has 17 digits

(int)log10(i) + 1 = 17

i - 1 = 99999999999999999 has 17 digits

(int)log10(i - 1) + 1 = 18i - 1 = 99999999999999999 has 17 digits

(int)log10(i - 1) + 1 = 18

i = 100000000000000000 has 18 digits

(int)log10(i) + 1 = 18

Campbell Ritchie

Marshal

Posts: 56562

172

posted 6 years ago

I'm not referring to the mathematical theory, rather the theory behind using floating point operations for this kind of thing. It may happen to work for Java using ints, but as I showed it doesn't work for Longs, and it might not work for Type X in Language Y in 5 years' time, which makes it bad programming practice in my book. Besides, it probably slower than an integer-based method that you can guarantee always works.

Shahid Pathan

Greenhorn

Posts: 23

Shahid Pathan

Greenhorn

Posts: 23

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 6 years ago

Well, I agree with Campbell that optimizing in this way seems like a bad idea, as the printing is likely to be much slower than the math operations you're worrying over. For that matter, the string concatenation is probably slower as well, though not as slow as the printing.

Nonetheless, here's my quick attempt to solve the original problem with a minimum of performance bottlenecks. I don't care enough about this to test whether the way I'm using System.out is actually optimal or not. If it isn't, maybe try using a BufferedWriter around an OutputStreamWriter around System.out.

I intentionally omitted the initial 0 because (a) it doesn't fit into the rest of the algorithm, and (b) it seems silly to describe the number of digits in zero. If you care, add this at the beginning:

Nonetheless, here's my quick attempt to solve the original problem with a minimum of performance bottlenecks. I don't care enough about this to test whether the way I'm using System.out is actually optimal or not. If it isn't, maybe try using a BufferedWriter around an OutputStreamWriter around System.out.

I intentionally omitted the initial 0 because (a) it doesn't fit into the rest of the algorithm, and (b) it seems silly to describe the number of digits in zero. If you care, add this at the beginning:

posted 6 years ago

You should really do some benchmarking before making incorrect statements like this. I timed your method by running it 100000 times and found that even if you take out the printlns and stick the strings in an array instead, about 95% of the run time is spent building the strings. And the time taken (slightly surprisingly to me) is more or less proportional to the length of the strings you use. But this in turn will be tiny compared with the time it'll take to do anything with them, like output to the console, so "optimising" your conditional statements is irrelevant in any practical situation since it has an unmeasurably small effect. If you want to speed up your method (which is kind of pointless when you have I/O in there), stop worrying about conditionals and focus on avoiding string concatenation like Mike does above.

Shahid Pathan wrote:However the performance is low,

You should really do some benchmarking before making incorrect statements like this. I timed your method by running it 100000 times and found that even if you take out the printlns and stick the strings in an array instead, about 95% of the run time is spent building the strings. And the time taken (slightly surprisingly to me) is more or less proportional to the length of the strings you use. But this in turn will be tiny compared with the time it'll take to do anything with them, like output to the console, so "optimising" your conditional statements is irrelevant in any practical situation since it has an unmeasurably small effect. If you want to speed up your method (which is kind of pointless when you have I/O in there), stop worrying about conditionals and focus on avoiding string concatenation like Mike does above.