fixedpoint.jp




2014/10/31

Scheme の min / max にまつわる問題

Scheme には minmax という1つ以上の real number の最小値および最大値を返す手続きがあります。R5RS から R7RS に至るまで、その numerical tower に沿って一貫して定義されています。(ただし R6RS では positive infinity と negative infinity についての記述が追加されていました。)

ところが上の定義には問題があります。引数によっては最小値や最大値が定義できない場合があるのです。「引数の集合は有限個の実数の集合なんだから、常に最小値と最大値が存在するだろう」というのは数学的に正しいですが、Scheme の場合 NaN が real number に含まれています。NaN は(NaN 自身を含め)どの real number と比較した場合でも false (#f)になるとされているため、NaN が引数に出てくると total order になりません。

このことが関係して、minmax に NaN を渡すと一見奇妙な振舞いをする実装もあります。例えば GaucheYpsilon は引数の順序によって返る値が変わります:

$ gosh -V
Gauche scheme shell, version 0.9.4 [utf-8,pthreads], x86_64-unknown-linux-gnu
$ gosh
gosh> (min +nan.0 1)
+nan.0
gosh> (min 1 +nan.0)
1.0
gosh> (max +nan.0 1)
+nan.0
gosh> (max 1 +nan.0)
1.0
gosh> 
$ ypsilon
Ypsilon 0.9.6-update3 Copyright (c) 2008 Y.Fujita, LittleWing Company Limited.
> (min +nan.0 1)
1.0
> (min 1 +nan.0)
+nan.0
> (max +nan.0 1)
+nan.0
> (max 1 +nan.0)
1.0
> 
これらは「引数のうち極小値(または極大値)のいずれかを返す」ものと解釈することができます。一方 Racket の場合は、用意周到に「NaN が引数に出てきた場合には NaN を返す」とドキュメンテーションに書かれています: http://docs.racket-lang.org/reference/generic-numbers.html

ちなみに R5RS/R7RS では NaN や infinity は実装拡張とされ、NaN がサポートされていない実装では問題ありません。

参考:

#permalink

2014/10/26

Three farmers パズルを解く

Terence Tao 教授がお子さんの宿題に難しいパズルが出ていて驚いたということが紹介されています。

パズルの内容は以下のとおりです:

Three farmers were selling chickens at the local market. One farmer had 10 chickens to sell, another had 16 chickens to sell, and the last had 26 chickens to sell. In order not to compete with each other, they agreed to all sell their chickens at the same price. But by lunchtime, they decided that sales were not going so well, and they all decided to lower their prices to the same lower price point. By the end of the day, they had sold all their chickens. It turned out that they all collected the same amount of money, $35, from the day's chicken sales. What was the price of the chickens before lunchtime and after lunchtime?

一見それほど難しいように感じませんが、実際に解いてみると結局多少のプログラミングを利用することになりました。以下はその筋道を紹介するもので、最後に解答を書いています。

ひとまずパズルの内容を式で表現してみます。まず3人の農夫(売り手)がそれぞれお昼前までに売ったニワトリの数をそれぞれ(登場順に) abc とします。そして3人全員が合意したお昼前までの価格を p ドル、また3人全員でお昼過ぎてから安売りしたときの価格を q ドルとします。

1日の売上は3人とも同じ35ドルなので、以下のような式が成り立ちます:

ただし上の等式に表れていない重要なポイントがあり、それは(ニワトリは1羽ずつ売られているので)abc は必ず非負整数値を取るということです。この時点でこのパズルは制約問題として integer programming の知識があれば解けるということが分かります。ただここではそのような知識を仮定しません。

上の等式に

r = p - q

という r を考えると見通しがよくなります:

さらに abc を右辺にまとめると以下のようになります:

特に式(5)と(14)、(15)から

q <= 35/26

であることも分かります。

まずは「pq がともにドルの単位で表せる、つまりともに整数になる」という前提で考えてみます。

そうすると式(6)および(16)から、q = 1 でなければなりません。なので式(3)および(4)が成り立つ整数の組み合わせ (c, p, q){(1, 10, 1), (3, 4, 1), (9, 2, 1)} の3通りしかありません。 ところが、これらはいずれも式(1)に式(5)の範囲での整数解がありません。つまり「pq ともに整数」という前提だと解が見つからないことが分かります。

では次に「pq ともにセントの単位で表せる」という前提で考えてみるとどうでしょうか。これはつまり、「p = p'/100 および q = q'/100 となる整数 p' および q' で解になるものがある」ことを意味します。

ここで式(12)、(13)、(14)、(16)を変形して、q' についての式にします:

式(17)、(18)および(19)の右辺の分子に注目します。等式の左辺はいずれも整数であり、共通の分母を持つので、右辺の分子に表れる3つの数の最大公約数が大きくなることが予想されます。そこで、Scheme で簡単なプログラムを用意して、q' が取り得る範囲の整数を並べ上げて最大公約数を計算してみます。

gosh> (define (nums qq) (list (- 3500 (* 10 qq)) (- 3500 (* 16 qq)) (- 3500 (* 26 qq))))
nums
gosh> (map (lambda (qq) (apply gcd (nums qq))) (iota 134 1))
(2 4 2 4 10 4 14 4 2 20 2 4 2 28 10 4 2 4 2 20 14 4 2 4 50 4 2 28 2 20 2 4 2 4 70 4 2 4 2 20 2 28 2 4 10 4 2 4 14 100 2 4 2 4 10 28 2 4 2 20 2 4 14 4 10 4 2 4 2 140 2 4 2 4 50 4 14 4 2 20 2 4 2 28 10 4 2 4 2 20 14 4 2 4 10 4 2 28 2 100 2 4 2 4 70 4 2 4 2 20 2 28 2 4 10 4 2 4 14 20 2 4 2 4 250 28 2 4 2 20 2 4 14 4)

250が一番大きく、期待できそうです。250になるのはq' = 125のときです:

gosh> (filter (lambda (qq) (= 250 (apply gcd (nums qq)))) (iota 134 1))
(125)

ではこの3つの分子の比はどうなるかというと:

gosh> (map (lambda (n) (/ n 250)) (nums 125))
(9 6 1)

きれいに整数の比が出てきました。これがabc になりそうです。

これで解がp' = 375 および q' = 125 であることが分かりました。つまり、答えはお昼前の価格が3ドル75セント、お昼過ぎてからの価格が1ドル25セントになります。

#permalink

Archives

2014: Aug / Apr / Mar / Feb / Jan

2013: Dec / Nov / Oct / Sep / Aug / Jun / May / Apr / Mar

2012: Nov / Oct / Sep / Jul / Jun / May / Mar / Feb / Jan

2011: Dec / Nov / Oct / Sep / Jul / Jun / Apr / Mar / Feb / Jan

2010: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2009: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2008: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2007: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2006: Dec / Nov / Oct / Sep


© 2006-2014 fixedpoint.jp