- 1 名前：デフォルトの名無しさん [2005/05/12(木) 21:44:01 ]
- 過去スレ
Part1: piza2.2ch.net/tech/kako/987/987169286.html
Part2: pc.2ch.net/tech/kako/1002/10025/1002584344.html
Part3: pc.2ch.net/tech/kako/1008/10082/1008220265.html
Part4: pc.2ch.net/tech/kako/1016/10162/1016211619.html
Part5: pc3.2ch.net/tech/kako/1023/10230/1023091882.html
Part6: pc3.2ch.net/tech/kako/1031/10315/1031560687.html
Part7: pc5.2ch.net/tech/kako/1042/10421/1042167213.html
Part8: pc5.2ch.net/tech/kako/1058/10582/1058263391.html
Part9: pc2.2ch.net/test/read.cgi/tech/1069594582/
Part10: pc5.2ch.net/test/read.cgi/tech/1075630259/
Part11: pc5.2ch.net/test/read.cgi/tech/1091456033/
Part12: pc8.2ch.net/test/read.cgi/tech/1100229366/
関連リンクは>>2-10あたり
- 523 名前：本田 [2005/07/05(火) 22:54:51 ]
- >>513 ：デフォルトの名無しさん ：2005/07/05(火) 04:54:27
> KCLは２０年前からネイティブコードで走ってるけど、何か？
KCLのコンパイラはC言語にコンパイルするはず。
- 524 名前：デフォルトの名無しさん mailto:sage [2005/07/05(火) 22:58:46 ]
- C 言語は ASM にコンパイルされるし、ASM は機械語に変換される。
C にしない処理系でも IL に変換されたりするし、C にコンパイルしていても
最終的にネイティブコードになる事には変わりない。
- 525 名前：デフォルトの名無しさん [2005/07/05(火) 23:34:23 ]
- >>522
疑問に思ったのがこのコードを実行してみてだったので、
そのまま質問してしまいました。
末尾再帰は直接関係ありません。
手続きを定義するときにその手続きは定義時の環境を「覚えて」いて、
手続きを呼び出したときにはその環境内で手続きが評価される、と
理解しています。
514の質問の意図は、作られた手続きが保持しているものが
(1)手続き作成時の環境そのもの(シンボルテーブルなど環境内の要素を含む)
なのか、
(2)手続き作成時の環境への参照またはポインタ
でよいのか、についての答えをいただきたいということでした。
(2)でよいと思っていたのですが、もしそうだとすると、>>514の例では
手続き18:の環境は手続き2:と共有されるために、束縛関係が書き換えらてしまい、
実際の結果の説明ができません。
ということは、手続き定義時には、そのときの環境が複製され、
定義された手続き固有の(他の手続きなどからアクセスできない)
環境となって保持される、ということでよいのでしょうか。
- 526 名前：デフォルトの名無しさん mailto:sage [2005/07/05(火) 23:42:52 ]
- 根本的に変な固定概念に取り憑かれているようだな。憑き落とししなきゃ。ｗ
- 527 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 00:20:41 ]
- >>525
参照とかポインタとか複製とか実装の観点から考えないほうがいいですよ
文字通り「字面上の」スコープに縛られるんです
; それをどう実装するかは別の話
- 528 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 02:35:31 ]
- >>523
それが何か？
- 529 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 02:37:20 ]
- >>525
>>521 を勉強汁
- 530 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 02:43:08 ]
- SICPに載ってる環境モデルでええやん
- 531 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 03:33:24 ]
- 必要以上に深く考え過ぎ。しかも間違った方向に。
- 532 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 04:58:04 ]
- 學而不思則罔、思而不學則殆 ってやつだな。あやうくてしかたない。
- 533 名前：デフォルトの名無しさん [2005/07/06(水) 09:02:31 ]
- >>530
>SICPに載ってる環境モデルでええやん
知りたかったのはまさにこれです。
ありがとうございました。
- 534 名前：デフォルトの名無しさん [2005/07/06(水) 17:37:37 ]
- SICPが名著だと言われるゆえんを実感しました。
- 535 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 18:22:40 ]
- 油煙
- 536 名前：デフォルトの名無しさん mailto:sage [2005/07/06(水) 18:25:04 ]
- SICPって何ですか？
- 537 名前：536 mailto:sage [2005/07/06(水) 18:26:01 ]
- って >>6 に書いてあったですね ｽﾏﾝ
- 538 名前：デフォルトの名無しさん [2005/07/07(木) 20:09:49 ]
- いや、普通わからんて
Structure And Interpretation Of Computer Programs
すとらくちゃーあんどいんたーぷりてーしょんおぶこんぴゅーたぷろぐらむす
コンピュータープログラムの構造と解釈
略してSICPという。
え？
SAIOCPじゃないの？
AとOはどこいったよ？
なあ？
普通わかんねーよなあ
ところで
SICPって何て読むか知ってるか？
俺は知らないが
しくぷとか発音すると馬鹿にされそうで
恐い
- 539 名前：デフォルトの名無しさん mailto:sage [2005/07/07(木) 20:17:20 ]
- ここは Lisp/Scheme スレだから SICP で十分通じる。
俺の脳内ではシックピーって読んでるよ。
- 540 名前：デフォルトの名無しさん [2005/07/07(木) 20:19:36 ]
- お前の脳内の事なんか聞いてない
- 541 名前：デフォルトの名無しさん [2005/07/07(木) 20:22:23 ]
- あ、ごめん
間違えて書き込むボタン押しちゃったよ
こういうのは本来書き込むべき内容ではなかったが、
名無しだからいいやと思ってしまうな
匿名って恐いな
２ｃｈにいるとどんどんクズ人間になっていく気がする
おれのこと軽蔑した？
悪かったよごめんな
- 542 名前：デフォルトの名無しさん mailto:sage [2005/07/07(木) 20:49:05 ]
- 接続詞は頭文字に含めないことくらい普通は知ってる
- 543 名前：デフォルトの名無しさん [2005/07/07(木) 20:50:13 ]
- >>541 ドンマイ、しかし、貢献するべし
- 544 名前：デフォルトの名無しさん mailto:sage [2005/07/07(木) 20:59:23 ]
- さて、そろそろ LISP の話 ｷﾎﾞﾝﾇ
- 545 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 13:25:12 ]
- >>542
前置詞もな
あと冠詞
他に何かあったっけ？
SICPよりも LISP の方がわかりにくい。
LISt Processor
- 546 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 14:30:34 ]
- LITHP (LITHtth Prothethor)
John Unger Zussman が冗談で作った架空言語。
1982年Infoworldが出した「あまりよく知られていない言語」という書籍の面白言語リストに掲載され、
後にUsenetに投稿された。この架空言語の本質は、「もしLisperのキーボードに"S"が無かった」という発想である
- 547 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 14:34:42 ]
- S式はTH式になるのか？
まあ算盤も広い意味では計算機だがな
- 548 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:38:15 ]
- すいません、質問なのですが、
(p'((1)2 3))
とすると
1 2 3
と表示する、括弧を取り除いて表示するような
関数pはどのように定義すればよいのでしょう？
- 549 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:38:45 ]
- ↑は(1 2 3)と表示する、の間違いでした。
- 550 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:46:19 ]
- >>548
(defun p (x)
(if (listp x)
(mapcan #'p x)
(list x)))
- 551 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:54:24 ]
- >>550
ありがとうございます！
mapcanと#の意味がわからないんですけど
これはどういうことですか？
- 552 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:58:27 ]
- >>551
Common Lisp 勉強汁
- 553 名前：デフォルトの名無しさん mailto:sage [2005/07/08(金) 23:59:42 ]
- >>551
mapcanはmapcarと同じ動作をした後に各館数の返り血をappendで連結した物を返す関数。
#`はそのシンボルを関数として扱うという意味。
- 554 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 00:04:19 ]
- >>552-553
よくわかりました。
本当にありがとうございました。
- 555 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 00:06:49 ]
- >>553
重箱の隅ですまんが append ではなく nconc、#` ではなく #' だね。
- 556 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 02:43:36 ]
- 素人質問への解答乙。
つか、明らかに荒らしだよなこいつの質問は。
- 557 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 02:44:24 ]
- 基本的な関数のみで書いた、初心者向け版。
(defun p (x)
(if (null x) '()
(if (consp (car x))
(append (p (car x))
(p (cdr x)))
(cons (car x)
(p (cdr x))))))
- 558 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 03:01:55 ]
- Scheme には mapcan が無いとお嘆きの貴兄に、Scheme 版。
(define (p x)
(if (list? x)
(apply append (map p x))
(list x)))
- 559 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 03:49:56 ]
- nconc や append! を使う自信が無くて、つい append を使ってしまう自分。
- 560 名前：デフォルトの名無しさん [2005/07/09(土) 09:51:51 ]
- (defun p (x)
(cond ((null x) '())
((consp x)
(nconc (p (car x))
(p (cdr x))))
(t (cons x '()))))
(p '((x . y) (x)))
- 561 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 16:49:29 ]
- >>559
静的関数型言語方面じゃ型推論と同じなノリで、
破壊しても問題ないと推論される場合には破壊的にやっちゃうようなコードを吐かせよう、
みたいなことやってるみたいね。
ttp://sky.zero.ad.jp/~zaa54437/programming/clean/LanguageReport21/Chap9.html
- 562 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 19:21:50 ]
- >>548
うまいこと宿題やってもらえて良かったね。
- 563 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 21:46:39 ]
- 最近に処理系では破壊的な方が速いとは限らない
みたいなことがANSI Common Lisp(P. Graham)に書いてあったんだけど、そんなもんなのかね。
どうしたらそうなるのか見当もつかないんだが。
- 564 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 22:03:44 ]
- gcがめちゃくちゃ速いから？
- 565 名前：デフォルトの名無しさん mailto:sage [2005/07/09(土) 22:15:14 ]
- Write Barrier のコストとか。
- 566 名前：デフォルトの名無しさん mailto:sage [2005/07/10(日) 00:09:20 ]
- copy on write とか?
- 567 名前：デフォルトの名無しさん [2005/07/10(日) 00:14:17 ]
- ttp://www.ai.mit.edu/projects/cl-http/dist/からcl-http-70-190a.tar.gz落として
cmuclで動かそうとしたんだけどパッチすらあたらなかった。
うまく動作してる人いない？
- 568 名前：デフォルトの名無しさん mailto:sage [2005/07/10(日) 02:21:43 ]
- >>561
ああっ、それいいなあ。
LISP と関数型言語の差って、何でも自分でいじれるオフロード車と、外装内
装に便利なものが作り込まれたタウンカーの差みたいなものかな。
- 569 名前：デフォルトの名無しさん [2005/07/11(月) 22:48:53 ]
- 総称関数モデルがメッセージ駆動モデルよりも強力だといえるのは何故？
メリットとかデメリットとか教えて欲しい。
- 570 名前：デフォルトの名無しさん mailto:sage [2005/07/11(月) 23:08:22 ]
- >>569
メッセージ駆動モデルって何?
- 571 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 00:21:25 ]
- >>570
メソッドはオブジェクトに属していて、オブジェクトにメッセージを送ることでメソッドが活性化される。
メソッドはデータと一緒に継承される。
SmalltalkとかJavaとかはメッセージ駆動モデルなんだって。
- 572 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 00:29:57 ]
- それって総称関数のサブセットじゃないか
- 573 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 02:54:29 ]
- Lisp 関係の古典がオンラインで読めるようになったので一応アドレス貼っておきますね。
John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin.
LISP 1.5 Programmer’s Manual.
The M.I.T. Press, 1962, second edition.
community.computerhistory.org/scc/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf
Berkeley and Bobrow, editors.
The Programming Language LISP: Its Operation and Applications.
Information International, Inc., March 1964 and The MIT Press, April 1966.
community.computerhistory.org/scc/projects/LISP/book/III_LispBook_Apr66.pdf
- 574 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 03:50:45 ]
- >>571
そういう話は無益だから止めれ
Java にメッセージ式は無い
Smalltalk のメソッドはクラスに属している（クラスもオブジェクトだけど）
- 575 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 09:17:12 ]
- Ｒｕｂｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙｙ
- 576 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 17:19:47 ]
- とりあえず総称関数だとマルチメソッドが考えやすい。レシーバーだけでなく、複数の引数のクラスで処理を分けたいときに便利。
その分、メソッドが特定のクラス(やオブジェクト)に属さないのでオブジェクト指向モデリングとやや相性が悪い。
総称関数の方ができることが多い(いや、究極的にはできることは同じだけどやり易さとして)けど、オブジェクト指向とはちょっと考え方が違う感じ。メッセージモデルの方がオブジェクト指向らしい。
もっと計算理論的な話は別の人に任す。
- 577 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 21:51:56 ]
- 複数引数の型を見て処理を割り振る話(メソッド・ディスパッチだっけ？)について。
多くのOO言語では、静的な解決しかできない。
総称関数ベースなら、呼び出された時の型を見て動的に処理を割り振ることができる。
これがメリット？
- 578 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:15:42 ]
- >>577
マルチディスパッチと動的ディスパッチは一応別の問題だよね。
Smalltalkなんかはシングルの動的ディスパッチじゃないかな。
静的なマルチディスパッチの例としてはC++の関数や演算子ね。
- 579 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:20:22 ]
- えぇ〜とLispのは、具体的なメソッド選択を明示的に書く仕組みだったと思います。(実使用体験０、80年代のbit記事受け売り)
ってな話だと、>>578とは違うんじゃないかなぁ〜。
- 580 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:39:20 ]
- >>577
>多くのOO言語では、静的な解決しかできない。
んな事は無い
- 581 名前：577 mailto:sage [2005/07/12(火) 22:42:26 ]
- >>580
そのとおり。
でも、引数を親クラスにキャストしてメソッド呼出したら、、、
- 582 名前：デフォルトの名無しさん mailto:sage [2005/07/12(火) 22:53:23 ]
- 何でキャストの話が出て来るんだよ
OO のモデルなんか趣味の世界だから、自分で使って勝手に判断すれば良い
- 583 名前：577 mailto:sage [2005/07/13(水) 00:00:29 ]
- なんだぁ？ヴァカか。
- 584 名前：デフォルトの名無しさん mailto:sage [2005/07/13(水) 01:03:28 ]
- では、そろそろ LISP の話に戻りましょうか
- 585 名前：デフォルトの名無しさん mailto:sage [2005/07/13(水) 02:14:15 ]
- まとめると
総称関数だといくつかのクラスにまたがった複数引数をとるメソッドがかける
ってことか
- 586 名前：デフォルトの名無しさん mailto:sage [2005/07/14(木) 15:03:45 ]
- SICPの5.4 The Explicit-Control Evaluatorで、
> Our Scheme evaluator register machine includes a stack and
> seven registers: exp, env, val, continue, proc, argl, and unev.
とあるのですが、unevという名前の意味や由来は何なのでしょうか?
他のものは一目瞭然なのですが、unevだけ全く見当がつきません。
- 587 名前：デフォルトの名無しさん mailto:sage [2005/07/14(木) 15:09:51 ]
- >>586
unevaluated (未評価)かな？
- 588 名前：586 mailto:sage [2005/07/14(木) 19:58:40 ]
- >>587
なるほど!
確かに「後で評価する式を格納しておく」という使い方をされてますから、
それで正解だと思います。ありがとうございました。
ああすっきりした! 今日は気持ちよく眠れる!
- 589 名前：デフォルトの名無しさん [2005/07/22(金) 14:37:51 ]
- xn(n ∈ N)は，次のように再帰的に定義することができる．
xn = xm×xm (n = 2m,m >= 1)
= x×xm×xm (n = 2m+1,m >= 0)
= 1 (n = 0)
これを利用して，xnを計算する2引数関数pow2を定義せよ．なお，再帰呼び出しの回数をできるだけ減らすようにすること．
これ教えてもらえませんでしょうか…
解答例をお願いします。。。
- 590 名前：589 [2005/07/22(金) 14:41:15 ]
- あぁ、書き忘れ。schemeです。
- 591 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:03:50 ]
- 夏休みの宿題くらい自分でやれ
- 592 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:27:50 ]
- 「できるだけ」ってのがひっかかるな。
- 593 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:39:49 ]
- どうしてもループに直せないおバカ救済用じゃね?
- 594 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 15:55:59 ]
- Lispもschemeもうぜえええええええええ
- 595 名前：589 [2005/07/22(金) 16:02:10 ]
- 出来ないからこうして書いてるんです( ´,_ゝ`)
- 596 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 16:14:52 ]
- 出来ないなら教官に質問しにいくとかすれば?
出来ないことを色々考えて出来るようになるのが学生の仕事だろ?
ロクに考えもせずに答教えろとか言う奴は単位なぞ落としてしまえ。
- 597 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 16:36:44 ]
- 最近の小学校はScheme教えてるのか。すごいな。
- 598 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 18:16:05 ]
- ※しょうがくせいのみんなへ
・なつやすみのしゅくだいは、じぶんでやりましょう。
- 599 名前：?デフォルトの名無しさん mailto:sage [2005/07/22(金) 22:03:21 ]
- Schemeの問題で
>再帰呼び出しの回数をできるだけ減らすようにすること
ってのはどんなんだろうね？
再帰をなるべく末尾再帰にしろってんならいいんだけど。
- 600 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 23:29:41 ]
- x は関数または演算子なんだよね？x×(xm×xm)って、演算子と整数の
積なの？意味がわからない。
- 601 名前：デフォルトの名無しさん mailto:sage [2005/07/22(金) 23:43:50 ]
- 頭悪いのを披露するためだけにわざわざ横から出てきてごくろうさん。
- 602 名前：600 mailto:sage [2005/07/22(金) 23:45:57 ]
- あ、問題を読み間違えていた。
- 603 名前：ビッケ ◆Jyl0Z1ahKc mailto:sage [2005/07/22(金) 23:52:54 ]
- xnなどと書かれているのはベキ乗 x^n のことでしょう。
「再帰呼び出しの回数」については、設問中のベキ乗の定義を見ると
再帰呼び出しのネスティングの深さのことを言ってるのかも知れませんね。
その授業（？）でそういうことを扱った直後の演習問題とか。
「できるだけ」なんていわれても困るけど、設問中の定義に従って
ネスティングの深さがO(log n)となる定義を書けばOKということなのかも。
- 604 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:02:33 ]
- ちゃんと自分の頭で噛み砕いて質問すれば親切な香具師は答えてくれる
かもしれんが、ここまで露骨に「宿題やって」だと誰も答えてくれんわな。
- 605 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:12:28 ]
- これ、ループに直せるの？定義が再帰的だから、どうしてもループには出来ないや。
末尾再帰も無理っぽい。
結局、let (let*) で途中経過をまとめるぐらいしかできないよ。こまった。
- 606 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:19:22 ]
- これ定義どおり実装するなら幼稚園児向けの問題で面白くもなんともないじゃん。
おまいら小学生ならもっと頭を使おうぜ。ｗ
- 607 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:19:34 ]
- (define (pow2 x n)
(let loop ((x x) (n n) (r 1))
(if (= n 0) r
(loop (* x x) (quotient n 2) (if (even? n) r (* r x))))))
- 608 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:33:24 ]
- >>607
きれいだけど、定義から離れすぎてない？
漏れの頭では、>>589 の定義からは、これを自明には導き出せない…。
- 609 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 00:47:05 ]
- >>607 が >>589 の定義と同値かどうかは興味深い問題だね。
"1" が "×" の単位元でない場合とか "×" が可換でない
場合とかを考えるとちゃんとした証明が必要かも。
- 610 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 01:58:59 ]
- (define (pow2 x n) (apply * (vector->list (make-vector n x))))
- 611 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 02:10:26 ]
- >>608
>>589 をそのまま実装すると
(define (pow2 x n)
(if (= n 0) 1
(let ((x1 (pow2 x (quotient n 2))))
(* x1 x1 (if (even? n) 1 x)))))
x^n * x^n = (x * x)^n だから
(define (pow2 x n)
(if (= n 0) 1
(* (pow2 (* x x) (quotient n 2)) (if (even? n) 1 x))))
末尾再帰に変換して >>607
- 612 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 02:30:33 ]
- >>611
ありがとう。おかげで疑問点がはっきりしてきました。
x^n * x^n = (x * x)^n って、使っていいの？
我々は pow2 が累乗を返す関数だと知っているから、この変形は自然に見えるけど、
この問題で使っていいのは、あくまで
pow2(x, 2n) = pow2(x, n) * pow2(x, n)
pow2(x, 2n + 1) = x * pow2(x, n) * pow2(x, n)
pow2(x, 0) = 1
の3式だけではないんだろうか？
- 613 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 02:53:57 ]
- なるほど、確かに
pow2(x * x, n) = pow2(x, n) * pow2(x, n) は自明ではないな。
- 614 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 03:24:59 ]
- (define pow2 expt)
- 615 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 03:43:39 ]
- >>612-613
pow2(x, 0) * pow2(x, 0) = pow2(x * x, 0) = 1
pow2(x, n) * pow2(x, n) = pow2(x * x, n) とすると
定義より pow2(x, n + 1) = x * pow2(x, n) (これも証明する?) なので
pow2(x, n + 1) * pow2(x, n + 1) = x * pow2(x, n) * x * pow2(x, n)
= (x * x) * (pow2(x, n) * pow2(x, n)) = (x * x) * pow2(x * x, n)
= pow2(x * x, n + 1)
以上から数学的帰納法により pow2(x, n) * pow2(x, n) = pow2(x * x, n)
- 616 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 05:11:48 ]
- >>615
数学的帰納法を使ったら pow2 の一般項 =x^n だって証明できてしまうと思われ。
そもそも関数の再帰的定義とは数学的帰納法を機械にやらせることなのに、
それを人間がやってしまったら本末転倒ではないかと。
- 617 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 06:39:58 ]
- ん? 元々 x^n を求める pow2(x, n) を定義せよって話でしょ。
x^2n = x^n * x^n
x^(2n+1) = x * x^n * x^n
x^0 = 1
となる性質を使えって条件があるだけで。
- 618 名前：デフォルトの名無しさん mailto:sage [2005/07/23(土) 10:34:49 ]
- 求める関数を pow2(x,n), s(x,n)=log_x pow2(x,n) とおくと、pow2 漸化式は次のようになる。
s(0,x)=0
s(2n,x)=2*s(n,x)
s(2n+1,x)=2*s(n,x)+1
ここまで見ると何となく s(n,x)=n になりそうな事が見えて来るが、
帰納法を使わず直観的に考えてみる。
s(n,x)の",x"を以後省略することとし、
nの2進表記を b_n...b_1b_0 とすると
s(b_n...b_1b_0)
=2*s(b_n...b_1)+b_0
=4*s(b_n...b_2)+2*b_1+b_0
...
=2^n*b_n+...+2*b_1+b_0
すなわち s(n)=n となる。
よって pow2(x,n)=x^n である。
故に>>614
- 619 名前：デフォルトの名無しさん mailto:sage [2005/07/24(日) 19:52:58 ]
- でもってexptを高速化する手法の一つが今回の問題だったんでないかい？
- 620 名前：デフォルトの名無しさん mailto:sage [2005/07/24(日) 20:17:31 ]
- ヒント：exptは浮動小数でも(略)
- 621 名前：デフォルトの名無しさん mailto:sage [2005/07/24(日) 21:58:13 ]
- R5RS には (expt EXACT INTEGER) => EXACT とは書いてないから
(define (expt x n) (exp (* (log x) n))) な実装もアリ。
だから処理系に依存せずに EXACT ^ INTEGER => EXACT が欲しければ
自前で書くしかない。
Common Lisp だと (expt RATIONAL INTEGER) => RATIONAL が保証
されてるのに……
- 622 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 08:43:33 ]
- >>621
ふが〜 おれ (expt 2 128) とかがEXACT INTEGERで正確に得られることを期待してコード書いてたけど、これ処理系依存になっちまうのか....いたいぜ。
- 623 名前：デフォルトの名無しさん mailto:sage [2005/07/25(月) 08:53:40 ]
- >>620
意味不明。（略）が（おれは無知です）の意味ならどうでもいいけど。
|
 |
