2008年10月31日金曜日

ユリウス日

数日前に書いた個人用電卓にユリウス日のキーがあった. これは特に週日を求めるためのものである. ユリウス日に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に実装した. 電車の中でもテストが出来て楽しいが, 実用化にはまだ改良の余地は多々ある.

2008年10月29日水曜日

多面体描画道楽

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

2008年10月28日火曜日

個人用電卓

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]の場所は別画面起動用にするのもいいかと考えている.

2008年10月2日木曜日

単調関数

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

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



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

TAOCP流にいうと, the bit string i=i0...in-1 is regarded as contained in or equal to the bitstring j=j0...jn-1 if and only if ikjkfor all k.


これでやってみるとmonotone functionは
0変数で2種類(0, 1),
1変数で3種類(0, x, 1),
2変数で6種類(0, xy, 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に, その右隣りがxyzに, のように対応している. 右下が最後の1である. 大学にいた頃, monotonic functionは, このキューブを羊羮だと考え, 黒丸のコーナーと黒丸なしのコーナーが包丁で一度に切り分けられるもの, といったことがある.その様子は見て取れよう.

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

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

μ0=(1,1)
μ1=(1,0,1,1)
μ2=(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はxyに, 1,0,1,0はyに, 1,1,0,0はxに, 1,1,1,0はxyに, 1,1,1,1は1に対応する.

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