Can the number of digits be Math.log10 (x) .floor + 1?

This article assumes Ruby, but I think the same can be said for many languages.

What are you talking about?

There are many ways to find out how many digits a positive integer x will be in decimal. One of them

Math.log10(x).floor + 1

However, is it really possible to get the correct answer? Even if you are not good at math, look at it as carefully as possible so that you can understand it even if you do not know much about Ruby.

However, if you just want to know the conclusion, [Is that okay? [#% E3% 81% 9D% E3% 82% 8C% E3% 81% A7% E3% 81% 84% E3% 81% 84% E3% 81% AE% E3% 81% 8B) ..

Various ways to find the number of digits

In this section, it is assumed that the local variable x is assigned a positive integer. Ruby can handle any large integer if conditions such as memory allow it.

Stringification

For Ruby integers (Integer class), generate a number string expressed in N-ary notation [Integer # to_s](https://docs.ruby-lang.org/ja/2.7.0/method/Integer/i There is a method called /inspect.html).

If you omit the argument, you get a sequence of numbers in decimal notation.

p (36 + 72).to_s # => "108"

On the other hand, in the String class, there is a method called String # length that counts the length (number of characters). There is.

p "Ruby".length # => 4

If you combine this

x.to_s.length

You can get the number of digits with. It's pretty easy.

However, I feel a little uneasy. Isn't it slow to create a huge string with a length of 100,000 for an integer of 100,000 digits when you just want to know the number of digits? It's actually pretty fast, but let's leave that story aside.

Get an array of digit-by-digit numbers

Ruby returns an array of the number of each digit when a non-negative integer (integer greater than or equal to 0) is expressed in N-ary notation Integer # digits There is a method called /2.7.0/method/Integer/i/digits.html).

If the argument is omitted, it is in decimal notation.

p 1234.digits # => [4, 3, 2, 1]

Since they are arranged in order from the bottom, the order of appearance is reversed.

If you use this and Array # length that returns the length of the array

x.digits.length

You can get the number of digits with.

Mystery thought, "It seems that integers are faster than strings, so why not be faster than x.to_s.length? ", But that was not the case. That's right. A huge array is created.

And Math.log10 (x) .floor + 1

There are other ways, but the main subject

Math.log10(x).floor + 1

Let's go to. Why does this give me the number of digits in x?

Math.log10 is a method that returns the common logarithm value of the given argument.

Common logarithm function

y = \log_{10}x

Is an exponential function with 10 as base </ ruby>

x = 10^y

It was the inverse function of. This exponential function is easy to understand when $ y $ is an integer, but it is also defined for any real number.

Let's look at when $ y $ is an integer greater than or equal to 0

y = \log_{10}x x = 10^y
0 1
1 10
2 100
3 1000
4 10000

If you look at this, you can see that when $ y $ is an integer greater than or equal to 0, $ y + 1 $, that is, $ \ log_ {10} (x) + 1 $ is the number of digits.

However, $ x $, where $ y $ is an integer, is limited. What about the more common positive integer $ x $?

As a trial, consider $ x = 999 $. This is a little less than $ 1000 . Since the logarithmic function increases monotonically ( y $ increases as $ x $ increases), $ \ log_ {10} 999 $ should be ** a little smaller ** than $ 3 $. Therefore, if you convert it to an integer with ** truncation **, you will get $ 2 $.

Let's use the floor floor </ ruby> function for truncation. This truncates the odds to the left of the number line (negative infinity). In this case, negative numbers do not appear, so you can think of it as "decimal part truncation" [^ fl].

[^ fl]: Note that for negative numbers, -1.1.floor is -2, not -1 with the decimal part truncated.

By the way, in mathematical symbols, it seems that the floor function is written as $ \ lfloor a \ rfloor $, but from the above consideration, when $ x $ is $ 100 $ or more and $ 999 $ or less,

\lfloor \log_{10}x \rfloor

Turns out to be all $ 2 $. In other words, it looks like this.

x \lfloor \log_{10}x \rfloor
19 0
1099 1
100999 2
10009999 3
1000099999 4

Therefore, the number of digits can be obtained by adding 1 to $ \ floorloor \ log_ {10} x \ rfloor + 1 $. Mathematically.

Is that ok?

Finally at the core.

If you write $ \ floorloor \ log_ {10} x \ rfloor + 1 $ in Ruby code

Math.log10(x).floor + 1

However, I feel a little uneasy. That was the point of this article.

That's because Math.log10 is a floating point operation of the Float class. Floating-point arithmetic usually involves errors. Is it possible that the resulting digits will be out of order due to subtle errors?

What should I think about?

Looking at the positive integer x in the order of 1, 2, 3, ..., where does the digit change? Of course, it's 9 → 10 or 99 → 100 or 999 → 1000. If an error in floating-point arithmetic gives an incorrect result, it is probably around this boundary. It is possible that something like 10000000 is mistakenly made one less digit, or something like 9999999999 is mistakenly made one more digit. Of these, numbers such as 1000000 are originally in the form of $ 10 ^ k $, so I feel that errors are unlikely to occur. Then, let's experiment with the number of 9s.

Yes, I wrote this code.

1.upto(100) do |k|
  puts "%3d %3d" % [k, Math.log10(10 ** k - 1).floor + 1]
end

Change $ k $ from 1 to 100 to calculate the digits of $ 10 ^ k -1 $ (that is, the number of 9s arranged in $ k $). Display this side by side with $ k $. It's a mathematical match, so see if the same numbers are lined up.

The result is as follows

  1   1
  2   2
  3   3
  4   4
  5   5
  6   6
  7   7
  8   8
  9   9
 10  10
 11  11
 12  12
 13  13
 14  14
 15  16
 16  17
 17  18
 18  19
 19  20
 20  21
 21  22
 22  23
 23  24
 24  25
 25  26
 26  27
 27  28
 28  29
 29  30
 30  31
 31  32
 32  33
 33  34
 34  35
 35  36
 36  37
 37  38
 38  39
 39  40
 40  41
 41  42
 42  43
 43  44
 44  45
 45  46
 46  47
 47  48
 48  49
 49  50
 50  51
 51  52
 52  53
 53  54
 54  55
 55  56
 56  57
 57  58
 58  59
 59  60
 60  61
 61  62
 62  63
 63  64
 64  65
 65  66
 66  67
 67  68
 68  69
 69  70
 70  71
 71  72
 72  73
 73  74
 74  75
 75  76
 76  77
 77  78
 78  79
 79  80
 80  81
 81  82
 82  83
 83  84
 84  85
 85  86
 86  87
 87  88
 88  89
 89  90
 90  91
 91  92
 92  93
 93  94
 94  95
 95  96
 96  97
 97  98
 98  99
 99 100
100 101

It is off the middle. Here is an excerpt.

 14  14
 15  16

Up to $ 10 ^ {14} ―― 1 $ can be calculated correctly, but at $ 10 ^ {15} ―― 1 $, as expected, the number is one larger than the correct answer.

There was something that came to my mind here. "The precision of floating-point numbers is about 15 digits in decimal," he said. Ruby's Float is actually environment-dependent, so the accuracy cannot be unequivocally stated, but it is IEEE in a large number of environments. It seems that 754 "double precision" is used. In this case, the precision is about 15 digits in decimal.

So it's quite possible that the result of Math.log10 (x) .floor + 1 with an integer of 15 9s wasn't the correct number of digits.

Conclusion

For small integers, Math.log10 (x) .floor + 1 is fine, but for large integers there is an error.

Recommended Posts

Can the number of digits be Math.log10 (x) .floor + 1?
Count the number of digits after the decimal point in Java
Number of digits in numeric item
How to determine the number of parallels
About the number of threads of Completable Future
[Java] Check the number of occurrences of characters
[Java] Be careful of the key type of Map
I checked the number of taxis with Ruby