スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

pyCUDAをUbuntu 14.04 + CUDA 6.5で使う

以前の記事のアップデートである。

CUDA 6.5はNVIDIA側でUbuntu 14.04に対応しているので、インストールには特別なことは必要ない。
ただし以前のバージョンのcuda、nvidia関連のパッケージは

dpkg -l | grep nvidia
dpkg -l | grep cuda

で調べた上で、一旦アンインストールしておくのがいいだろう。

その上で、NVIDAのダウンロードサイトからcuda-repo-ubuntu1404_6.5-14_amd64.debを持ってきてgdebi等でインストールする。

そして

sudo apt-get update
sudo apt-get install cuda

を実行すればインストールは完了する。約1.7GBほどのディスク領域を使用する。

ここまでで、CUDA 6.5を直接利用するのには問題ない。

一方、pyCUDA等の、CUDAを内部で使用するUbuntuでパッケージングされているソフトウェアは、CUDAのUbuntuでパッケージとして用意されているバージョンである5.5に対してリンクされているのでこのままではインストールできない。無理にインストールするとCUDA 5.5も一緒にインストールされてしまい、CUDA 6.5の環境が破壊される。

そこでCUDA5.5相当の機能がすでにインストールされていることをパッケージデータベースに登録するためのフェイクパッケージを作成する。フェイクパッケージは、2つ必要である。

最初のパッケージは、名前は何でもよいのだが、mycudaglueとする。
次のようなテキストファイルを作成する。(SourceとMaintainerは適宜変更)

### Commented entries have reasonable defaults.
### Uncomment to edit them.
# Source:
Section: misc
Priority: extra
Homepage: http://gm3d.blog.fc2.com
Standards-Version: 3.9.2

Package: mycudaglue
Version: 6.5-14
Maintainer: GM3D (@gm3d2 on twitter)
#Depends: cuda (>= 6.5)
Provides: libcublas5.5, libcudart5.5, libcufft5.5, libcufftw5.5,
libcuinj64-5.5, libcurand5.5, libcusparse5.5, libnppc5.5,
libnppi5.5, libnpps5.5, libnvtoolsext1, libnvvm2,
libthrust-dev, libvdpau-dev, nvidia-cuda-dev, nvidia-cuda-doc,
nvidia-cuda-gdb, nvidia-cuda-toolkit, nvidia-libopencl1-331,
nvidia-opencl-dev, nvidia-profiler, nvidia-visual-profiler,
opencl-headers

このファイルをmycudaglueという名前でセーブして、
equivs-build mycudaglue
でできたパッケージをgdebiでインストール。

もう一つはlibcurand5.5のフェイクパッケージである。

libcurand5.5という名前で、以下のファイルを作成。

Section: misc
Priority: optional
Standards-Version: 3.9.2

Package: libcurand5.5
Version: 99
Maintainer: GM3D (@gm3d2 on twitter)

このファイルから、
equivs-build libcurand5.5

によりパッケージを生成、インストールする。これでpyCUDAに関しては依存性が満たされるはずである。念のため、一回

sudo aptitude -s install python-pycuda

でシミュレートを行い、インストールされるのがpython-pycuda、python-pycuda-docのみであることを確認した後、

sudo aptitude install python-pycuda

でインストールを行えば良い。

テストは、上記エントリにも書いてあるように、pyCUDAのhello_gpu.pyあたりを実行してみればよい。
スポンサーサイト

androidアプリを初めて作る

表題の通り、初めてandroidデバイス用のアプリを製作してみた。
タイトルはちょっとポエムで恥ずかしいが、「SatelliteDust - みちびきのささやき -」とつけた。

みちびき、というのはGPSの日本版にあたる、準天頂衛星の1号機である。準天頂軌道という特別な軌道を通るので、日本の上空に滞在する時間が長く、日本で測位に用いるのに便利という性質がある。

このみちびきのプロモーションのために準天頂衛星アプリコンテストという催しが行われていることを先月知ったので、良い機会と思い、androidアプリの基本を学びがてらに応募してみようと思ったのである。

作ったアプリは、以下のような画面を表示する(だけの!)簡単なものである。

Screenshot_2014-07-06-18-38-17.jpg

なにしろこの催し自体を知ったのが遅くて、最初のバージョンを締切りに間に合わせるのがやっとだったので、きわめてシンプルなものである。

準天頂衛星とどう関係あるかというと、この光の粒が上空から降ってくるのだが、その数が準天頂衛星とGPS両方含めて、信号を実際に受信できている衛星の数に比例して多くなるようにしてある。

もっと実用的なアプリはもうすでにこのイベント以外も含めて多くの人が作成しているので、開き直って実用性0を目指してみた。自分は実はこういう簡単なグラフィックが動いているとぼんやり眺めてしまう方なのだが、案外似たような人はいるかもしれないと思って作ってみた。

OpenGLは幸いシェーダーも含めて経験があるので、OpenGL ES2.0を使って表示を行っている。その分表示に関してもまだまだいろいろ変更する余地があるので、今後少しづつバージョンアップを重ねながら設定項目も充実させていきたい。(最初のバージョンは、設定項目もヘルプ画面も何もない)

このエントリを読んでくれた方も、良ければぜひGoogle Playからインストールして試してみていただければありがたい。作りが素人っぽいのはともかくとして、少なくとも怪しいことはしていないので安心していただきたい。

動作に必要な許可は、
位置サービス(低精度)
位置サービス(高精度)
インターネット接続(JAXAからAPIで衛星の軌道データを取得するため)
である。また、OpenGL ES 2.0を用いている関係上、対応するandroidバージョンは2.2(API 8)以上となる。ただ実機テストは4.2.1、4.2.2でしか行っていないので、動作・非動作の報告などもいただけるとありがたい。

Google calendar APIをPythonスクリプトから使う

最近になってだんだんGoogleカレンダーで予定の管理をする頻度が増えてきたのだが、定型的なスケジュールを先まで登録するのにいちいちWebインターフェースで開始時間と登録時間やその他の項目を設定するのが面倒になってきた。

まったく同一内容で、同じ時間帯に繰り返されるようなスケジュールなら、繰り返しのパラメータを指定すればよい。だがここでは、学校の時間割のように、時間枠は毎日一定だが中身は順繰りに変わる、といったような形式のものを考える。

30分くらい思考停止してブラウザ上で黙々とクリックして登録しまくれば一月分くらいすぐ登録できそうであるが、それよりは一日頭をひねってAPIの使い方を習得した方が、自分としては心理的ストレスは少ない。

Google Calendar API自体はREST形式のHTTPリクエストをベースにしているので、まず認証から実際にカレンダーを操作するまでの流れ自体を、

Google Apps Calendar APIの使い方(カレンダーに予定を登録してみる) - howdylikes:

にしたがって、一度ブラウザベースで実行し、感触をつかむことをおすすめする。

その上で、ここではPythonベースで、コマンドラインインターフェースからの操作を行うことが目的である。
基本的な流れとしては、スクリプトの作成前に、先にこれから作成するスクリプトを、Google APIのサーバに対してアプリケーションとして登録して、アプリケーション固有のID(クレデンシャル)を発行してもらう必要がある。あらかじめ登録済みのアプリケーションのみがGoogle APIにアクセスすることを認められるというわけだ。

具体的には、以下のように準備を進めていく。

Google Developers Console
に行き、新規プロジェクトを作成する。そして、作成できたらそのプロジェクトの設定を開き、APIs & auth → APIs の欄で、Calendar APIをONにしておく。スクリーンショットでは上の方に表示されているが、これはONにした後なので、ONにする前はリストの下の方に表示されているので注意してほしい。
google_dev_console1.png

次に、Google API 用のPythonクライアントライブラリをインストールする。
Google APIs Client Library for Python — Google Developers:に行く。
このページの上半分、Runs on Google App Engineまでのところは無視してよい。単に、Client library installationの項にある通り、管理者権限で、

$ sudo pip install --upgrade google-api-python-client

とすれば、クライアント側で必要なPythonライブラリがインストールされる。もちろん、Python(2.x)とpipが使えることが前提である。
そして、そのまま同じページでAPIと環境を選ぶ。ここではCalendar APIと、Python/Command Lineを選択する。そしてConfigure Projectボタンを押す。すると、このアプリケーション用に認証用のクレデンシャルが生成され、次のように画面が遷移する。
google_dev_consosle2.png

そこに書いてある通りに"Download the starter application"からcalendar-python-cmd-line.zipをダウンロードし、適当なディレクトリで解凍し、そこに移動する。また、"Download the client secrets file"からclient_secrets.jsonファイルをダウンロードする。このファイルに、このプロジェクトに属するプログラムを認証してもらうためのクレデンシャルが入っているので、解凍してできたcalendar-cmd-line-sampleディレクトリにある同名のダミーファイルをこれで置き換える。

この時点で、calendar-cmd-line-sampleフォルダ内のsample.pyスクリプトが動作するはずである。このスクリプトは、client_secrets.jsonからクレデンシャルを読み込んで、それを用いてOAuth 2.0認証を行うところまでを実行するようになっている。引数なしで実行してみると、初回だけブラウザが自動的に立ち上がり、このアプリケーションはカレンダーデータへのアクセスを行うことが通知されるので、Acceptを押す。(「誰の」カレンダーかと言えば、最初にアプリケーションを登録するときにGoogleアカウントが必要なので、そのユーザーのカレンダーということになる)
google_api1.png

これでうまく行けば、

Authentication successful.
Success! Now add code here.

というメッセージが表示されて、認証は完了である。なお、ブラウザがインストールされていないなどで自動起動できない環境の場合、--noauth_local_wevserverオプションをつけて実行すると、ブラウザが起動する代わりに、コマンドライン上に認証用のURLと、

"Enter verification code:"

というメッセージが表示される。このURLを別マシンのブラウザなりで開き、そこに表示される認証コードをプロンプトに入力すれば初回認証が完了する。

初回認証さえ完了すれば、後は帰ってきたトークンがsample.datファイル内に保存され、次回以降はこれを使って認証が行われる。

引数なしだと2回目以降もブラウザが起動されるかもしれないが、その場合--noauth_local_wevserverオプションを使用すれば、もう認証コードを要求されることはないので完全にコマンドラインオンリーで操作は完結する。試していないが、グラフィック環境のないマシンであれば、この段階までデスクトップマシンで実行してからディレクトリごとターゲットマシンにコピーすればいいのではないだろうか。

ここまでうまくいけば、後はsample.pyの

try:
print "Success! Now add code here."
except client.AccessTokenRefreshError:
print ("The credentials have been revoked or expired, please re-run"
"the application to re-authorize")

のtry節の部分に具体的なカレンダーAPI操作を付け加えればいいだけである。一通りどんな操作が可能かは最初に紹介したブログなどでつかんでもらったとして、個々の操作を各言語のバインディングでどう行えばいいかは、Google Calendar API - Google Calendar API — Google Developers:
にある。たとえば、予定の作成を行う場合、

try:
events = service.events().insert(calendarId='primary',
body=citem).execute()
except client.AccessTokenRefreshError:
print ("The credentials have been revoked or expired, "
"please re-run the application to re-authorize")

としてやればよい。ここで、citemには、APIで必要な各パラメータを正しい形式で格納したPythonの辞書オブジェクトを指定する(RESTで要求されるJSONではない)。実は最初は、bodyにJSONを指定するとどうしても”Missing end time"というエラーで登録できなかったのだが、どうもPython クライアントライブラリを使う場合、「なんだかJSONを渡さなければならない気がしていたが、よく考えたらそんなことはなかったぜ」ということのようである。

ここまでできたら、後は各自の要求に合わせて処理を拡張することは容易だろう。
私は最初に述べたように、時間枠は固定、中身は一定のリストの中からある規則にしたがって順番に変わっていくような予定を自動的に登録したかったので、最後にそのスクリプトをやや長いがそのまま挙げておく。

具体的には、

py cal3.py 0614 0621 --noauth_local_webserver

のように実行する。第一引数と第二引数で登録開始日と終了日を指定すると、その範囲にわたって学校の時間割にそこはかとなく似たものを自動生成、登録してくれる。年は現在の年固定にしてある。

google_calendar1.png

予定のタイトル(サマリー)一覧はリストではなく辞書にしてあって、あるサマリーの相対的な出現頻度をサマリーをキーとした値として一応持たせてあるが、このバージョンではその情報はまだ利用しておらず、単にキーを順繰りに返すようになっている。

まあ、かなりやっつけ的なスクリプトなのだが、今のところこれ以上凝った自動化の要求が個人的にないのでこうなっている。より洗練されたものにすることは容易だろう。


# -*- coding: utf-8 -*-
# cal3.py
import inspect
import sys
import datetime
import argparse
import httplib2
import os
import string

from apiclient import discovery
from oauth2client import file
from oauth2client import client
from oauth2client import tools

summary_pool = {"量子光学":2, "プログラミング":2, "素粒子論":1, "量子観測理論":2, "マシンラーニング":2, "統計力学":1}

scheduled_times = (("08:00", "09:45"),
("10:00", "11:45"),
("12:45", "14:30"),
("14:45", "16:30"),
("16:45", "18:30"))

def pick(pool):
i = 0
l = len(pool)
while True:
for key, val in pool.items():
yield key

def main(argv):
parser = argparse.ArgumentParser(
description=__doc__,
formatter_class=argparse.RawDescriptionHelpFormatter,
parents=[tools.argparser])
argc = len(argv)
flags = []
print argc, argv
if argc >= 3:
start_date = argv[1]
end_date = argv[2]
elif argc == 2:
start_date = argv[1]
end_date = argv[1]
elif argc == 1:
print "specify start and end date."
sys.exit()
else:
flags = parser.parse_args(argv[3:])
CLIENT_SECRETS = os.path.join(os.path.dirname(__file__),
'client_secrets.json')
FLOW = client.flow_from_clientsecrets(
CLIENT_SECRETS,
scope=[
'https://www.googleapis.com/auth/calendar',
'https://www.googleapis.com/auth/calendar.readonly',
],
message=tools.message_if_missing(CLIENT_SECRETS))
storage = file.Storage('sample.dat')
credentials = storage.get()
if credentials is None or credentials.invalid:
credentials = tools.run_flow(FLOW, storage, flags)
http = httplib2.Http()
http = credentials.authorize(http)
service = discovery.build('calendar', 'v3', http=http)

y = datetime.date.today().year
d = datetime.datetime.strptime(start_date, '%m%d').date()
e = datetime.datetime.strptime(end_date, '%m%d').date()
d = d.replace(year=y)
e = e.replace(year=y)
summaries = pick(summary_pool)
while d <= e:
for tpair in scheduled_times:
stime, etime = tpair
stimestr = tstr(d, stime)
etimestr = tstr(d, etime)
s = summaries.next()
citem = {
"start":{"dateTime": stimestr},
"end": {"dateTime": etimestr},
"summary": s,
"location": "自室",
"description": "Created with cal3.py",
"colorId": "5",
"transparency": "transparent",
"reminders":{
"useDefault": False,
"overrides": [
{
"method": "popup",
"minutes": 5
}
]
}
}

try:
events = service.events().insert(calendarId='primary',
body=citem).execute()
except client.AccessTokenRefreshError:
print ("The credentials have been revoked or expired, "
"please re-run the application to re-authorize")

d += datetime.timedelta(days=1)
print "Following events are created.", events

def tstr(d, t):
hour, minute = map(int, t.split(':'))
t1 = datetime.time(hour, minute)
dt = datetime.datetime.combine(d, t1)
return dt.strftime('%Y-%m-%dT%H:%M:00+09:00')

if __name__ == '__main__':
main(sys.argv)








そしてUbuntu 14.04にしたよ

CUDA 6.0がうまく動作する確証が持てなかったのでずっとUbuntu 12.10のままで頑張っていたのだが、Askubuntu.comのこの質問の最初の答えを見ると、どうやらインストールが可能なようなので、アップグレードを行うことにした。

このリンクにある通りの作業を行ったら無事にインストールできた。ドライバをインストールする段階で、スクリプトが対話的にneoveauドライバを無効にする設定を行うかどうか尋ねてくれるので、YESと答えておけばnouveauの抹殺も手間いらずで行える。ただし、.runパッケージからのインストールなので、debianのパッケージシステムにCUDAの存在が認識されていない状態になっているのが気になる。後で.debパッケージからの再インストールを試みた方がいいかもしれない。

あと、既知の問題として、14.04へのアップグレード後、キーボード配列が英語配列になってしまうという現象があるようだ。実際自分のマシンでもそうなってしまい、若干調べると

Ubuntu 14.04 betaでキーボードレイアウトを日本語に戻す ibus-mozc編

ubuntu-gnome 14.04 (ibus-mozc)で日本語キーボードを使う

あたりにmozcの場合の対処方法は書いてある。私はまだAnthyのままなので、これらの記事を参考に

/usr/share/ibus-anthy/engine/default.xml

をエディターで編集し、

<layout>default</layout>

となっている行を

<layout>jp</layout>

と変更した。

これでも再起動しただけでは英語配列のままだったが、全角/半角キーを押すことで、半角モードでは日本語配列で通常のアスキー文字、全角モードでは日本語入力が可能になった。ただし、Control+Spaceとの絡みで、Control+Spaceを押さないと半角/全角キーもただバッククォートが入力されるだけになったり、また画面上のキーボードインジケータは日本語モードでもEnのままだったり、まだまだ挙動不審である。
本当は全角半角キーはEscapeにマップしてしまいたいのだが、泥沼にはまりそうなので、これでとりあえず我慢しておく。

12.xまでのときはWindowsを使い「こなせる」レベルの人にだったらUbuntuを試しに薦めることも可能だったが、日本語入力がこういう状態だと、さすがに他人には薦められない。インストール直後から普通にキーボード通りの文字が打てて日本語も入力できるというごく当たり前の状態が回復されることを切に願う。


サイダックによる素数が無限にあることの証明に関して

フィリップ・サイダック氏による、素数が無限にあることの別証があるということを先日ツイッターで知った。

読んでいるうちに、別証とはいいつつも、実質的にはユークリッドの証明とほとんど違わない気がしてきたので、そのことについて書くことにする。

と書くと氏の証明を読まれて感動した方の気分を害してしまうかもしれないので言っておくと。ある証明と別の証明がどの程度似ているか、というのを定量的に表す方法は私の知る限りまだ確立されていないので、「主観の問題」ということになる。

ここでは、なぜ私がそう感じたかの道筋を示し、皆さんがどう感じるかはそれぞれにお任せしよう。似ている、似ていないの結論にこだわるよりも、少なくとも一段この定理に関する理解は深まるはずである。

それではまず、ユークリッドとサイダックの両証明で共通して用いられている、
A: 「自然数NとN+1は互いに素である」という事実について確認しておく。

「互いに素」とは、1より大きい共通の因数を持たないということだ。因数というのは、ある数を割り切る数、ということで、例えば

6 = 2 * 3 (* は掛け算の記号)

だから、2や3は6の因数である。なお、因数のうち、素数であるものを素因数という。だからこの例で言うと2や3は6の素因数である。

12 = 2 * 2 * 3

の例で言うと、やはり2や3は12の素因数である。4や6は、12の素因数ではないが、因数ではある。


さて、A: に戻って、NとN+1が共通の因数mを持つとどうなるか考えてみる。すると、NもN+1も、mを因数として

N = m * 整数
N + 1 = m * 別の整数

という形に書けるわけである。下の式から上の式を引くと、

(N + 1) - N = m * 別の整数 - m * 整数 = m * (別の整数 - 整数)

という形になるわけだが、「別の整数 - 整数」というのも結局整数であるので、右辺はmを整数倍した形になっている。しかしこれはもともと、N + 1 と N の差を計算しているのであって、1に決まっている。ということは、mも、「別の整数 - 整数」の部分も両方1に取るしか可能性はない。これでN + 1とNの共通の因数mが1より大きい可能性はなくなった。

大事なので一回まとめよう。
A: 自然数N と N + 1は1より大きい共通の因数を持つことはない。このことをNとN+1は互いに素であるという。

サイダックの証明とユークリッドの証明は、見かけ上の大きな違いは、ユークリッドが背理法に依っているのに対し、サイダックの証明はある程度構成的に次々と素数を見つける手続きを与えていることだ。だが、いずれも根本は実はA:の事実によっており、背理法を使うかどうかは本質的ではない。

A:の意味するところをよく考えよう。N と N + 1は互いに素である…もしここで、Nが既知の素数全部を因数として含んでいたとしたらどうだろう?すると、N+1にはそれらの素因数は含まれないのだから、N+1には必ず新しい素数が因数として含まれることになる。

具体例でちょっと考える。適当に、N = 6とすると、N + 1 = 7である。

6 = 2 * 3
7 = 7

であり、6に含まれている素因数2, 3とは違う新しい素因数7が7には(この場合かなり自明な形で)含まれている。

より両者の類似を明確にし、背理法は本質ではないことを示すために、ユークリッドの方法を、背理法ではなくサイダックと同じ手続き的な形で述べてみる。

ステップ0. 最初は素数p(1) = 2からスタートする。
ステップ1. ここまでで判明しているすべての素数(p(1), p(2), ... p(k)としよう)を掛け算し、それに1を足す。できた数をMと呼ぶことにしよう。
ステップ2. A: で分かったように、p(1)*p(2)*...*p(k) と p(1)*p(2)*...*p(k) + 1 = Mは共通の因数を1以外に持たない。つまりMを素数の積に分解すると、かならずp(1)、N(2)...p(k)とは違った新しい素数が因数として(最低でも一個、うまくいけば複数個)得られる。これらを既知の素数のリストに追加する。
ステップ3. ステップ1に戻る。

このようにして、無限個の素数が得られていく。実際にステップ0から少し試してみよう。無限に続くので、感じがつかめたら読むのをやめて構わない。

ステップ0; p(1) = 2
ステップ1: M = 2 + 1 = 3
ステップ2: 3はそのままで素数、新しく1個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2と3なので、M = 2 * 3 + 1 = 7
ステップ2: 7はそのままで素数、新しく1個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2、3、7なので、M = 2 * 3 * 7 + 1 = 43
ステップ2: 43はそのままで素数、新しく1個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2、3、7、43なので、M = 2 * 3 * 7 * 43 + 1 = 1807
ステップ2: 1807は 1807 = 13 * 139と分解できて、この二つの因数は素因数、新しく2個の素数が見つかった!
ステップ3: ステップ1に戻る
ステップ1: 既知の素数は2、3、7、13, 43, 139なので、M = 2 * 3 * 7 * 13 * 43 * 139 + 1 = 3263443
ステップ2: 3263443はそのままで素数、新しく1個の素数が見つかった!
...

この手続きを実行するのに大変なところは、新しく得られたMを素数の積に分解するところである。上の例でもすでに最後の方は数式処理ソフトMaximaのお世話になった。数が大きくなるにつれてここが極めて困難になっていくので、手続き的とは言いつつも、実行するのは容易ではない。

もともとの形のユークリッドの証明は、このステップが有限回でおしまいになったとすると矛盾が生じるということを背理法の形で言ったものにすぎない。なぜ背理法で述べたかといえば、上のように手続き的な形で述べると、ある人にはわかりやすいかもしれないが、どうしても多少長くなる。結論だけを最短で示すことを考えると背理法の方が字面でいえば短くなるのでそういう形にしたのであろう。

一方のサイダックの証明であるが、ユークリッドの証明において、ステップ1の計算で出てきた既知の素数の積p(1)*p(2)*...p(k)をN(k)と呼んだらどうなるだろう?ユークリッドの証明をこれを使って書き換えてみる。といっても当たり前であるがほとんど変わっていない。

ステップ0: 最初は既知の素数はp(1) = 2 だけなので、N(1) はこれ1個の積 2そのものである。
ステップ1: N(k) + 1 をMとする。
ステップ2: MはN(k)と互いに素なので、Mを素因数の積に分解すれば既知のリストに含まれない新しい素数が得られる、これらを既知の素数のリストに追加する。
ステップ3: 新しく得られた素数をすべて、今までの既知の素数の積N(k)に掛けたものをN(k+1)として、ステップ1に戻る。

さて、既に述べたように、このステップで実行が一番大変なのはMを素因数の積に分解するところである。しかし実際にこの分解操作をすることが必要だろうか?

上の手続きでは、新しく得られた素数は、それまでの既知の素数と一緒に使って、積を計算するわけである。結局必要なのは積だけだとしたら、わざわざ一回Mを素因数の積に分解しなくても、そのままN(k)に掛けてやったらどうだろう。

そのように考えて上の手続きを少しだけ変更したものが次の手続きである。
ステップ0: 最初は既知の素数はp(1) = 2 だけなので、N(1)もこれに等しくとる。
ステップ1: N(k) + 1 をMとする。
ステップ2: Mには既知の素数以外の新しい素数が因数として含まれている。このMをそのまま既知の素数すべての積であるN(k)に掛け算してやり、これをN(k + 1)とする。N(k+1)は新しい素数も含めた既知の素数すべての積になっている。(ただしユークリッドの方法との違いは、重複を取り除いていないので同じ素因数が複数回含まれるかもしれない。だが、それはこの手続きにおいては問題にはならない。)
ステップ3: 1に戻る。

…そしてこれは、冒頭で紹介したサイダックの証明そのものである! 先ほどと同じく、具体的に実行してみよう。

ステップ0: N(1) = 2
ステップ1: M = 2 + 1 = 3
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数3が含まれている。新しい素数が得られた! また次回の実行のため、N(2) = N(1) * M = 2 * 3 = 6 とする。
ステップ3: ステップ1に戻る。
ステップ1: M = 6 + 1 = 7
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数7が含まれている。新しい素数が得られた! また次回の実行のため、N(2) = N(1) * 7 = 6 * 7 = 42 とする。
ステップ3: ステップ1に戻る。
ステップ1: M = 42 + 1 = 43
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数43が含まれている。新しい素数が得られた! また次回の実行のため、N(3) = N(2) * M = 42 * 43 = 1806とする。
ステップ3: ステップ1に戻る。
ステップ1: M = 1806 + 1 = 1807
ステップ2: Mには(もし素因数の積に分解してみれば)新たな素数13と139が含まれている。新しい素数が得られた! しかしサイダック的には実際は素因数分解はしないで、あくまで「もし素因数分解してみれば、そこには新しい素因数が含まれている」点がポイントである。また次回の実行のため、N(3) = N(2) * M = 1806 * 1807 = 3263442とする。


どうであろうか。ここまでの範囲では、両者とも結局まったく同じことをやっている。違いが出てくるのは、手続き中で得られたMに、ある素因数mがmの二乗(か三乗以上か)の形で含まれる場合である。ユークリッドの方はmを一個分だけカウントするのに対して、サイダック方式ではmが二乗や三乗の形のまま積として使われることになる。

サイダック方式の方が、頭の中で「素因数分解を実行する」というステップを省略している分は確かに簡略化されていると言えるが、背理法と手続的方法という表面上の違いを別にすれば、両者の違いはその一点だけだということもお分かりいただけるのではないだろうか。後はそれぞれの読者の感想に委ねたい。

以下は余談ではあるが、数学において、ある定理についてどのような証明が「良い証明」とされるかについては、基準は必ずしも一つではない。すぐ思いつくだけでも以下のような基準があり得る。これらは互いに関連していたり、逆に相反する要素だったりする。


1. 短い
2. 理解が容易である
3. 初等的な事実のみを前提としている
4. 構成的である
5. 他の定理や分野との関係が見てとりやすい

1.と2.は誰でも納得できる基準だろう。3.は、たとえば近年証明されたある分野の難解な大定理を用いると明らか、というようなものだと、一行で済んだとしてもその分野の専門家にしか分からないことになるので、万人向けとは言い難くなる。

4.に関しては、数学を道具として使う物理学、工学、情報などの分野では重要である。単に「~が存在する」とだけ言われるよりは、「ここで示す手続きにしたがえば、具体的に~が構成できる」ことを示される方が、多少長くなったとしても実用上ははるかに有益である。

5.も似ているが、特に数学の専門家同士で重要な観点かもしれない。数学の中の二つの異なるサブジャンルを結びつけるような成果は大きな仕事として評価されるだろう。

これは、証明を、結論という山頂まで山岳ガイドに連れていってもらうことに例えると、どのようなルートが「良いルート」なのか?という話と似ている。

最短で薮の中を突っ切り、後で一人では絶対来られないようなルートを連れていかれ、いきなり視界が開けたと思ったらすでに山頂にいた、というのが良いのか、いろいろと途中で見どころを訪ねながらじっくりと味わいながら行くのがいいか、面白みはないがメジャーな道標のある大きな道筋を辿り、後から一人でも来られるようになるのが良いか。それぞれに長所、短所があり、どれがベストか一概に言えないことはお分かりだろう。

追記 2014/04/01
数学における証明の方法として、背理法や数学的帰納法というのがある。注意しておきたいのは、しばしばこれらの方法自体は証明の本質、あるいは示されている事項の本質ではないことだ。

背理法に関して言うと、背理法に頼らずに証明できる問題ならば、どちらかといえば背理法を用いない方が望ましい。それは、背理法は言ってみればマンガにおける夢オチみたいなもので、証明の途中で作り上げた補助的な事実も、最後は「ハイ矛盾出ました~、最初の仮定が違ってたからですね~、だから途中で示したこともすべて実は成り立ってませんでしたあ~!」ということになり、結論だけは示されるが、証明した事項が成り立つ背景の構造といった、「次につながる」、あるいは「広がりを持たせる」副産物が得にくいからである。

だから、結論だけをとにかく最短で示したい場合や、証明したい結論が非常に難しく、ギリギリ背理法に頼ってなんとか示すことができる、という場合を除くと、あまり背理法を濫用しない方がよい。
プロフィール

GM3D

Author:GM3D
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
FC2カウンター
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。