考えるの面倒臭くなってmapとapplyで全て済ましたというメモ。 (define (ExGCD x y) ;;;Input: x, y in Z ;;;Output: a and b s.t. ax + by = gcd(a,b) (let loop ((r0 x) (r1 y) (a0 1) (a1 0) (b0 0) (b1 1)) (if (= r1 0) (values r0 a0 b0) (receive (q …

誰の役に立つのか分からないけど. 分岐が意外と多い. Jacobi記号はLegendre記号の一般化になっているので, Legendre記号もこれで求められますよ. (define (Jacobi a n) (cond ((= a 0) 0) ((= a -1) (cond ((= (modulo n 4) 1) 1) ((= (modulo n 4) 3) -1)))…

slib - Mathematical Packages 何でMiller-RabinじゃなくってSolovay-Strassenなんだろう? 計算量的に特してるところあったかな?

参考: d:id:odz:20080229:1204287954 Project Euler用のメモ 100万までの各数について真の約数の和を求めることを考える. C系だとこんな感じ. long[] a; a.length = 1000000; for (long i = 2; i < 1000000; i++){ for (j = 2; j * i < 1000000; j++){ a[j *…