[ create a new paste ] login | about

Link: http://codepad.org/NDMl4XkI    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Aug 4:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
; big modular exponentiation

(define p 34534985349875439875439875349875)
(define q 93475349759384754395743975349573495)
(define m (+ (expt 10 9) 7))

(define (expm b e m)
  (define (m* x y) (modulo (* x y) m))
  (cond ((zero? e) 1)
        ((even? e) (expm (m* b b) (/ e 2) m))
        (else (m* b (expm (m* b b) (/ (- e 1) 2) m)))))

(time (display (expm p q m)) (display " "))

(define (f p q m) (expm (modulo p m) (modulo q (- m 1)) m))

(time (display (f p q m)) (display " "))


Output:
1
2
735851262 cpu time: 0 real time: 3 gc time: 0
735851262 cpu time: 0 real time: 1 gc time: 0


Create a new paste based on this one


Comments: