From be41b252ac81d11b3e9cbbddc514c2e17e1f20fc Mon Sep 17 00:00:00 2001 From: Sam Ritchie Date: Wed, 7 Apr 2021 06:18:21 -0600 Subject: [PATCH 1/5] tiny updates --- src/sicmutils/calculus/derivative.cljc | 51 ++-------- src/sicmutils/calculus/form_field.cljc | 10 +- src/sicmutils/env.cljc | 2 +- src/sicmutils/euclid.cljc | 6 +- src/sicmutils/generic.cljc | 17 +++- src/sicmutils/matrix.cljc | 68 ++++++++----- src/sicmutils/modint.cljc | 100 +++++++++++++------ src/sicmutils/numbers.cljc | 27 ++++- src/sicmutils/numsymb.cljc | 37 ++++--- src/sicmutils/structure.cljc | 4 + src/sicmutils/util/aggregate.cljc | 14 +++ src/sicmutils/util/permute.cljc | 5 +- test/sicmutils/calculus/derivative_test.cljc | 69 +++++++++++++ test/sicmutils/laws.cljc | 5 +- test/sicmutils/matrix_test.cljc | 12 +-- test/sicmutils/modint_test.cljc | 10 +- 16 files changed, 290 insertions(+), 147 deletions(-) diff --git a/src/sicmutils/calculus/derivative.cljc b/src/sicmutils/calculus/derivative.cljc index 80f66ba2c..a17955d0f 100644 --- a/src/sicmutils/calculus/derivative.cljc +++ b/src/sicmutils/calculus/derivative.cljc @@ -456,6 +456,12 @@ (o/make-operator #(g/partial-derivative % []) g/derivative-symbol)) +(defn D-as-matrix [F] + (fn [s] + (matrix/s->m (s/compatible-shape (F s)) + ((D F) s) + s))) + (defn partial "Returns an operator that, when applied to a function `f`, produces a function that computes the partial derivative of `f` at the (zero-based) slot index @@ -464,51 +470,6 @@ (o/make-operator #(g/partial-derivative % selectors) `(~'partial ~@selectors))) -(def ^{:doc "Operator that takes a function `f` and returns a new function that - calculates the [Gradient](https://en.wikipedia.org/wiki/Gradient) of `f`. - - The related [[D]] operator returns a function that produces a structure of the - opposite orientation as [[Grad]]. Both of these functions use forward-mode - automatic differentiation."} - Grad - (-> (fn [f] - (f/compose s/opposite - (g/partial-derivative f []))) - (o/make-operator 'Grad))) - -(def ^{:doc "Operator that takes a function `f` and returns a function that - calculates the [Divergence](https://en.wikipedia.org/wiki/Divergence) of - `f` at its input point. - - The divergence is a one-level contraction of the gradient."} - Div - (-> (f/compose g/trace Grad) - (o/make-operator 'Div))) - -(def ^{:doc "Operator that takes a function `f` and returns a function that - calculates the [Curl](https://en.wikipedia.org/wiki/Curl_(mathematics)) of `f` - at its input point. - - `f` must be a function from $\\mathbb{R}^3 \\to \\mathbb{R}^3$."} - Curl - (-> (fn [f-triple] - (let [[Dx Dy Dz] (map partial [0 1 2]) - fx (f/get f-triple 0) - fy (f/get f-triple 1) - fz (f/get f-triple 2)] - (s/up (g/- (Dy fz) (Dz fy)) - (g/- (Dz fx) (Dx fz)) - (g/- (Dx fy) (Dy fx))))) - (o/make-operator 'Curl))) - -(def ^{:doc "Operator that takes a function `f` and returns a function that - calculates the [Vector - Laplacian](https://en.wikipedia.org/wiki/Laplace_operator#Vector_Laplacian) of - `f` at its input point."} - Lap - (-> (f/compose g/trace (g/* Grad Grad)) - (o/make-operator 'Lap))) - ;; ## Derivative Utilities ;; ;; Functions that make use of the differential operators defined above in diff --git a/src/sicmutils/calculus/form_field.cljc b/src/sicmutils/calculus/form_field.cljc index 3c501ce9c..facc7597c 100644 --- a/src/sicmutils/calculus/form_field.cljc +++ b/src/sicmutils/calculus/form_field.cljc @@ -450,11 +450,11 @@ (assert (= (count args) n) "Wrong number of args to alternation") (g/* (/ 1 (factorial n)) - (apply g/+ - (map (fn [permutation parity] - (g/* parity (apply form permutation))) - (permute/permutation-sequence args) - (cycle [1 -1])))))] + (ua/generic-sum + (map (fn [permutation parity] + (g/* parity (apply form permutation))) + (permute/permutation-sequence args) + (cycle [1 -1])))))] (procedure->nform-field alternation n `(~'Alt ~(v/freeze form))))))) diff --git a/src/sicmutils/env.cljc b/src/sicmutils/env.cljc index a18133b6b..62610146b 100644 --- a/src/sicmutils/env.cljc +++ b/src/sicmutils/env.cljc @@ -240,7 +240,7 @@ constant [Pi](https://en.wikipedia.org/wiki/Pi)."} #?(:cljs [sicmutils.ratio ratio? rationalize numerator denominator]) [sicmutils.util bigint? #?@(:cljs [bigint])] - [sicmutils.function arity compose arg-shift arg-scale I] + [sicmutils.function arity compose arg-shift arg-scale] [sicmutils.modint chinese-remainder] [sicmutils.operator commutator anticommutator] [sicmutils.series binomial-series partial-sums] diff --git a/src/sicmutils/euclid.cljc b/src/sicmutils/euclid.cljc index bce047f28..dd277727a 100644 --- a/src/sicmutils/euclid.cljc +++ b/src/sicmutils/euclid.cljc @@ -57,7 +57,5 @@ ;; multimethod implementation for basic numeric types. -(defmethod g/gcd :default [a b] (gcd a b)) - -(defmethod g/lcm :default [a b] - (g/abs (g/divide (g/* a b) (g/gcd a b)))) +(defmethod g/gcd :default [a b] + (gcd a b)) diff --git a/src/sicmutils/generic.cljc b/src/sicmutils/generic.cljc index 2864fa5ea..41903e3bb 100644 --- a/src/sicmutils/generic.cljc +++ b/src/sicmutils/generic.cljc @@ -178,11 +178,13 @@ ([] 1) ([x] x) ([x y] - (cond (and (v/numerical? x) (v/zero? x)) (v/zero-like y) - (and (v/numerical? y) (v/zero? y)) (v/zero-like x) - (v/one? x) y - (v/one? y) x - :else (mul x y))) + (let [numx? (v/numerical? x) + numy? (v/numerical? y)] + (cond (and numx? (v/zero? x)) (v/zero-like y) + (and numy? (v/zero? y)) (v/zero-like x) + (and numx? (v/one? x)) y + (and numy? (v/one? y)) x + :else (mul x y)))) ([x y & more] (reduce * (* x y) more))) @@ -457,6 +459,11 @@ multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of the two inputs `a` and `b`.") +(defmethod lcm :default [a b] + (abs + (divide (* a b) + (gcd a b)))) + ;; ### Trigonometric functions (declare sin) diff --git a/src/sicmutils/matrix.cljc b/src/sicmutils/matrix.cljc index fe97d46dd..3d7a00a4d 100644 --- a/src/sicmutils/matrix.cljc +++ b/src/sicmutils/matrix.cljc @@ -27,7 +27,6 @@ some core-some} #?@(:cljs [:exclude [get-in some]])) (:require [sicmutils.differential :as d] - [sicmutils.expression :as x] [sicmutils.function :as f] [sicmutils.generic :as g] [sicmutils.series :as series] @@ -38,7 +37,7 @@ #?(:clj (:import [clojure.lang Associative AFn IFn Sequential]))) -(declare fmap generate I identity-like identity? m:=) +(declare fmap identity-like identity? m:=) (derive ::square-matrix ::matrix) (derive ::column-matrix ::matrix) @@ -81,7 +80,7 @@ Associative (assoc [_ k entry] (Matrix. r c (assoc v k entry))) (containsKey [_ k] (contains? v k)) - (entryAt [_ k] (.entryAt v k)) + (entryAt [_ k] (.entryAt ^Associative v k)) (count [_] (count v)) (seq [_] (seq v)) (valAt [_ key] (get v key)) @@ -540,11 +539,14 @@ [m u] (when (not= (num-cols m) (count u)) (u/illegal "matrix and tuple incompatible for multiplication")) - (s/up* (map (fn [i] - (reduce g/+ (for [k (range (num-cols m))] - (g/* (core-get-in m [i k]) - (get u k))))) - (range (num-rows m))))) + (s/up* + (map (fn [i] + (ua/generic-sum + (fn [k] + (g/* (core-get-in m [i k]) + (get u k))) + 0 (num-cols m))) + (range (num-rows m))))) (defn- d*M "Multiply a matrix `m` by down tuple `d` on the left. The return value has @@ -554,10 +556,11 @@ (u/illegal "matrix and tuple incompatible for multiplication")) (s/down* (map (fn [i] - (reduce g/+ (for [k (range (num-rows m))] - (g/* (get d k) - (core-get-in m [i k]) - )))) + (ua/generic-sum + (fn [k] + (g/* (get d k) + (core-get-in m [i k]))) + 0 (num-rows m))) (range (num-cols m))))) (def ^{:dynamic true @@ -580,6 +583,15 @@ (g/* ms (s/unflatten (s/basis-unit nups j) rs))))))) +(defn as-matrix + "Any one argument function of a structure can be seen as a matrix. This is only + useful if the function has a linear multiplier (e.g. derivative)" + [F] + (fn [s] + (let [v (F s)] + (s->m + (s/compatible-shape (g/* v s)) v s)))) + (defn nth-row "Returns the `n`-th row of the supplied matrix `m` as a `down` structure." [m n] @@ -681,13 +693,18 @@ "Returns the submatrix of `m` generated by taking - rows from `lowrow` -> `hirow`, - - columns from `lowcol` -> `hicol`" - [m lowrow hirow lowcol hicol] - (generate (inc (- hirow lowrow)) - (inc (- hicol lowcol)) - (fn [i j] - (core-get-in m [(+ i lowrow) - (+ j lowcol)])))) + - columns from `lowcol` -> `hicol` + + TODO test that this can handle structures too." + [x lowrow hirow lowcol hicol] + (let [m (if (s/structure? x) + (square-structure-> x (fn [m _] m)) + x)] + (generate (inc (- hirow lowrow)) + (inc (- hicol lowcol)) + (fn [i j] + (core-get-in m [(+ i lowrow) + (+ j lowcol)]))))) (defn without "Returns the matrix formed by deleting the `i`-th row and `j`-th column of the @@ -733,11 +750,12 @@ 2 (let [[[a b] [c d]] m] (g/- (g/* a d) (g/* b c))) - (reduce g/+ (map g/* - (cycle [1 -1]) - (nth m 0) - (for [i (range (num-rows m))] - (determinant (without m 0 i))))))) + (ua/generic-sum + (map g/* + (cycle [1 -1]) + (nth m 0) + (for [i (range (num-rows m))] + (determinant (without m 0 i))))))) (defn cofactors "Returns the matrix of cofactors of the supplied square matrix `m`." @@ -763,7 +781,7 @@ 0 m 1 (->Matrix 1 1 [[(g/invert (core-get-in m [0 0]))]]) (let [C (cofactors m) - Δ (reduce g/+ (map g/* (nth m 0) (nth C 0)))] + Δ (apply g/+ (map g/* (nth m 0) (nth C 0)))] (fmap #(g/divide % Δ) (transpose C)))))) diff --git a/src/sicmutils/modint.cljc b/src/sicmutils/modint.cljc index c459a2a43..47c35b776 100644 --- a/src/sicmutils/modint.cljc +++ b/src/sicmutils/modint.cljc @@ -30,10 +30,9 @@ [sicmutils.util :as u] [sicmutils.value :as v])) -(defrecord ModInt [i m] - v/Numerical - (numerical? [_] true) +(declare mod:=) +(deftype ModInt [i m] v/Value (zero? [_] (v/zero? i)) (one? [_] (v/one? i)) @@ -43,12 +42,45 @@ (identity-like [_] (ModInt. (v/one-like i) m)) (freeze [_] (list 'modint i m)) (exact? [_] true) - (kind [_] ::modint)) + (kind [_] ::modint) + + #?@(:clj + [Object + (equals [this that] (mod:= this that)) + (toString [_] (str "[" i " mod " m "]"))] + + :cljs + [IEquiv + (-equiv [this that] (mod:= this thiat)) + + Object + (toString [_] (str "[" i " mod " m "]")) + + IPrintWithWriter + (-pr-writer [x writer _] + (write-all writer + "#object[sicmutils.modint.ModInt \"" + (.toString x) + "\"]"))])) (defn modint? "Returns true if `x` is an instance of [[ModInt]], false otherwise." [x] - (instance? x ModInt)) + (instance? ModInt x)) + +(defn residue [x] + (.-i ^ModInt x)) + +(defn modulus [x] + (.-m ^ModInt x)) + +(defn- mod:= [this that] + (if (modint? that) + (and (= (modulus this) + (modulus that)) + (v/= (residue this) + (residue that))) + (v/= (residue this) that))) (defn make "Returns an instance of [[ModInt]] that represents integer `i` with integral @@ -60,13 +92,13 @@ (defn- modular-binop [op] (fn [a b] - (if-not (= (:m a) (:m b)) + (if-not (= (modulus a) (modulus b)) (u/arithmetic-ex "unequal moduli") - (make (op (:i a) (:i b)) (:m a))))) + (make (op (residue a) (residue b)) (modulus a))))) (defn- invert "Modular inverse. JVM implementation uses the native BigInt implementation." - ([m] (invert (:i m) (:m m))) + ([m] (invert (residue m) (modulus m))) ([i modulus] #?(:clj (try (-> (biginteger i) @@ -86,7 +118,7 @@ "Modular exponentiation, more efficient on the JVM." [base pow modulus] #?(:clj (let [base (if (neg? pow) - (:i (invert base modulus)) + (residue (invert base modulus)) base)] (-> (.modPow (biginteger base) (.abs (biginteger pow)) @@ -103,9 +135,9 @@ (defn chinese-remainder "[Chinese Remainder Algorithm](https://en.wikipedia.org/wiki/Chinese_remainder_theorem). - Accepts a sequence of [[ModInt]] instances (where the modulus `:m` of + Accepts a sequence of [[ModInt]] instances (where the `modulus` of all [[ModInt]] instances are relatively prime), and returns a [[ModInt]] `x` - such that `(:i input) == (mod x (:m input))`. + such that `(residue input) == (mod x (modulus input))`. For example: @@ -113,15 +145,17 @@ (let [a1 (m/make 2 5) a2 (m/make 3 13)] [(= 42 (chinese-remainder a1 a2)) - (= (:i a1) (mod cr (:m a1))) - (= (:i a2) (mod cr (:m a2)))]) + (= (residue a1) (mod cr (modulus a1))) + (= (residue a2) (mod cr (modulus a2)))]) ;;=> [true true true] ```" [& modints] - (let [prod (transduce (map :m) g/* modints) - xform (map (fn [{:keys [i m]}] - (let [c (g/quotient prod m)] - (g/* i c (:i (invert c m))))))] + (let [prod (transduce (map modulus) g/* modints) + xform (map (fn [mi] + (let [i (residue mi) + m (modulus mi) + c (g/quotient prod m)] + (g/* i c (residue (invert c m))))))] (-> (transduce xform g/+ modints) (g/modulo prod)))) @@ -134,7 +168,7 @@ (defn- div [a b] (mul a (invert b))) -(defmethod g/integer-part [::modint] [a] (:i a)) +(defmethod g/integer-part [::modint] [a] (residue a)) (defmethod g/fractional-part [::modint] [a] 0) (defmethod g/floor [::modint] [a] a) (defmethod g/ceiling [::modint] [a] a) @@ -142,23 +176,27 @@ (defmethod g/mul [::modint ::modint] [a b] (mul a b)) (defmethod g/div [::modint ::modint] [a b] (div a b)) (defmethod g/sub [::modint ::modint] [a b] (sub a b)) -(defmethod g/negate [::modint] [a] (make (g/negate (:i a)) (:m a))) +(defmethod g/negate [::modint] [a] (make (g/negate (residue a)) (modulus a))) (defmethod g/invert [::modint] [a] (invert a)) -(defmethod g/magnitude [::modint] [{:keys [i m] :as a}] (g/modulo i m)) -(defmethod g/abs [::modint] [{:keys [i m] :as a}] - (if (g/negative? i) - (make i m) - a)) +(defmethod g/magnitude [::modint] [a] + (g/modulo (residue a) + (modulus a))) + +(defmethod g/abs [::modint] [a] + (let [i (residue a)] + (if (g/negative? i) + (make i (modulus a)) + a))) (defmethod g/quotient [::modint ::modint] [a b] (mul a (invert b))) (defmethod g/remainder [::modint ::modint] [a b] (remainder a b)) (defmethod g/modulo [::modint ::modint] [a b] (modulo a b)) (defmethod g/exact-divide [::modint ::modint] [a b] (mul a (invert b))) -(defmethod g/negative? [::modint] [a] (g/negative? (:i a))) +(defmethod g/negative? [::modint] [a] (g/negative? (residue a))) ;; A more efficient exponent implementation is available on the JVM. -(defmethod g/expt [::v/integral ::modint] [a b](mod-expt a (:i b) (:m b))) -(defmethod g/expt [::modint ::v/integral] [a b] (mod-expt (:i a) b (:m a))) +(defmethod g/expt [::v/integral ::modint] [a b](mod-expt a (residue b) (modulus b))) +(defmethod g/expt [::modint ::v/integral] [a b] (mod-expt (residue a) b (modulus a))) (defmethod g/solve-linear [::modint ::modint] [a b] (div b a)) (defmethod g/solve-linear-right [::modint ::modint] [a b] (div a b)) @@ -166,11 +204,11 @@ ;; Methods that allow interaction with other integral types. The first block is ;; perhaps slightly more efficient: (doseq [op [g/add g/mul g/sub]] - (defmethod op [::v/integral ::modint] [a b] (make (op a (:i b)) (:m b))) - (defmethod op [::modint ::v/integral] [a b] (make (op (:i a) b) (:m a)))) + (defmethod op [::v/integral ::modint] [a b] (make (op a (residue b)) (modulus b))) + (defmethod op [::modint ::v/integral] [a b] (make (op (residue a) b) (modulus a)))) ;; The second block promotes any integral type to a ModInt before operating. (doseq [op [g/div g/solve-linear g/solve-linear-right g/quotient g/remainder g/exact-divide]] - (defmethod op [::v/integral ::modint] [a b] (op (make a (:m b)) b)) - (defmethod op [::modint ::v/integral] [a b] (op a (make b (:m a))))) + (defmethod op [::v/integral ::modint] [a b] (op (make a (modulus b)) b)) + (defmethod op [::modint ::v/integral] [a b] (op a (make b (modulus a))))) diff --git a/src/sicmutils/numbers.cljc b/src/sicmutils/numbers.cljc index f38e19f45..46ca81a5c 100644 --- a/src/sicmutils/numbers.cljc +++ b/src/sicmutils/numbers.cljc @@ -43,8 +43,9 @@ #?(:cljs (:import (goog.math Long Integer)) :clj - (:import [clojure.lang BigInt Ratio] - [java.math BigInteger]))) + (:import (clojure.lang BigInt Ratio) + (java.math BigInteger) + (org.apache.commons.math3.util ArithmeticUtils)))) ;; "Backstop" implementations that apply to anything that descends from ;; ::v/real. @@ -175,7 +176,27 @@ ;; type system. #?(:clj ;; Efficient, native GCD on the JVM. - (defmethod g/gcd [BigInteger BigInteger] [a b] (.gcd a b))) + (do (defmethod g/gcd [BigInteger BigInteger] [a b] + (.gcd ^BigInteger a + ^BigInteger b)) + + (defmethod g/gcd [Long Long] [a b] + (ArithmeticUtils/gcd ^long a ^long b)) + + (defmethod g/gcd [BigInteger Long] [a b] + (.gcd ^BigInteger a (biginteger b))) + + (defmethod g/gcd [Long BigInteger] [a b] + (.gcd (biginteger a) b)) + + (defmethod g/gcd [Integer Integer] [a b] + (ArithmeticUtils/gcd ^int a ^int b)) + + (defmethod g/gcd [BigInteger Integer] [a b] + (.gcd ^BigInteger a (biginteger b))) + + (defmethod g/gcd [Integer BigInteger] [a b] + (.gcd (biginteger a) b)))) #?(:cljs (do (defmethod g/expt [::v/native-integral ::v/native-integral] [a b] diff --git a/src/sicmutils/numsymb.cljc b/src/sicmutils/numsymb.cljc index 394692bc8..e69fcadec 100644 --- a/src/sicmutils/numsymb.cljc +++ b/src/sicmutils/numsymb.cljc @@ -28,6 +28,8 @@ [sicmutils.value :as v] [sicmutils.util :as u])) +(def ^:dynamic *incremental-simplifier* nil) + (def operator first) (def operands rest) @@ -97,7 +99,9 @@ (sum? a) (cond (sum? b) `(~'+ ~@(operands a) ~@(operands b)) :else `(~'+ ~@(operands a) ~b)) (sum? b) `(~'+ ~a ~@(operands b)) - :else `(~'+ ~a ~b)))) + :else `(~'+ ~a ~b))) + ([a b & more] + (reduce add (add a b) more))) (defn- sub [a b] (cond (and (v/number? a) (v/number? b)) (g/sub a b) @@ -106,10 +110,12 @@ (= a b) 0 :else `(~'- ~a ~b))) -(defn- sub-n [& args] - (cond (nil? args) 0 - (nil? (next args)) (g/negate (first args)) - :else (sub (first args) (reduce add (next args))))) +(defn- sub-n + ([] 0) + ([x] (g/negate x)) + ([x y] (sub x y)) + ([x y & more] + (sub x (apply add (cons y more))))) (defn- mul ([] 1) @@ -129,9 +135,12 @@ (product? a) (cond (product? b) `(~'* ~@(operands a) ~@(operands b)) :else `(~'* ~@(operands a) ~b)) (product? b) `(~'* ~a ~@(operands b)) - :else `(~'* ~a ~b)))) + :else `(~'* ~a ~b))) + ([a b & more] + (reduce mul (mul a b) more))) -(defn- div [a b] +(defn- div + [a b] (cond (and (v/number? a) (v/number? b)) (g/div a b) (v/number? a) (if (v/zero? a) a `(~'/ ~a ~b)) (v/number? b) (cond (v/zero? b) (u/arithmetic-ex "division by zero") @@ -139,10 +148,12 @@ :else `(~'/ ~a ~b)) :else `(~'/ ~a ~b))) -(defn- div-n [arg & args] - (cond (nil? arg) 1 - (nil? args) (g/invert arg) - :else (div arg (reduce mul args)))) +(defn- div-n + ([] 1) + ([x] (div 1 x)) + ([x y] (div x y)) + ([x y & more] + (div x (apply mul (cons y more))))) (defn- modulo [a b] (mod-rem a b modulo 'modulo)) @@ -547,9 +558,9 @@ 'and sym:and 'or sym:or 'not sym:not - '+ #(reduce add %&) + '+ add '- sub-n - '* #(reduce mul %&) + '* mul '/ div-n 'modulo modulo 'remainder remainder diff --git a/src/sicmutils/structure.cljc b/src/sicmutils/structure.cljc index f59d79dfe..d951efb8c 100644 --- a/src/sicmutils/structure.cljc +++ b/src/sicmutils/structure.cljc @@ -746,6 +746,10 @@ (v/zero-like (transpose s))) +(def ^{:doc "Alias for [[compatible-zero]]."} + dual-zero + compatible-zero) + (defn compatible-shape "Returns a structure compatible for multiplication with `s` down to a scalar, with the slots filled with gensyms." diff --git a/src/sicmutils/util/aggregate.cljc b/src/sicmutils/util/aggregate.cljc index 87b69c9ff..bfe7e4366 100644 --- a/src/sicmutils/util/aggregate.cljc +++ b/src/sicmutils/util/aggregate.cljc @@ -75,3 +75,17 @@ (apply g/+ xs)) ([f low high] (transduce (map f) g/+ (range low high)))) + +(defn halt-at + "Returns a transducer that ends transduction when `pred` (applied to the + aggregation in progress) returns true for an aggregation step." + [pred] + (fn [rf] + (fn + ([] (rf)) + ([result] + (rf result)) + ([result input] + (if (pred result) + (reduced result) + (rf result input)))))) diff --git a/src/sicmutils/util/permute.cljc b/src/sicmutils/util/permute.cljc index cc8460e05..1b1e36362 100644 --- a/src/sicmutils/util/permute.cljc +++ b/src/sicmutils/util/permute.cljc @@ -132,8 +132,9 @@ "Given a `permutation` (represented as a list of numbers), and a sequence `xs` to be permuted, construct the list so permuted." [permutation xs] - (map (fn [p] (nth xs p)) - permutation)) + (let [xs (vec xs)] + (map (fn [p] (get xs p)) + permutation))) (defn- index-of [v x] #?(:clj (.indexOf ^APersistentVector v x) diff --git a/test/sicmutils/calculus/derivative_test.cljc b/test/sicmutils/calculus/derivative_test.cljc index 22081e7bb..b59c8be3c 100644 --- a/test/sicmutils/calculus/derivative_test.cljc +++ b/test/sicmutils/calculus/derivative_test.cljc @@ -26,6 +26,7 @@ [sicmutils.calculus.derivative :as d :refer [D partial]] [sicmutils.complex :as c] [sicmutils.differential :as sd] + [sicmutils.expression :as x] [sicmutils.function :as f] [sicmutils.generic :as g :refer [acos asin atan cos sin tan cot sec csc @@ -595,6 +596,74 @@ (g/simplify))))))) (deftest moved-from-structure-and-matrix + (testing "as-matrix, D-as-matrix" + (let [Hamiltonian2 '(-> (UP Real + (UP Real Real) + (DOWN Real Real)) + Real) + S (s/up 't (s/up 'x 'y) (s/down 'p_x 'p_y)) + present (fn [expr] + (-> (simplify expr) + (x/substitute (v/freeze S) 'p)))] + (is (= '(matrix-by-rows + (up (((partial 0) H) p) + (((partial 1 0) H) p) + (((partial 1 1) H) p) + (((partial 2 0) H) p) + (((partial 2 1) H) p))) + (present + ((d/D-as-matrix (af/literal-function 'H Hamiltonian2)) + S))))) + + (let [C-general (af/literal-function + 'C '(-> (UP Real + (UP Real Real) + (DOWN Real Real)) + (UP Real + (UP Real Real) + (DOWN Real Real)))) + S (s/up 't (s/up 'x 'y) (s/down 'px 'py)) + present (fn [expr] + (-> (simplify expr) + (x/substitute (v/freeze S) 'p)))] + (is (= '(matrix-by-rows (up (((partial 0) C↑0) p) + (((partial 1 0) C↑0) p) + (((partial 1 1) C↑0) p) + (((partial 2 0) C↑0) p) + (((partial 2 1) C↑0) p)) + (up (((partial 0) C↑1↑0) p) + (((partial 1 0) C↑1↑0) p) + (((partial 1 1) C↑1↑0) p) + (((partial 2 0) C↑1↑0) p) + (((partial 2 1) C↑1↑0) p)) + (up (((partial 0) C↑1↑1) p) + (((partial 1 0) C↑1↑1) p) + (((partial 1 1) C↑1↑1) p) + (((partial 2 0) C↑1↑1) p) + (((partial 2 1) C↑1↑1) p)) + (up (((partial 0) C↑2_0) p) + (((partial 1 0) C↑2_0) p) + (((partial 1 1) C↑2_0) p) + (((partial 2 0) C↑2_0) p) + (((partial 2 1) C↑2_0) p)) + (up (((partial 0) C↑2_1) p) + (((partial 1 0) C↑2_1) p) + (((partial 1 1) C↑2_1) p) + (((partial 2 0) C↑2_1) p) + (((partial 2 1) C↑2_1) p))) + (present + ((matrix/as-matrix (D C-general)) S)))) + + (is (= '(matrix-by-rows (up 0 0 0 0 0) + (up 0 0 0 0 0) + (up 0 0 0 0 0) + (up 0 0 0 0 0) + (up 0 0 0 0 0)) + (simplify + ((- (d/D-as-matrix C-general) + (matrix/as-matrix (D C-general))) + S)))))) + (let [vs (s/up (s/up 'vx1 'vy1) (s/up 'vx2 'vy2)) diff --git a/test/sicmutils/laws.cljc b/test/sicmutils/laws.cljc index 05e388a89..39c89393e 100644 --- a/test/sicmutils/laws.cljc +++ b/test/sicmutils/laws.cljc @@ -237,8 +237,9 @@ (let [mul-check (if with-one? multiplicative-monoid multiplicative-semigroup)] - (additive-group opts generator type-name :commutative? true)) - (multiplicative-semigroup opts generator type-name :commutative? commutative?)) + (additive-group opts generator type-name :commutative? true) + (mul-check opts generator type-name :commutative? commutative?) + (mul-distributes-over-add opts generator type-name))) (defn field "A field is a type `a` that: diff --git a/test/sicmutils/matrix_test.cljc b/test/sicmutils/matrix_test.cljc index 0524cbd23..9c003270f 100644 --- a/test/sicmutils/matrix_test.cljc +++ b/test/sicmutils/matrix_test.cljc @@ -247,14 +247,14 @@ (testing "submatrix" (let [M (m/by-rows [1 2 3] [4 5 6] - [7 8 9])] + [7 8 9]) + SM (s/down (s/up 1 4 7) + (s/up 2 5 8) + (s/up 3 6 9))] (is (= (m/by-rows [1 2] [4 5]) - (m/submatrix M 0 1 0 1))) - - (is (= (m/by-rows [1 2] - [4 5]) - (m/submatrix M 0 1 0 1))))) + (m/submatrix M 0 1 0 1) + (m/submatrix SM 0 1 0 1))))) (checking "make-zero" 100 [m (gen/choose 0 10) n (gen/choose 0 10)] diff --git a/test/sicmutils/modint_test.cljc b/test/sicmutils/modint_test.cljc index cc933154f..47143921b 100644 --- a/test/sicmutils/modint_test.cljc +++ b/test/sicmutils/modint_test.cljc @@ -75,9 +75,9 @@ (checking "m^i matches simple implementation" 100 [m (sg/modint) e (gen/fmap g/abs sg/native-integral)] - (let [i (:i m) - modulus (:m m)] - (is (= (:i (g/expt m e)) + (let [i (m/residue m) + modulus (m/modulus m)] + (is (= (m/residue (g/expt m e)) (-> (g/expt (u/bigint i) (u/bigint e)) (g/modulo modulus)))))) @@ -113,8 +113,8 @@ a2 (m/make 3 13) cr (m/chinese-remainder a1 a2)] (is (= 42 cr)) - (is (= (:i a1) (mod cr (:m a1)))) - (is (= (:i a2) (mod cr (:m a2)))))))) + (is (= (m/residue a1) (mod cr (m/modulus a1)))) + (is (= (m/residue a2) (mod cr (m/modulus a2)))))))) (defn div-mul-inverse-test "Test that: From bcbc14f6fa9087c13d55310055b5a9f2e48fc358 Mon Sep 17 00:00:00 2001 From: Sam Ritchie Date: Wed, 7 Apr 2021 06:41:43 -0600 Subject: [PATCH 2/5] fix --- CHANGELOG.md | 22 ++++++++++++++++++++ src/sicmutils/env.cljc | 5 +++-- src/sicmutils/matrix.cljc | 9 ++++----- src/sicmutils/modint.cljc | 20 +++++++++++++------ test/sicmutils/modint_test.cljc | 32 ++++++++++++++++++++++++++++++ test/sicmutils/structure_test.cljc | 8 +++++++- 6 files changed, 82 insertions(+), 14 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 1ea7d8e3c..f3edb8509 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -2,6 +2,28 @@ ## [unreleased] +- From #342: + + - Added `sicmutils.calculus.derivative/D-as-matrix` and + `sicmutils.matrix/as-matrix`, ported from scmutils. + + - converted `sicmutils.modint.ModInt` to a `deftype`; this allows `ModInt` + instances to be `=` to non-`ModInt` numbers on the right, if the right side + is equal to the residue plus any integer multiple of the modulus. `v/=` + gives us this behavior with numbers on the LEFT too, and `ModInt` on the + right. + + - This change means that `:i` and `:m` won't return the residue and modulus + anymore. `sicmutils.modint` gains new `residue` and `modulus` functions to + access these attributes. + + - The JVM version of sicmutils gains more efficient `gcd` implementations + for `Integer` and `Long` (in addition to the existing native `BigInteger` + `gcd`), thanks to our existing Apache Commons-Math dependency. + + - `sicmutils.structure/dual-zero` aliases `compatible-zero` to match the + scmutils interface. Both are now aliased into `sicmutils.env`. + - From #339: - `Structure` instances can now hold metadata. diff --git a/src/sicmutils/env.cljc b/src/sicmutils/env.cljc index 62610146b..5a9c5b85c 100644 --- a/src/sicmutils/env.cljc +++ b/src/sicmutils/env.cljc @@ -240,7 +240,7 @@ constant [Pi](https://en.wikipedia.org/wiki/Pi)."} #?(:cljs [sicmutils.ratio ratio? rationalize numerator denominator]) [sicmutils.util bigint? #?@(:cljs [bigint])] - [sicmutils.function arity compose arg-shift arg-scale] + [sicmutils.function arity compose arg-shift arg-scale I] [sicmutils.modint chinese-remainder] [sicmutils.operator commutator anticommutator] [sicmutils.series binomial-series partial-sums] @@ -276,6 +276,7 @@ constant [Pi](https://en.wikipedia.org/wiki/Pi)."} simplify] [sicmutils.structure compatible-shape + compatible-zero dual-zero down mapr sumr orientation @@ -333,7 +334,7 @@ constant [Pi](https://en.wikipedia.org/wiki/Pi)."} curvature-components] [sicmutils.calculus.derivative - derivative D taylor-series] + derivative D D-as-matrix taylor-series] [sicmutils.calculus.form-field form-field? nform-field? oneform-field? diff --git a/src/sicmutils/matrix.cljc b/src/sicmutils/matrix.cljc index 3d7a00a4d..37409a219 100644 --- a/src/sicmutils/matrix.cljc +++ b/src/sicmutils/matrix.cljc @@ -690,12 +690,11 @@ (assoc m i v)) (defn submatrix - "Returns the submatrix of `m` generated by taking + "Returns the submatrix of the matrix (or matrix-like structure) `s` generated by + taking - rows from `lowrow` -> `hirow`, - - columns from `lowcol` -> `hicol` - - TODO test that this can handle structures too." + - columns from `lowcol` -> `hicol`" [x lowrow hirow lowcol hicol] (let [m (if (s/structure? x) (square-structure-> x (fn [m _] m)) @@ -781,7 +780,7 @@ 0 m 1 (->Matrix 1 1 [[(g/invert (core-get-in m [0 0]))]]) (let [C (cofactors m) - Δ (apply g/+ (map g/* (nth m 0) (nth C 0)))] + Δ (ua/generic-sum (map g/* (nth m 0) (nth C 0)))] (fmap #(g/divide % Δ) (transpose C)))))) diff --git a/src/sicmutils/modint.cljc b/src/sicmutils/modint.cljc index 47c35b776..7ae678a53 100644 --- a/src/sicmutils/modint.cljc +++ b/src/sicmutils/modint.cljc @@ -75,12 +75,17 @@ (.-m ^ModInt x)) (defn- mod:= [this that] - (if (modint? that) - (and (= (modulus this) - (modulus that)) - (v/= (residue this) - (residue that))) - (v/= (residue this) that))) + (cond (modint? that) + (and (= (modulus this) + (modulus that)) + (v/= (residue this) + (residue that))) + + (v/number? that) + (v/= (residue this) + (g/modulo that (modulus this))) + + :else false)) (defn make "Returns an instance of [[ModInt]] that represents integer `i` with integral @@ -168,6 +173,9 @@ (defn- div [a b] (mul a (invert b))) +(defmethod v/= [::v/number ::modint] [l r] (mod:= r l)) +(defmethod v/= [::modint ::v/number] [l r] (mod:= l r)) + (defmethod g/integer-part [::modint] [a] (residue a)) (defmethod g/fractional-part [::modint] [a] 0) (defmethod g/floor [::modint] [a] a) diff --git a/test/sicmutils/modint_test.cljc b/test/sicmutils/modint_test.cljc index 47143921b..27ff4a846 100644 --- a/test/sicmutils/modint_test.cljc +++ b/test/sicmutils/modint_test.cljc @@ -44,6 +44,38 @@ (is (= '(modint 1 2) (v/freeze (m/make 1 2))))) + (checking "v/= can handle non-modint instances" 100 + [m (sg/modint) + n gen/small-integer] + (let [incremented (g/+ (m/residue m) + (g/* n (m/modulus m)))] + (is (v/= (m/residue m) m) + "v/= can take numbers on the left") + + (is (= m (m/residue m)) + "= can handle numbers on the right") + + (is (v/= m (m/residue m)) + "v/= can too") + + (is (= m incremented) + "= returns true of the non-ModInt on the right is incremented + by a multiple of the modulus") + + (is (v/= m incremented) + "v/= can do this too...") + + (is (v/= incremented m) + "v/= can handle the number on the left."))) + + (testing "equality unit tests" + (is (v/= 3 (m/make 3 10)) + "v/= compares numbers with ModInt instances by modding them first") + + (is (v/= 13 (m/make 3 10)) + "If the number is incremented by a multiple of the modulus, v/= returns + true.")) + (let [m3_7 (m/make 3 7) m0_7 (m/make 0 7) m1_7 (m/make 1 7) diff --git a/test/sicmutils/structure_test.cljc b/test/sicmutils/structure_test.cljc index 1bd1f0bf5..9e57b2210 100644 --- a/test/sicmutils/structure_test.cljc +++ b/test/sicmutils/structure_test.cljc @@ -581,7 +581,13 @@ (checking "s/compatible-zero works" 100 [s (sg/structure sg/real)] (is (v/zero? (g/* s (s/compatible-zero s)))) - (is (v/zero? (g/* (s/compatible-zero s) s)))) + (is (v/zero? (g/* (s/compatible-zero s) s))) + + (is (v/zero? (g/* s (s/dual-zero s))) + "dual-zero is an alias for compatible-zero.") + + (is (v/zero? (g/* (s/dual-zero s) s)) + "dual-zero is an alias for compatible-zero.")) (testing "compatible-shape" (let [o (s/compatible-shape (s/up 1 2))] From 87a018c1df2293a04b9b1ef0356898cc0e5ce609 Mon Sep 17 00:00:00 2001 From: Sam Ritchie Date: Wed, 7 Apr 2021 06:43:09 -0600 Subject: [PATCH 3/5] fix vc tests --- .../calculus/vector_calculus_test.cljc | 36 +++++++++---------- 1 file changed, 18 insertions(+), 18 deletions(-) diff --git a/test/sicmutils/calculus/vector_calculus_test.cljc b/test/sicmutils/calculus/vector_calculus_test.cljc index 3a6524a1c..e745f7813 100644 --- a/test/sicmutils/calculus/vector_calculus_test.cljc +++ b/test/sicmutils/calculus/vector_calculus_test.cljc @@ -24,7 +24,7 @@ [sicmutils.calculus.coordinate :refer [let-coordinates] #?@(:cljs [:include-macros true])] [sicmutils.calculus.covariant :as cov] - [sicmutils.calculus.derivative :as d :refer [D]] + [sicmutils.calculus.derivative :refer [D]] [sicmutils.calculus.manifold :as m] [sicmutils.calculus.vector-calculus :as vc] [sicmutils.abstract.function :as af] @@ -51,13 +51,13 @@ (up 1 0 0) (up 0 (cos y) 0) (up 0 0 (* -1 (sin z)))) - (simplify ((d/Grad f) xyz)))) + (simplify ((vc/Grad f) xyz)))) (is (= '(up 0 (* -1 (sin y)) (* -1 (cos z))) - (simplify ((d/Lap f) xyz)))) + (simplify ((vc/Lap f) xyz)))) (is (= '(+ (cos y) (* -1 (sin z)) 1) - (simplify ((d/Div f) (s/up 'x 'y 'z))))))) + (simplify ((vc/Div f) (s/up 'x 'y 'z))))))) (deftest non-fdg-vector-operator-tests (testing "symbolic representations of Div, Curl, Grad, Lap are correct" @@ -68,13 +68,13 @@ (((partial 1) F) (up x y z)) (((partial 2) F) (up x y z))) (simplify - ((d/Grad F) (s/up 'x 'y 'z))))) + ((vc/Grad F) (s/up 'x 'y 'z))))) (is (= '(+ (((partial 0) A↑0) (up x y z)) (((partial 1) A↑1) (up x y z)) (((partial 2) A↑2) (up x y z))) (simplify - ((d/Div A) (s/up 'x 'y 'z))))) + ((vc/Div A) (s/up 'x 'y 'z))))) (is (= '(up (+ (((partial 1) A↑2) (up x y z)) (* -1 (((partial 2) A↑1) (up x y z)))) @@ -83,13 +83,13 @@ (+ (((partial 0) A↑1) (up x y z)) (* -1 (((partial 1) A↑0) (up x y z))))) (simplify - ((d/Curl A) (s/up 'x 'y 'z))))) + ((vc/Curl A) (s/up 'x 'y 'z))))) (is (= '(+ (((expt (partial 0) 2) F) (up x y z)) (((expt (partial 1) 2) F) (up x y z)) (((expt (partial 2) 2) F) (up x y z))) (simplify - ((d/Lap F) (s/up 'x 'y 'z))))))) + ((vc/Lap F) (s/up 'x 'y 'z))))))) (testing "Div, Curl, Grad, Lap identities" (let [F (af/literal-function 'F '(-> (UP Real Real Real) Real)) @@ -98,30 +98,30 @@ (UP Real Real Real)))] (is (= '(up 0 0 0) (simplify - ((d/Curl (d/Grad F)) (s/up 'x 'y 'z)))) + ((vc/Curl (vc/Grad F)) (s/up 'x 'y 'z)))) "Curl of the gradient is zero!") (is (= 0 (simplify - ((d/Div (d/Curl A)) (s/up 'x 'y 'z)))) + ((vc/Div (vc/Curl A)) (s/up 'x 'y 'z)))) "divergence of curl is 0.") (is (= 0 (simplify - ((- (d/Div (d/Grad F)) - (d/Lap F)) + ((- (vc/Div (vc/Grad F)) + (vc/Lap F)) (s/up 'x 'y 'z)))) "The Laplacian of a scalar field is the div of its gradient.") (is (= '(up 0 0 0) (simplify - ((- (d/Curl (d/Curl A)) - (- (d/Grad (d/Div A)) (d/Lap A))) + ((- (vc/Curl (vc/Curl A)) + (- (vc/Grad (vc/Div A)) (vc/Lap A))) (s/up 'x 'y 'z))))) (is (= 0 (simplify - ((- (d/Div (* F (d/Grad G))) - (+ (* F (d/Lap G)) - (g/dot-product (d/Grad F) - (d/Grad G)))) + ((- (vc/Div (* F (vc/Grad G))) + (+ (* F (vc/Lap G)) + (g/dot-product (vc/Grad F) + (vc/Grad G)))) (s/up 'x 'y 'z)))))))) (deftest vector-operator-tests From bc3f54e5c8c061104947d696ab5170d404021a58 Mon Sep 17 00:00:00 2001 From: Sam Ritchie Date: Wed, 7 Apr 2021 06:45:40 -0600 Subject: [PATCH 4/5] halt-at --- src/sicmutils/util/aggregate.cljc | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/src/sicmutils/util/aggregate.cljc b/src/sicmutils/util/aggregate.cljc index bfe7e4366..c2b27a980 100644 --- a/src/sicmutils/util/aggregate.cljc +++ b/src/sicmutils/util/aggregate.cljc @@ -78,7 +78,11 @@ (defn halt-at "Returns a transducer that ends transduction when `pred` (applied to the - aggregation in progress) returns true for an aggregation step." + aggregation in progress) returns true for an aggregation step. + + NOTE: This transducer should come first in a chain of transducers; it only + inspects the aggregate, never the value, so putting it first will prevent + unnecessary transformations of values if the aggregate signals completion." [pred] (fn [rf] (fn From 372601799c30959f076c6590c7f76e8d00f9dccd Mon Sep 17 00:00:00 2001 From: Sam Ritchie Date: Wed, 7 Apr 2021 06:52:59 -0600 Subject: [PATCH 5/5] fix vc tests --- src/sicmutils/calculus/vector_calculus.cljc | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/src/sicmutils/calculus/vector_calculus.cljc b/src/sicmutils/calculus/vector_calculus.cljc index 534001441..4c10c8308 100644 --- a/src/sicmutils/calculus/vector_calculus.cljc +++ b/src/sicmutils/calculus/vector_calculus.cljc @@ -25,6 +25,7 @@ metric and basis." (:refer-clojure :exclude [+ - * /]) (:require [sicmutils.calculus.basis :as b] + [sicmutils.calculus.derivative :as d] [sicmutils.calculus.covariant :as cov] [sicmutils.calculus.form-field :as ff] [sicmutils.calculus.hodge-star :as hs] @@ -90,13 +91,13 @@ `f` must be a function from $\\mathbb{R}^3 \\to \\mathbb{R}^3$."} Curl (-> (fn [f-triple] - (let [[Dx Dy Dz] (map partial [0 1 2]) + (let [[Dx Dy Dz] (map d/partial [0 1 2]) fx (f/get f-triple 0) fy (f/get f-triple 1) fz (f/get f-triple 2)] - (s/up (g/- (Dy fz) (Dz fy)) - (g/- (Dz fx) (Dx fz)) - (g/- (Dx fy) (Dy fx))))) + (s/up (- (Dy fz) (Dz fy)) + (- (Dz fx) (Dx fz)) + (- (Dx fy) (Dy fx))))) (o/make-operator 'Curl))) (defn curl @@ -114,7 +115,7 @@ Laplacian](https://en.wikipedia.org/wiki/Laplace_operator#Vector_Laplacian) of `f` at its input point."} Lap - (-> (f/compose g/trace (g/* Grad Grad)) + (-> (f/compose g/trace (* Grad Grad)) (o/make-operator 'Lap))) (defn Laplacian [metric orthonormal-basis]