【Python】4300桁以上が想定されるint型変数の桁数を求める

やりたいこと

• Pythonでint型の桁数を求めたい

普通のやり方

一般的にstrに直した後でlen()関数に入れる方法が知られている。
整数型をそのままlen()に入れることができればいいのだが、メソッドが存在しないため、変換する必要がある。

やってみる

簡単に実装できる

num = 12345
length = len(str(num)))
print(length)
# 5

問題点

この方法だと、v3.10.7、v3.9.14、v3.8.14、v3.7.14より新しいバージョンで、4300桁以上の整数型がエラーになる。

Python3.10.6

num = 9999**9999
length = len(str(num))
print(length)
# 39996

Python3.11

num = 9999**9999
length = len(str(num))
print(length)
# Traceback (most recent call last):
#  File "/code/test.py", line 3, in <module>
#    length = len(str(num))
#                 ^^^^^^^^
# ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

原因

ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limitと書いてあります。

上記の対応によって、桁数の多いint<->strの相互変換に制限が加えられました。
具体的には4300桁を超える(>)変換がデフォルトではできなくなりました。
サービス拒否攻撃の防止のため、桁数を測るためだけに制限を迂回するのも良くなさそうです。

新たな方法

定番の方法があるわけではなさそうですが、str変換を使わない方法で実装する必要があります。

常用対数を使った実装

数学的に、桁数を求める場合は下記公式を用いて求めることが多いです。

10^{n-1} \le N \lt 10^n \\ 
\iff n-1 \le \log_{10}{N} \lt n

これをPythonで実装すると

Python3.11

import math 

num = 9999**9999
length = int(math.log10(num) + 1)
print(length)
# 39996

ただし、num=0の時は無限大に飛んでしまうので、実際の実装では0を弾く必要があります。

Python3.11

import math 

def int_len(n):
    if n = 0:
        return 1
    else:
        return int(math.log10(num) + 1)

終わりに

このブログは数学弱々大学院生が書いた弱々記事です。
ここ違うぞ！とか、計算量おかしいことになるぞ！とかあったら編集リクエストやコメントお待ちしています。

参考文献