Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | imported v1.0.0 |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk | v1.0.0 |
Files: | files | file ages | folders |
SHA3-256: |
088758e92211480bb165995daf175bcd |
User & Date: | murphy 2018-08-18 15:56:32.071 |
Context
2018-08-18
| ||
15:57 | imported v1.0.1 check-in: 529ec5356a user: murphy tags: trunk, v1.0.1 | |
15:56 | imported v1.0.0 check-in: 088758e922 user: murphy tags: trunk, v1.0.0 | |
15:52 | initial empty check-in check-in: 4ab785d87f user: murphy tags: trunk | |
Changes
Added modular-arithmetic.meta.
> > > > > > > > > | 1 2 3 4 5 6 7 8 9 | ((egg "modular-arithmetic.egg") (files "modular-arithmetic.setup" "modular-arithmetic.meta" "modular-arithmetic.scm" "tests/run.scm") (needs numbers matchable) (test-depends test) (category math) (synopsis "Modular Arithmetic on Finite Fields") (author "Thomas Chust") (doc-from-wiki) (license "BSD")) |
Added modular-arithmetic.scm.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | (require-library srfi-1 numbers matchable) (module modular-arithmetic (xgcd mod+ mod- mod* mod/ modexpt with-modulus) (import (except scheme + - * / = > < >= <= number->string string->number exp log sin cos tan asin acos atan expt sqrt quotient modulo remainder numerator denominator abs max min gcd lcm positive? negative? odd? even? zero? exact? inexact? floor ceiling truncate round inexact->exact exact->inexact number? complex? real? rational? integer? real-part imag-part magnitude) (except chicken add1 sub1 signum bitwise-and bitwise-ior bitwise-xor bitwise-not arithmetic-shift) srfi-1 numbers) (import-for-syntax scheme chicken matchable) ;; Extended GCD (define (xgcd a b) (let-values ([(q m) (quotient&modulo a b)]) (if (zero? m) (values 0 1) (let-values ([(x y) (xgcd b m)]) (values y (- x (* y q))))))) ;; Modular addition generator (define ((mod+ modulus) . ns) (fold (lambda (n a) (modulo (+ a n) modulus)) 0 ns)) ;; Modular subtraction and negation generator (define (mod- modulus) (case-lambda [(a) (modulo (- a) modulus)] [(a . ns) (fold (lambda (n a) (modulo (- a n) modulus)) a ns)])) ;; Modular multiplication generator (define ((mod* modulus) . ns) (fold (lambda (n a) (modulo (* a n) modulus)) 1 ns)) ;; Modular division and inversion generator (define (mod/ modulus) (define (inverse a) (if (= a 1) 1 (let-values ([(1/a n) (xgcd a modulus)]) (if (zero? n) (error 'mod/ "operand and modulus are not coprime" a modulus) 1/a)))) (case-lambda [(a) (modulo (inverse a) modulus)] [(a . ns) (fold (lambda (n a) (modulo (* a (inverse n)) modulus)) a ns)])) ;; Modular exponentiation generator (define (modexpt modulus) (let ([* (mod* modulus)] [/ (mod/ modulus)]) (lambda (base exponent) (let loop ([a 1] [base (if (negative? exponent) (/ base) base)] [exponent (abs exponent)]) (if (positive? exponent) (loop (if (zero? (bitwise-and exponent 1)) a (* a base)) (* base base) (arithmetic-shift exponent -1)) a))))) ;; Syntax to overload +, add1, -, sub1, *, / and expt with modular versions (define-syntax with-modulus (er-macro-transformer (lambda (stx rename id=) (match stx [(with-modulus modulus body ...) (let ([~let (rename 'let)] [~letrec (rename 'letrec)] [~modulus (rename 'modulus)]) `(,~let ([,~modulus ,modulus]) (,~letrec ([+ (,(rename 'mod+) ,~modulus)] [add1 (lambda (n) (+ n 1))] [- (,(rename 'mod-) ,~modulus)] [sub1 (lambda (n) (- n 1))] [* (,(rename 'mod*) ,~modulus)] [/ (,(rename 'mod/) ,~modulus)] [expt (,(rename 'modexpt) ,~modulus)]) ,@body)))])))) ) |
Added modular-arithmetic.setup.
> | 1 | (standard-extension 'modular-arithmetic '1.0.0) |
Added tests/run.scm.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | (require-extension test modular-arithmetic) (test-group "Modular Arithmetic" (test "Extended GCD" '(3 -2) (receive (xgcd 15 21))) (test "Addition" 3 (with-modulus 7 (+ 1 2 3 4))) (test "Subtraction" 2 (with-modulus 5 (- 4 7))) (test "Multiplication" 50 (with-modulus 66 (* 4 8 16))) (test "Division" 1 (with-modulus #xE95E4A5F737059DC60DFC7AD95B3D8139515620F ((lambda (x) (/ x x)) 8977423876425786243783246))) (test "Exponentiation" 8 (with-modulus 13 (expt 5 3))) ) |