常用対数で整数の桁数を求める

Algorithm

コンピューターで整数の桁数を求めるアルゴリズムです。

前書き

最近のコンピューターは処理が高速です。
高速化を行っても、100万回実行して数ミリ秒くらいの効果しかありません。

Log10を使う方法

10の対数(常用対数)を使う方法です。

対数とは?

べき乗の逆です。

「10を2乗すると何になりますか?」がべき乗です。
「10を何乗すると100になりますか?」が対数です。

10を底とする対数が「常用対数」です。
10進数の常用対数をとって1を加算すると桁数を求めることができます。

System名前空間のMathクラスに常用対数を求める関数「Log10」があるので、これを使うと実装できます。

(int)Math.Log10(Math.Abs(value)) + 1;

結論を言うと、こちらのほうが速いです。

整数型の最小桁数と最大桁数

コンピューター内部で使う整数型は表現できる値が限られています。

整数型最小値最大値最小桁数最大桁数
8bit整数型-12812713
符号なし8bit整数型025513
16bit整数型-32,7683276715
符号なし16bit整数型065,53515
32bit整数型-2,147,483,6482,147,483,648110
符号なし32bit整数型04,294,967,295110
64bit整数型-9,223,372,036,854,775,8089,223,372,036,854,775,807119
符号なし64bit整数型018,446,744,073,709,551,615120

表現できる値が限られているため、最小桁数と最大桁数にも限りがあります。
最小桁数は「1桁」最大桁数は符号なし64bit整数型の「20桁」です。

線形探索を使う方法

対数を使わない方法の1つ目です。線形探索で数値を比較する方法です。

// valueはint型
int value;

// 1桁
if(value < 10)
{
  return 1;
}
// 2桁
if(value < 100)
{
  return 2;
}
// 3桁
if (value < 1000)
{
  return 3;
}
// 4桁
if (value < 10000)
{
  return 4;
}
// 5桁
if (value < 100000)
{
  return 5;
}
// 6桁
if (value < 1000000)
{
  return 6;
}
// 7桁
if (value < 10000000)
{
  return 7;
}
// 8桁
if (value < 100000000)
{
  return 8;
}
// 9桁
if (value < 1000000000)
{
  return 9;
}
// 10桁
else
{
  return 10;
}

ただし、線形探索のため数字が大きくなるほど比較回数が多くなります。
10桁の整数だと、9回も比較をしなければならなくなります。

二分探索を使う方法

先ほどの線形探索の改良版で、二分探索で比較をします。

if (value < 100000)
{
  if (value < 1000)
  {
    if (value < 10)
      {
        return 1;
      }
      else
      {
        if (value < 100)
        {
          return 2;
        }
        else
        {
          return 3;
        }
      }
    }
  else
  {
    if (value < 10000)
    {
      return 4;
    }
    else
    {
      return 5;
    }
  }
}
else
{
  if (value < 10000000)
  {
    if (value < 1000000)
    {
      return 6;
    }
    else
    {
      return 7;
    }
  }
  else
  {
    if (value < 100000000)
    {
      return 8;
    }
    else
    {
      if (value < 1000000000)
      {
        return 9;
      }
      else
      {
        return 10;
      }
    }
  }
}

ソースが分かりにくいため、図解です。

二分探索で桁数を求めるアルゴリズムの図解
二分探索で桁数を求めるアルゴリズムの図解

平衡二分探索木で探索することで、高速化できます。

線形探索では最大9回比較が必要でしたが、二分探索を使うことで最大4回までに減らすことができます。

ベンチマーク

僕の環境で計測した結果です。

厳密に測っているではないので、あくまでも参考程度に。

それぞれForループで約21億回やりました。40秒くらいかかりました。

public void Benchmark()
{
  int value;
  var sw = new Stopwatch();

  // 計測開始
  sw.Start();

  for (int i = 0; i < int.MaxValue; i++)
  {
    value = (int)Math.Log10(Math.Abs(i)) + 1;
  }

  sw.Stop();

  Console.WriteLine(sw.ElapsedMilliseconds);

  // 計測開始
  sw.Restart();

  for(int i = 0; i< int.MaxValue; i++)
  {
    // Digitメソッドは先ほどの二分探索アルゴリズム
    value = Ints.Digit(i);
  }

  sw.Stop();

  Console.WriteLine(sw.ElapsedMilliseconds);
}
アルゴリズムミリ秒
Math.Log1016854
二分探索25844

正直、Math.Log10は遅いと思ってましたが、実測するとかなり速いですね。
わざわざ複雑な二分探索を使う必要が無いです。

コメント

タイトルとURLをコピーしました