Knuth先生の小切手

8月の米国出張の際, オークランドのFranz社を訪問した. 鉄道マニアの私のことゆえ, 往きは当然Bartで行ったが, 帰りはFranzの小俣さんがサンフランシスコまで車で送ってくれた. その途中サブプライム問題による売り家の看板をいくつも見かけ, 金融危機をいささか実感した.

ところでこの度, Knuth先生がTAOCPのエラー発見者に対する小切手発行を止めるというので, 金融危機が急遽身近かになった. 完全主義者のKnuth先生は, 自著のエラーを最初に報告した人に十進法で2.56ドル(十六進法で1.00ドル)の小切手を贈ることにしてきた. 小切手は通常は1ヶ月以内に振出人に戻って来るが, Knuth先生の小切手は殆んど現金化されないので(「cashedは僅かで残りはcached」だそうだ), 多くの小切手が世界中に残留しており, 口座番号が知られる危険性があり, 100₁₀年に1度の金融危機の現状では放置出来ない仕儀と相なった.

その代りとして, Pincus惑星に支店のある, San Serriffe銀行に, 小切手受取人の口座を開き, そこに支払い証明(certificate)を積み立てることにしたというのだ. もちろんこれは架空の銀行で, われわれLisperならfoo銀行のbar支店というところである.

PincusとかSan Serriffeは, Knuth先生は好きらしく, TAOCP分冊0には, Pincus惑星の論理学者がどうのこうの(演習問題7.1.1-2)とか, San Serriffe島にはm羽の鳩がいる(演習問題7.1.1-41)とか, 出てくる. 私は漫画やSFには暗いので, これらの名詞がそういうものと何か関係があるかは存ぜぬ.

さて, その新システムの支払い証明がコンピュータ屋には面白い. いろいろ新機軸が見らる.

米国で暮した人は知っているように, ある受取人に2.56ドル渡す場合, 小切手には

Pay to the order of の次に受取人を書き, その右の方に $2.56 と書く.

中央の枠には綴りで Two and 〜〜〜〜〜〜〜〜 56/100 Dollars

のように書く. 従ってHundredとかThousandの綴りも知らなければならない. ドル以下は100分のなんとかと書くことになっている.

新システムにはKnuth先生の趣味がふんだんに見られ,

まず受取人の右の金額は十六進法で 0x$ 1.00 となる.

中央の枠は

One and 〜〜〜〜〜〜〜〜〜 no/256 Hexadecimal Dollars

と変った.


これは実は私として, 大変気持ちが悪い. Knuth先生のホームページなどに, $2.56の由来が書いてあるが, 「256 pennies is one hexadecimal dollar」 がその理由だ.

私に言わせれば, 1は十進でも十六進でも1であり, one hexadecimal dollarはすなわち one decimal dollar である. 100₁₆¢なら256₁₀¢ = $2.56₁₀で, これが理由なら納得出来る. 100₁₆¢ !=100₁₀¢なのだ.

エラー発見は$2.56であるが, 改良案を示すと32¢頂ける. つまり0x$0.20 である. 改良案2件なら 0x$0.40, 5件なら 0x$0.a0, 7件なら 0x$0.e0というわけだ. そこで新システムの中央の枠だが, 改良案1件の場合

Zero and 〜〜〜〜〜〜〜〜 32/256 Hexadecimal Dollarsとなるのだろうか?

Zero and 〜〜〜〜〜〜〜〜 20/100 Hexadecimal Dollarsではないかと思うのだが.

さらに仮りにエラーを12₁₀件見つけたら,

Twelve and なのかな. まさか C and とか書かないであろう.

問題は十六進の桁の読み方, A,B,...,Fの綴り方がないことである. 私は私なりの提案を持つが, それはまたいずれ.

追記 その後Knuth先生から32¢の支払い証明が送られてきた. 確かに0x$0.20とあり, 中央の枠には案の定

Zero and 〜〜〜〜〜〜〜〜 32/256 Hexadecimal Dollars

と書いてあった. 32¢を送る航空便には94¢の切手が貼ってあった.

萬葉集物語

1月ほど前, 新聞の出版広告を見ていたら, 思いがけず「森岡美子著 萬葉集物語」が復刊されたとあった.

実はこの本は, 私が小学生の頃, 繰り返し読んだ思い出深い書物である. その頃の本は, 家が空襲で焼けた時, 一緒に焼けてしまったはずだ.

しかし本書を読んだお蔭で, 萬葉集に対する興味が深まり, 多くの和歌や少なからぬ長歌も諳じた.

ところで左様な昔の本が, 2/3世紀もたった今頃, 復刊されたのは, 驚きである. 実は私の読んだ本とは別に, 多少の手直しを経て, 戦後の昭和27年に冨山房から新たに刊行されていたらしい. 今回復刊されたのは, それであった. 早速求めて読み直したのはいうまでもない.

私が愛した本は, ところどころに色刷りのページがあり, そこには「あおによし」「田子の浦に」など有名な和歌が万葉かなで書いてあった. それが冨山房版にはなかった.

この本は, 言葉使いが大変ていねいである. 「みなさまは, どうお考えになりますか」という調子である. 私は地の文の文体までは覚えていなかったが, こうい調子の本であったらしい.

小学生のころ, 著者が森岡美子という方だとは知っていたが, 女子学習院で教鞭をとられていたことは, 今回知った. そして90歳を超されてご健在であった.

考えてみると, 昔の先生は言葉が一般にていねいだったようにも思う. 私が中学1年の時, 「みなさまが将来論文をお書きになるなら」という先生もいらして, われわれも大人になったのだと実感した.

それはとにかく, 昔の優れた本が, 復刊されるのは, 嬉しいことである.

酉の市

11月5日は一の酉だった. したがって今年は三の酉まである. 酉の市で人出が多いのは, 大鷲神社らしい. 以前, 何回か酉の市の晩に大鷲神社に繰り出したが, 熊手を求める人と, 冷やかしと, もちろんお参りの人とでごった返し, 身動きもままならない様子である.

今年は6月に竜泉の一葉記念館を訪れたので, その帰りに大鷲神社に立ち寄ってみたら, 誰もいなかった.

三の酉といえば, 三の酉まである年は火事が多いといわれる. しかし酉の日は12日毎にあり, 11月は30日なので, 三の酉のある確率は0.5になり, 2年に1度は火事が多いことになる.

世の中もそういう解釈らしいが, 三の酉はあるとすれば11月の25日から30日なので, かなり寒さが身にしみ, 火事と結び付いたのであろう. 三の酉がない年の二の酉は11月の19日から24日までになければならず, 酉の市の寒さの印象は異るのであろう.

酉の市の平均が2.5回あるのと同様なのが, 土用の丑の日だ. 夏の土用は立秋の前の18日間なので, 12日毎の丑の日確率は1.5になる. 二の丑のある夏は暑いといわれないのはなぜか.

ところで曜日も干支も, 閏や大小の月に関係なく, 正確に繰り返される. したがって計算は簡単だ. 一の酉であった(今年の)11月5日のユリウス日数は, 例の個人用電卓によると, 2454776で, そのmod 12は8である. 従って剰余と干支は

子丑寅卯辰巳午未申酉戌亥
11 0 1 2 3 4 5 6 7 8 910

と対応することが分かる. (ユリウス日に1を足して12の法をとると, 0,...,11が子,...,亥に対応すると覚えた方がよいかも.)

同様なことは, 年の干支と西暦の間にもあり, 12で割りきれるのは申年, 60で割りきれるのは庚申である. これを知っていると壬申の乱(672年)は確に申年だと了解出来る.

昔のことだが, 三島由紀夫が自決したのは, 1970年11月25日. この日のユリウス日は2440916, mod 12はやはり8で, 実は三の酉であった.

ユリウス日

数日前に書いた個人用電卓にユリウス日のキーがあった. これは特に週日を求めるためのものである. ユリウス日に1を足し, 7で法をとると日曜を0, 月曜を1, ..., 土曜を6とする週日が得られるのである. またこの電卓は, 除算のとき, スタックトップには商が, そのすぐ下には剰余が出るので, 20081020 [JD] 1 [+] 7［/] [Pop] -> 1 となり, 本年10月20日は月曜と分かる. -4712年1月1日も月曜であったわけだ. ユリウス日は, -4712年1月1日 世界時正午を0.0とし, それからの通日である. 2008年10月20日のユリウス日が2454760というのは, 正確にはその日の世界時正午, JSTで午後9時のユリウス日が2454760.0であるということだ. それを省略してその日のユリウス日という. -4712年1月2日のユリウス日は1である. 理科年表や天文年鑑にも計算用の表がある.

A表              B表    *   C表      *
-1000 1355808     0  0,-1    1   0   0
 -900 1392333     1   365    2  31  31
 -800 1428858     2   730    3  59  60
 ...              3  1095    4  90  91
 1300 2195883     4  1460   ...
 1400 2232408     5  1826   11 304 305
 1500 2268933    ...        12 334 335
 1500 2268923    98 35794
 1600 2305448    99 36159
...
 2000 2451545

例えば2004年4月23日のユリウス日ならA表から2000年の2451545, B表から4年の1460, C表から4月の右の閏年用の91をとり, それに23を足して(+ 2451545 1460 91 23) -> 2453119が得られる. このA表は, 例えば2000年なら, -4712年1月1日から1999年12月31日までの日数である. 従ってこれは2001年1月1日のユリウス日のになりそうだが, B表の最初0年に, 閏年なら-1, 平年なら0とあるのが重要で, 2000年は閏年なので, 1引くから結局1月0日のユリウス日になる. 変換の式もサーチエンジンで探せるが, 私が情報処理学会誌のHaskell Programmingに書いた,

mon0, mon1 :: [Int]
mon0 = [0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334]
mon1 = [0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335]

gleap, jleap :: Int -> Bool -- Gregorian, Julian暦のうるう年
gleap y = if y `mod` 100 == 0 then y `mod` 400 == 0
                              else y `mod` 4 == 0
jleap y = y `mod` 4 == 0

julianDate :: Int -> Int -> Int -> Int
julianDate y m d =                   -- aからgは途中の値
 let a = (y + 4712) * 365
     b = (y + 4712 + 3) `div` 4
     c = if y > 1601 then y' `div` 400 - y' `div` 100 else 0
           where y' = y - 1601
     e = if [y,m,d] >= [1582,10,15] then -10 else 0
     f = (if leap y then mon1 else mon0) !! (m - 1)
           where leap = if y > 1600 then gleap else jleap
     g = d - 1
  in a + b + c + e + f + g           -- 最後の結果

のようにも書ける. インターネットなら, https://www.onlineconversion.com/julian_date.htmにJulian Date Converterがあり, Year, Month, Day(, Hour, Minute, Second)を入れ, Computer Julian dateを押すと結果が返ってくる. 個人用電卓では結局上の式を使った. 電卓は実はやっとiPod touchに実装した. 電車の中でもテストが出来て楽しいが, 実用化にはまだ改良の余地は多々ある.

多面体描画道楽

TAOCPにこういう絵がある. (演習問題7.2.1.2-60)

{0,1,2,3}の24通りの全順列を, 隣り同士の交換で実現しようというものである. 天辺にある0123を最初の順列とする. 左の2個を交換すると1023になり, それは天辺から左へ稜線を辿ると出会う1023である. 次は右の2個を交換し1032が得られる. このようにオレンジ色の線を一筆書きでたどれば全順列を通過するというわけである. これはこの立体のHamilton閉路(つまり全頂点を回って元へ戻る経路)になっている.

この立体は英語では"truncatedoctahedron", 日本語では「切頭八面体」というらしいが, いまいちな感じだ. これは正八面体の頂点を切り落としたものである.

赤い線で示すのが正八面体で, 黒線のように切り取る.

ところでこの立体は, 正八面体の頂点を削れば出来るが, 立方体(正六面体)をの頂点を削っても出来る.


従って「切頭六面体」でもある. ただ削り取る量ははるかに多い. もともとこの立体には, 正方形が6枚, 六角形が8枚あるのだが, 正八面体の6つの頂点が6枚の正方形に辿り着き, 立方体の8つの頂点が8枚の六角形に辿り着く.

同様なものには, サッカーボールともいわれる, 「切頭二十面体」がある. (truncatedicosahedron)



これも, 名前が示すように, 正二十面体の12個の頂点から削り, 12個の正五角形に辿り着くのと, 正十二面体の20の頂点から削り, 20個の正六角形に辿り着くのがある.



赤線で示す正二十面体の頂点から削って, 「切頭二十面体」を作る.



この方は赤線で示すのが正十二面体であり, その頂点から削り始めると, 正五角形の面が段々と削られ, 小さい正五角形が現れる.

さらに削り続けるとどうなるか. 正五角形は消滅して頂点になる. 一方正六角形は正三角形になる. 要するに正二十面体になってしまう. これが正十二面体と正二十面体は相対の関係にあることの証明である. 一方から他方へ移るちょうど途中にサッカーボールがあったのだ.

このことは, 最初の立体でも同じで, 正六面体と正八面体は相対の関係にあることが分かる. 正四面体は自分同士で相対の関係にある.

ではその途中はどういう立体か. その「切頭四面体」
(truncatedtetrahedron)を書いてみた.



あまり見かけない立体ではあるが, 4個の頂点から現れた正三角形が4個の正三角形を六角形にして浸食し, ついには頂点になり, 正三角形の方が面になって, 面と頂点の機能を逆転した正四面体になる. この六角形がちょうど正六角形になった瞬間が上の図である. つまり削られて短くなりつつある元の稜と, 削りながら長くなりつつある新しい稜の長さはどこかで等しくなるのである. この点の座標の計算は簡単である. 逆転した正四面体を青線で示す.

個人用電卓

Hewlett Packardの電卓16Cを愛用していた. 自分でもそういう電卓を設計したいと思い, 何年か前にHappy Hacking Calculatorのシミュレータを書いた. これはパソコンの中で動いているので, 計算するならパソコンを使えばよく, お遊びの域を出なかった.

それが最近, iPod touch用のシミュレータがあるので, iPod用に書き直してみた. それについて書いてみたい. (HHCalcの手引き)

見かけは下の通りである.



左半分が入力キー, 右半分が演算キーである. 入力キーの上部に結果を表示する.

演算の機能は次の通り:

[/] y/x
[*] y*x
[-] y-x
[+] y+x
[Hex] 基数を16進に
[Dec] 基数を10進に
[Oct] 基数を8進に
[Ent] 入力終り
[Pop] スタックトップを捨てる
[Dup] スタックトップを複製
[Exc] x<->y
[Chs] -x
[Sqt] √x
[Fct] xの素因数分解
[Pow] xのy乗
[JD] ユリウス日 2008年10月20日のJDは 20081020 [JD] ->2454760
-4712年1月1日のJDは 47120000[Chs]101[+][JD] -> 0

今のところはシミュレータで動いているだけだ. [JD]のようなマイナーな機能は別画面で指定するようにし, [JD]の場所は別画面起動用にするのもいいかと考えている.

単調関数

The Art of Computer Programming の先の方を読んでいたら, monotone-function function というのに出会った. もちろん, monotoneな関数とは, 単調な, 俗語でいえば「右肩上がり」か「右肩下がり」なものである.

しかし単調関数の関数となると, どうもそう簡単なものではないらしい. そこでの説明は以下の通り. 式が多いので, texで書いて張り付けてある.



上のμ_nの式の右辺のbigwedgeの下にある, 0≤i⊆j≤2ⁿは, 「nビットのiの各ビットがjの各ビットより大きくない対について」という意味である.

TAOCP流にいうと, the bit string i=i₀...i_n-1 is regarded as contained in or equal to the bitstring j=j₀...j_n-1 if and only if i_k≤j_kfor all k.


これでやってみるとmonotone functionは
0変数で2種類(0, 1),
1変数で3種類(0, x, 1),
2変数で6種類(0, x∧y, x, y, x&ory, 1)あり,
3変数の20種類は以下のとおりである.
0, (∧ x (∧ y z)), (∧ y z), (∧ z x), (∧ (∨ x y) z), z, (∧ x y), (∧ (∨ z x) y), y, (∧ (∨ y z) x), (∨ (∧ x y) (∨ (∧ y z) (∧ z x))), (∨ (∧ x y) z), (∨ (∧ z x) y), (∨ y z), x, (∨ (∧ y z) x), (∨ z x), (∨ x y), (∨ x (∨ y z)), 1

3変数関数はSchemeでチェックしたので, Cambridge Notationになっている.
monotone functionは否定なしで, ∧, ∨ だけで書けるというのはこれで分かる.



この図では, 各キューブが1つのmonotonic functionを示す. 座標軸はxが手前, yが右, zが上である. 角の黒丸が関数値が1になることを示す. 左上が3変数関数の0に, その右隣りがx∧y∧zに, のように対応している. 右下が最後の1である. 大学にいた頃, monotonic functionは, このキューブを羊羮だと考え, 黒丸のコーナーと黒丸なしのコーナーが包丁で一度に切り分けられるもの, といったことがある.その様子は見て取れよう.

ついでだが, この図で黒丸の数は0から8まである. 0個の関数は1, 8個のは1である.
1個のは x ∧ y ∧ z, 7個のは x ∨ y ∨ zである.
2個のは x ∧ y 型, 6個のは x ∨ y 型だ.
3個のは x ∧ (y ∨ z)型, 5個のは x ∨ (y ∧ z)型.
4個のは x 型か (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x)=(x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x) これは自己相対で<x, y, z> (多数決)である.

μ_nの真理値表は以下の通り:

μ₀=(1,1)
μ₁=(1,0,1,1)
μ₂=(1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,1)

最後の真理値表から, 2変数関数が単調になる真理値は(一番左を0番として)
0,0,0,0(0番)
1,0,0,0(8番)
1,0,1,0(10番)
1,1,0,0(12番)
1,1,1,0(14番)
1,1,1,1(15番)
だから, 0,0,0,0は0に, 1,0,0,0はx∧yに, 1,0,1,0はyに, 1,1,0,0はxに, 1,1,1,0はx∨yに, 1,1,1,1は1に対応する.

この出てきた文脈は, BDD(binary decision diagram)の合成である. これについてはまたにしよう.