1つの面接問題が引き起こした乱数に関する思考(7)

前の2つの記事でRandNが49以下の乱数を実現した以上,前の記事(http://blog.csdn.net/xzjxylophone/article/details/6853727)残された問題:任意のRand 7で任意の数の乱数を実現できるかどうか
この文章はどのように実現すべきかを議論します.
我々がRandNを計算する際に34=7*4+6を用いることに注意すると,101のように他の数を計算すると,101=2*49+3=2*pow(7,2)+0*pow(7,1)+3*pow(7,0)と考えられる.
これは進数(バイナリ、16進数など)を考えさせ、この考え方に基づいて次のコードを実現します.
まずNumAnalyzeクラス:このクラスの役割は、1つの数を私たちが与えた進数に基づいて表し、チェーンテーブルで結果を保存することです.

public class NumAnalyse
{
	private int _baseNum;//7:     
	private List<int> _list;//203
	//       
	/// <summary>
	///     
	/// </summary>
	/// <param name="baseNum">       </param>
	/// <param name="reaNum">        </param>
	public NumAnalyse(int baseNum, int reaNum)
	{
		//    ， _rand7.Next() - 1;
		//       ，              
		reaNum--;//       
		_baseNum = baseNum;
		ResetList();
		//      
		while (reaNum >= _baseNum)
		{
			int remain = reaNum % baseNum;
			reaNum = reaNum / baseNum;
			_list.Add(remain);
		}
		if (reaNum != 0)
		{
			_list.Add(reaNum);
		}
		//      
		_list.Reverse();
	}
	public NumAnalyse(int baseNum)
	{
		_baseNum = baseNum;
		ResetList();
		_list.Add(0);
	}
	//    
	private void ResetList()
	{
		if(_list != null)
		{
			_list.Clear();
		}
		else
		{
			_list = new List<int>();
		}
	}
	public int GetReaNum
	{
		get
		{
			int result = 0;
			int i = 0;
			for(i = 0; i < _list.Count; i++)
			{
				result += (_list[i]) * (int)Math.Pow(_baseNum, _list.Count - i - 1);
			}
			//+1          ，         
			return result + 1;
		}
	}
	public List<int> NumList
	{
		get
		{
			return _list;
		}
	}
}

RandSNクラスの実装を見ています.

public class RandSN : Rand7Base
{
	private NumAnalyse na;//maxNum       
	private RandSN(int maxNum)
	{
		UpdateMaxNum(maxNum);
	}
	public void UpdateMaxNum(int maxNum)
	{
		_maxNum = maxNum;
		na = new NumAnalyse(7, maxNum);
	}
	public static RandSN GetInstance(int maxNum)
	{
		if (rand == null || !(rand is RandSN))
		{
			rand = new RandSN(maxNum);
		}
		else if (rand is RandSN && rand.MaxNum != maxNum)
		{
			((RandSN)rand).UpdateMaxNum(maxNum);
		}
		return (RandSN)rand;
	}
	override public int Next()
	{
		int result = 0;
		NumAnalyse tempNa = new NumAnalyse(7);
		//      
		int num = _rand7.Next() - 1;
		//           
		bool preEqual = true;
		for (int i = 0; i < na.NumList.Count; i++)
		{
			//   && preEqual
			//           2      
			if (num > na.NumList[i] && preEqual)
			{
				result = Next();
				break;
			}
			else
			{
				tempNa.NumList.Add(num);
				//        ，     ，       
				if(preEqual)
				{
					preEqual = (num == na.NumList[i]);
				}
				num = _rand7.Next() - 1;
			}

		}
		//   result       
		return result != 0 ? result : tempNa.GetReaNum;
	}
}

テスト関数を追加するには、次の手順に従います.

static void TestRandSN()
{
	RandSN rand = RandSN.GetInstance(101);
	TestRand(rand);
	rand = RandSN.GetInstance(572);
	TestRand(rand);
}

テスト結果:

  Rand101     
  : 24.0733554924083  
Average:0.0099010;Max:0.0099738;Min:0.0098305
Max:0.0099738, Max-Average:0.0000728, Bits:0.7353800%
Min:0.0098305, Min-Average:-0.0000705, Bits:-0.7119500%
  Rand572     
  : 30.9447089193863  
Average:0.0017483;Max:0.0017927;Min:0.0017121
Max:0.0017927, Max-Average:0.0000444, Bits:2.5424400%
Min:0.0017121, Min-Average:-0.0000362, Bits:-2.0678800%

Rand 572についての偏差は2.54%程度だと思いますが、主な原因は、Rand 572にとってテストの総回数が小さすぎて、興味のある方はN倍拡大して試してみることができるからだと思います
もしかするとテスト関数では、単純差確率ではなく分散を計算すべきかもしれません.この点はともかくとして.
これまでRand 7を例に挙げてきたが,このアルゴリズムでは進数のような解を用いている.もっと基本的なアルゴリズムを書くことができると思います.Rand 7を捨てて、任意のrand関数、例えばRand 10、rand 20、rand 16、rand 2などを使うことができます.