Prev Top Top_Prev

4. メモリをビット単位で操作する。

 Prime3cでは1億まで計算するのにはメモリを約25.4MB(=100,000,000x8/30/1,024/1,024)使っています。 現在では問題にならない量ですが、少ないに越したことはありません。
 現状は論理型変数に1バイト使っていますが、これを1ビットに圧縮すればメモリの使用量を1/8に減らせます。
 ただし、VectorScriptではビットを直接読み書き出来ないので、回りくどいやり方になります。

 下の表は、1バイトで表せる数(0~255)を2進数に直したものです。 桁の小さいほうから0~7までの番号を振っています。

	ビットNo. 76543210	ビットNo. 76543210	ビットNo. 76543210	ビットNo. 76543210
	0 ・・・・00000000	64・・・・01000000	128 ・・・10000000	192 ・・・11000000
	1 ・・・・00000001	65・・・・01000001	129 ・・・10000001	193 ・・・11000001
	2 ・・・・00000010	66・・・・01000010	130 ・・・10000010	194 ・・・11000010
	3 ・・・・00000011	67・・・・01000011	131 ・・・10000011	195 ・・・11000011
	4 ・・・・00000100	68・・・・01000100	132 ・・・10000100	196 ・・・11000100
	5 ・・・・00000101	69・・・・01000101	133 ・・・10000101	197 ・・・11000101
	6 ・・・・00000110	70・・・・01000110	134 ・・・10000110	198 ・・・11000110
	7 ・・・・00000111	71・・・・01000111	135 ・・・10000111	199 ・・・11000111
	8 ・・・・00001000	72・・・・01001000	136 ・・・10001000	200 ・・・11001000
	9 ・・・・00001001	73・・・・01001001	137 ・・・10001001	201 ・・・11001001
	10・・・・00001010	74・・・・01001010	138 ・・・10001010	202 ・・・11001010
	11・・・・00001011	75・・・・01001011	139 ・・・10001011	203 ・・・11001011
	12・・・・00001100	76・・・・01001100	140 ・・・10001100	204 ・・・11001100
	13・・・・00001101	77・・・・01001101	141 ・・・10001101	205 ・・・11001101
	14・・・・00001110	78・・・・01001110	142 ・・・10001110	206 ・・・11001110
	15・・・・00001111	79・・・・01001111	143 ・・・10001111	207 ・・・11001111
	16・・・・00010000	80・・・・01010000	144 ・・・10010000	208 ・・・11010000
	17・・・・00010001	81・・・・01010001	145 ・・・10010001	209 ・・・11010001
	18・・・・00010010	82・・・・01010010	146 ・・・10010010	210 ・・・11010010
	19・・・・00010011	83・・・・01010011	147 ・・・10010011	211 ・・・11010011
	20・・・・00010100	84・・・・01010100	148 ・・・10010100	212 ・・・11010100
	21・・・・00010101	85・・・・01010101	149 ・・・10010101	213 ・・・11010101
	22・・・・00010110	86・・・・01010110	150 ・・・10010110	214 ・・・11010110
	23・・・・00010111	87・・・・01010111	151 ・・・10010111	215 ・・・11010111
	24・・・・00011000	88・・・・01011000	152 ・・・10011000	216 ・・・11011000
	25・・・・00011001	89・・・・01011001	153 ・・・10011001	217 ・・・11011001
	26・・・・00011010	90・・・・01011010	154 ・・・10011010	218 ・・・11011010
	27・・・・00011011	91・・・・01011011	155 ・・・10011011	219 ・・・11011011
	28・・・・00011100	92・・・・01011100	156 ・・・10011100	220 ・・・11011100
	29・・・・00011101	93・・・・01011101	157 ・・・10011101	221 ・・・11011101
	30・・・・00011110	94・・・・01011110	158 ・・・10011110	222 ・・・11011110
	31・・・・00011111	95・・・・01011111	159 ・・・10011111	223 ・・・11011111
	32・・・・00100000	96・・・・01100000	160 ・・・10100000	224 ・・・11100000
	33・・・・00100001	97・・・・01100001	161 ・・・10100001	225 ・・・11100001
	34・・・・00100010	98・・・・01100010	162 ・・・10100010	226 ・・・11100010
	35・・・・00100011	99・・・・01100011	163 ・・・10100011	227 ・・・11100011
	36・・・・00100100	100 ・・・01100100	164 ・・・10100100	228 ・・・11100100
	37・・・・00100101	101 ・・・01100101	165 ・・・10100101	229 ・・・11100101
	38・・・・00100110	102 ・・・01100110	166 ・・・10100110	230 ・・・11100110
	39・・・・00100111	103 ・・・01100111	167 ・・・10100111	231 ・・・11100111
	40・・・・00101000	104 ・・・01101000	168 ・・・10101000	232 ・・・11101000
	41・・・・00101001	105 ・・・01101001	169 ・・・10101001	233 ・・・11101001
	42・・・・00101010	106 ・・・01101010	170 ・・・10101010	234 ・・・11101010
	43・・・・00101011	107 ・・・01101011	171 ・・・10101011	235 ・・・11101011
	44・・・・00101100	108 ・・・01101100	172 ・・・10101100	236 ・・・11101100
	45・・・・00101101	109 ・・・01101101	173 ・・・10101101	237 ・・・11101101
	46・・・・00101110	110 ・・・01101110	174 ・・・10101110	238 ・・・11101110
	47・・・・00101111	111 ・・・01101111	175 ・・・10101111	239 ・・・11101111
	48・・・・00110000	112 ・・・01110000	176 ・・・10110000	240 ・・・11110000
	49・・・・00110001	113 ・・・01110001	177 ・・・10110001	241 ・・・11110001
	50・・・・00110010	114 ・・・01110010	178 ・・・10110010	242 ・・・11110010
	51・・・・00110011	115 ・・・01110011	179 ・・・10110011	243 ・・・11110011
	52・・・・00110100	116 ・・・01110100	180 ・・・10110100	244 ・・・11110100
	53・・・・00110101	117 ・・・01110101	181 ・・・10110101	245 ・・・11110101
	54・・・・00110110	118 ・・・01110110	182 ・・・10110110	246 ・・・11110110
	55・・・・00110111	119 ・・・01110111	183 ・・・10110111	247 ・・・11110111
	56・・・・00111000	120 ・・・01111000	184 ・・・10111000	248 ・・・11111000
	57・・・・00111001	121 ・・・01111001	185 ・・・10111001	249 ・・・11111001
	58・・・・00111010	122 ・・・01111010	186 ・・・10111010	250 ・・・11111010
	59・・・・00111011	123 ・・・01111011	187 ・・・10111011	251 ・・・11111011
	60・・・・00111100	124 ・・・01111100	188 ・・・10111100	252 ・・・11111100
	61・・・・00111101	125 ・・・01111101	189 ・・・10111101	253 ・・・11111101
	62・・・・00111110	126 ・・・01111110	190 ・・・10111110	254 ・・・11111110
	63・・・・00111111	127 ・・・01111111	191 ・・・10111111	255 ・・・11111111
	
	上の表を眺めれば判るように、
	第0ビット・・・・1
	第1ビット・・・・2
	第2ビット・・・・4
	第3ビット・・・・8
	第4ビット・・・ 16
	第5ビット・・・ 32
	第6ビット・・・ 64
	第7ビット・・・128
	になります。
		
 ビットをセットするときは、そのビットに対応する数(第3ビットなら8)を足してやればいいのですが、 元々そのビットがセットされているかどうかを知らないと、足して良いのか悪いのか判りません。
 特定のビットの状態を計算で求める簡単な方法はないので、配列変数を利用する方法でやります。

	procedure BitTest;
	{ 0~255までの整数を2進数で表示する。 }
	{ 2007/10/02 与太郎 }
	var
		bit	:array[0..255, 0..7] of boolean;
		i, bt, c	:integer;
		flg	:boolean;
		
		procedure InitBits;
		{ ビット参照用配列を初期化する。 }
		var
			i, stp, bt	:integer;
		begin
			stp:= 1;
			for bt:= 0 to 7 do begin
				c:= 0;
				flg:= false;
				for i:= 0 to 255 do begin
					bit[i, bt]:= flg;
					c:= c + 1;
					if c = stp then begin
						flg:= not flg;
						c:= 0;
					end;
				end;
				stp:= stp * 2;
			end;
		end;{InitBits}
		
		procedure WriteBin(i:integer);
		{ 0~255までの整数を2進数に変換する。 }
		var
			bt	:integer;
			s	:string;
		begin
			s:= '';
			for bt:= 7 downto 0 do begin
				if bit[i, bt] then
					s:= Concat(s, '1')
				else
					s:= Concat(s, '0');
			end;
			Message(i, ' = ', s);
		end;{WriteBin}
		
	begin{main}
		InitBits;
		repeat
			i:= IntDialog('0-255', '0');
			if (not DidCancel) & (0 <= i) & (i <= 255) then
				WriteBin(i);
		until DidCancel;
	end;
	Run(BitTest);
		
 上記スクリプトのbit変数と初期化ルーチンを使って、1バイト整数の各ビットを読み書き出来ます。
 VectorScriptには1バイト整数型はないので、Char型を使用します。
 30n~30n+29までが1バイトに納まるので、直すのも簡単です。

	procedure Prime4;
	{ 素数を書き出す。 }
	{ 2007/10/02 与太郎 }
	const
		MaxNum = 1000000;
		MsgDist = 500;
		OutputFile = 'Prime4-Output.txt';
		MaxArray = MaxNum div (10000 * 30);
	var
		t0, t	:longint;
		i, j, jj, k, n, sqM, bt	:longint;
		ch	:array[0..MaxArray, 0..9999] of char;
		offset	:array[0..7] of integer;
		disOffset	:array[0..29] of integer;
		bit	:array[0..255, 0..7] of boolean;
		bitWt	:array[0..7] of integer;
		
		procedure InitBits;
		{ ビット参照用配列を初期化する。 }
		var
			i, stp, bt, c	:integer;
			flg	:boolean;
		begin
			stp:= 1;
			for bt:= 0 to 7 do begin
				c:= 0;
				flg:= false;
				for i:= 0 to 255 do begin
					bit[i, bt]:= flg;
					c:= c + 1;
					if c = stp then begin
						flg:= not flg;
						c:= 0;
					end;
				end;
				stp:= stp * 2;
			end;
			bitWt[0]:= 1;
			bitWt[1]:= 2;
			bitWt[2]:= 4;
			bitWt[3]:= 8;
			bitWt[4]:= 16;
			bitWt[5]:= 32;
			bitWt[6]:= 64;
			bitWt[7]:= 128;
		end;{InitBits}
		
		function GetBit(ch:char; bt:integer):boolean;
		{ chのbt番目のビットを返す。 }
		begin
			GetBit:= bit[Ord(ch), bt];
		end;{GetBit}
		
		procedure SetBit(var ch:char; bt:integer);
		{ chのbt番目のビットをTrueにする。 }
		begin
			if not bit[Ord(ch), bt] then
				ch:= Chr(Ord(ch) + bitWt[bt]);
		end;{SetBit}
		
		procedure ResetBit(var ch:char; bt:integer);
		{ chのbt番目のビットをFalseにする。 }
		begin
			if bit[Ord(ch), bt] then
				ch:= Chr(Ord(ch) - bitWt[bt]);
		end;{ResetBit}
		
		procedure ResetMultiple(i:longint);
		{ iの倍数をFalseにする。 }
		var
			ii, j, k	:longint;
		begin
			ii:= i * i;
			while ii <= MaxNum do begin
				j:= ii div 30;
				k:= disOffset[ii mod 30];
				if k <> -1 then
					ResetBit(ch[j div 10000, j mod 10000], k);
				ii:= ii + i*2;
			end;
		end;{ResetMultiple}
		
		function IsPrime(i:longint):boolean;
		{ 素数ならTrueを返す。 }
		var
			result	:boolean;
			j, k	:longint;
		begin
			j:= i div 30;
			k:= disOffset[i mod 30];
			if k = -1 then
				result:= false
			else
				result:= GetBit(ch[j div 10000, j mod 10000], k);
			IsPrime:= result;
		end;{IsPrime}
		
	begin{main}
		t0:= GetTickCount;
		InitBits;
		offset[0]:= 1;
		offset[1]:= 7;
		offset[2]:= 11;
		offset[3]:= 13;
		offset[4]:= 17;
		offset[5]:= 19;
		offset[6]:= 23;
		offset[7]:= 29;
		for i:= 0 to 29 do
			disOffset[i]:= -1;
		disOffset[1]:= 0;
		disOffset[7]:= 1;
		disOffset[11]:= 2;
		disOffset[13]:= 3;
		disOffset[17]:= 4;
		disOffset[19]:= 5;
		disOffset[23]:= 6;
		disOffset[29]:= 7;
		Message('配列を初期化中...');
		for i:= 0 to MaxArray do begin
			for j:= 0 to 9999 do
				ch[i, j]:= Chr(255);
			Message('配列を初期化中...', (i+1) * 10000 * 30, '/', MaxNum);
		end;
		ReWrite(OutputFile);
			sqM:= Round(Sqrt(MaxNum));
			Message('素数を判定中...');
			for i:= 6 to sqM do begin
				if IsPrime(i) then begin
					Message(i, 'の倍数を消去中... ', i, '/', sqM);
					ResetMultiple(i);
				end;
			end;
			ResetBit(ch[0, 0], 0);
			Message('素数を書き出し中...');
			WriteLn(2);
			WriteLn(3);
			WriteLn(5);
			n:= 3;
			for i:= 0 to MaxArray do begin
				j:= 0;
				repeat
					for bt:= 0 to 7 do begin
						if GetBit(ch[i, j], bt) then begin
							n:= n + 1;
							k:= i*10000*30 + j*30 + offset[bt];
							if (k <= MaxNum) then begin
								WriteLn(k);
								if (n mod MsgDist) = 0 then
									Message('素数を書き出し中...', n, ' : ', k, '/', MaxNum);
							end;
						end;
					end;
					j:= j + 1;
				until (9999 < j) | (MaxNum <= k);
			end;
		Close(OutputFile);
		t:= GetTickCount;
		Message(Maxnum, ' 以下の素数を ', n, ' 個書き出しました。(', (t-t0)/60, 'sec.)');
		SysBeep;
	end;{main}
	Run(Prime4);
		
実行時間は下のようになりました。
100,000・・・・・・ 2.6秒
200,000・・・・・・ 5.0秒
500,000・・・・・・12.1秒
1,000,000・・・・・24.4秒
2,000,000・・・・・49.1秒
5,000,000・・・・ 119.8秒
10,000,000 ・・・ 259.2秒
 メモリサイズは1/8で済みますが、実行時間は約1.5倍になりました。  100,000,000は面倒なので確認しませんでした。
 1億までの計算に必要なメモリは、約3.2MB(=100,000,000/30/1,024/1,024)です。 このスクリプトでは最大312.5MB(=32,768x10,000/1,024/1,024)で約98億までの配列を使えますが、 素数がLongint型の範囲(-2,147,483,648~2,147,483,647)を超えてしまうので、 実際には約21億までしか計算できません。
 Real型にすれば配列サイズいっぱいまで計算できると思いますが、何日もかけて計算しても面白味に欠けるので、 この話題はこのへんで止めておきます。

Top_Prev