クイーン支配問題
クイーン支配問題 The Art of Computer Programmingに, クイーン支配問題(queens domination probmel)という話題があった. 8×8の盤に, 5個のクイーンを, 盤のすべての場所を支配するように置く という問題である. 1863年の本にあるそうだから, 古典的問題である. この解は, 4860通りあるらしいので, 自分でも計算することにした. 私のことだから, Schemeを使う. またSchemeを使うなら, bit-stringが役立つ. プログラムを書いたら, 思ったより簡単で, 1時間はかからなかった. こんな具合だ. (define (r n) (map (lambda (i) (+ (* n 8) i)) (range 0 8))) (define (c n) (map (lambda (i) (+ (* i 8) n)) (
Piの1000桁
前回のブログのPiの1000桁をもう少し詳しく説明したい. Piの値の計算に Machinの式 π/4 = 4 tan-1(1/5)- tan-1(1/239) tan-1(1/5)=1/5-1/(3·53)+1/(5·55) -1/(7·57)+... tan-1(1/239)=1/239-1/(3·2393)+1/(5·239 5)-1/(7·2397)+... を使った. これは絵を描いてみるとこういうことだ. 円弧の中に底辺:高さが5:1の直角三角形を描く. その中心角をαとする. つまり α=tan-1(1/5). αは11.3°くらいだ. αの斜辺の上にまた今の直角三角形を描く. それを3回繰り返すと4αの 角度が得られ, 上の値を使えば4α=45.2°だ. 一方π/4は45°だから, 今度は底辺:高さ=239:1の直角三角形(赤線)を角度を引く方法に描くとその斜辺が 丁度45
e1000桁の計算
60年くらい前によく行われていた, Napier's constant eの値を1000桁計算するパラメトロン計算機PC-1のプログラムについてのファイルがあったので, 私のブログに載せておくことにした. 自然対数の底 e の値を小数点以下1000桁まで計算することは,1960年代の計算機で流行した. Taylor展開 e = 1 + 1/1! + 1/2! + ... + 1/n! で計算するのだが, n = 460くらいで1000桁の精度がある. 実際には上の式で計算するのではない. e = 1 + 1/1(1 + 1/2(1 + 1/3(1 + ... +1/459(1 + 1/460)...))) を使う. さらに例えば4項ずつまとめて計算することを考える. Qa-4 = 1 + 1/(a - 3)(1 + 1/(a - 2)(1 + 1/(a - 1)(1 + 1/a・Qa
PDP8のプログラム技法
前回のブログで基本ループの動くのは分ったが, calのプログラムを書くにはまだmon0, mon1のデータを用意する仕事がある. そのプログラムの話だ. mon0は各月の1日の曜日が決ったとき, その週の最左端の枠, つまり日曜の日付けである. 1日の曜日の計算は月の定数にその年の定数と(日付けの)1を足す. その年の定数は, 年の下2桁をyとして, (y+floor(y/4)+世紀の定数)%7である. 世紀の定数は, 年の上2桁を4で除した剰余の0,1,2,3について, それぞれ+4, +2, 0, -2である. この辺までを計算するのが次のプログラムの000行から034行である. 000行はプログラムの200番地からの格納の指定. 001行はアキュムレータとリンクのリセット. 002,3行で1文字(1数字)を読みaへ置く. 009行までで4文字(4数字)を読み, 1000,100,10
PDP8のプログラム技法
この表とその年の定数から各月の0日の曜日が判る. 2000年の定数は4なので, 例えば2000年8月15日は(4+4+15)mod 7=2で火曜だ. 注意すべきは2000年が閏年だったので, 1月と2月はこの表から1引くことである. 従ってこの表は補正後は, 1,4,5,8,3,... のように始まる. それに年の定数を足して7の法をとると, 5,1,2,5,0,... になる. すると1月1日は4+1+1=6で土曜である. 1日が土曜だと, 金曜が0, 木曜が-1, 水曜が-2, 火曜が-3, 月曜が-4, 日曜が-5に相当し, 1月の第1週は-5日から始まる. そこから1日ずつ増えて, 1になるのが土曜である. 従って次の図のmon0と書いた表の最上段(1月)に7773, つまり10000-5を入れる. mon0はこのように出来ている. 年の定数が変るとか, 年の定数が同じでも閏年であ
PDP8のプログラム技法
今から50年程前にDEC(Digital Equipment Corporation)が発売していたPDP8というミニコンがあった. 思うにこれはMITのTX-0を源とする似たようなアーキテクチャの計算機である. 簡単に概要を示すと, 1語は12ビット, 記憶装置は12ビットの4096語. 1ページが128語の32ページで構成される. 演算装置の中心は12ビットのアキュムレータで, 2の補数(4096の補数)で演算される. アキュムレータの左に1ビットのリンクがあり, 加算の結果繰上がりがあると, リンクのビットは反転される. アキュムレータのシフトは回転シフトであり, リンクを経由する. アキュムレータのクリアはリンクに影響しない. 図の2段目は記憶装置参照命令で12ビット. 下の図のような構成である. 左端の3ビットが命令コード. 右端の7ビットがページ内アドレスである. ビット4が0
Zuseの計算機
Konrad Zuseはベルリン工科大学で, 電気工学や機械工学でなく土木を学んだが, 1930年代の学生時代にすでに計算機を作ることを考えていたといわれる. Z1からZ4までのZuseの計算機は全く独特なもので, 特に1936年〜1938年に作られた全機械式のZ1に私は興味がある. すべて金属の板, 金属の棒のたぐいでできた浮動小数点の加算器, 制御装置, 記憶装置はまったくユニークであり, その構造を調べたくなるのは人情であろう. 1936年といえば, あのTuringの論文の出た年である. しかしこのZ1は大戦中に連合軍の空襲で破壊され, Zuseが戦後に再構築したZ1が存在し, その写真をみることができる. 再構築の話はここに詳しい. 今回からしばらくZuseの計算機についてブログを書きたい. アメリカのComputer History MuseumにZ1の一部の写真がある. その
ビットごとの秘法と技法 から
最も左のビットの位置を知る法 TACPにはもっと凄いλ関数の計算法がある. 今回はそれを説明しよう. xのサイズは知らなければならないが, それがどんなに大きくてもbignumのような2adic integer(2個進数)での処理だ. まず準備としてあるアルゴリズムを考える. 具体的に4ビットとしよう. 4ビットだから対象は0≤x<16 である. c≤8と最も左のビットだけが1のh=8が登場する. h|x-cは引かれる方が8≤ <16だから, 0≤x<16について, 差は8-c≤ <16-cの2回繰り返しになる. たとえばc=3とすれば, 5,6,...,12,5,6,...,12になる. つまりそれぞれの最初のc個だけが<8になる. これにxをビットごとorすれば, 右半分はxの最も左のビットが1なので≥8になる. 従って全体では左端のc個だけが<8, それ以外は≥8になって, hでビッ
ビットごとの秘法と技法 から
最も左のビットの位置を知る法 二進法で表したxの最も左の1のビットの位置λ(x)は, 2を底とする対数lgがあれば簡単だ. λ(x)=⌊lg (x)⌋ たしかに (lg 1) => 0 (lg 2) => 1. (lg 3) => 1.5849625007211563 (lg 4) => 2. (lg 5) => 2.321928094887362 (lg 6) => 2.584962500721156 (lg 7) => 2.807354922057604 (lg 8) => 3. になっている. TAOCPでの最初の方法は浮動小数点演算命令による. FLOTU y,ROUND_DOWN,x; SUB y,y,fone; SR lam,y,52 ここで fone=#3ff0000000000000. これでうまく行く理由だが, MMIXの浮動小数点はIEEE/ANSI standard
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
四面体の体積
パラメトロン計算機
パラメトロン計算機
パラメトロン計算機
パラメトロン計算機
Fixed Day Number
Fixed Day Number
満月の十五夜
クイーン支配問題
Tパズル
SDGsロゴの錯視