Fermat の小定理 - hattorix0's blog
SICP を読んでいる時に、いつもつまってしまうのでまとめてみる。 概要 Fermat の小定理 - P.28 n を素数，a を n より小さい正の任意の整数とすると，a の n 乗は n を法として a と合同である． そして、それをテストするコードが下記である。 (define (square n) (* n n)) (define (even? n) (= (remainder n 2) 0)) ;; gosh用 (define (random n) (use srfi-27) (random-integer n)) (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* bas
数学ガールを読むぞぉ 7 - フィボナッチ数列の一般項(2) - ボクノス
フィボナッチ数列の一般項の続きです。 フィボナッチの一般項は、 なんですが、(1 + √5)^nの計算が重い。結局n回展開しなければならないため、計算回数は反復の時と変わらなかった。桁落ちしてしまうので、浮動小数点は使いたくないし・・・。 むむぅ・・・と考え。 あ。 あらかじめ展開してやればいいじゃないか！！ ということで、√5をxと置きます。 だいぶスッキリです。 上の部分だけ計算すると、 0 : 1 - 1 = 0 1 : (1 + x) - (1 - x) = 2x 2 : (1 + 2x + x^2) - (1 - 2x + x^2) = 4x 3 : (1 + 3x + 3x^2 + x^3) - (1 - 3x + 3x^2 - x^3) = 6x + 2x^3 4 : ... = 8x + 8x^3 5 : = 10x + 20x^3 + 2x^5 6 : = 12x + 4
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
