Berkeley COMPSCI 282 - Basic Domains of Interest used in Computer Algebra Systems

Unformatted text preview:

Basic Domains of Interest used in Computer Algebra SystemsWe can compute with any finitely representable objects, at least in principleThe Usual OperationsMore OperationsYet More OperationsSlide 6Slide 7Integer representations, operationsUnfortunately computers don’t do these operations directlyIs it hard to do arbitrary integer (bignum) arithmetic?Who cares about integer arithmetic?Some ideas just for representing integersYet more ideasTo be continued..Richard Fateman CS 282 Lecture 2 1Basic Domains of Interest used in Computer Algebra SystemsLecture 2Richard Fateman CS 282 Lecture 2 2We can compute with any finitely representable objects, at least in principle•Objects from any algebraic system, and even some ad-hoc mixtures•With any algorithms –All steps specified precisely–Terminating•Some processes are not-necessarily terminating. E.g. L’hôpital’s rule … use termination heuristics: time/space limits, losing some credibility for results •But we tend to concentrate on domains that occur in applied math, physical sciences, etc.Richard Fateman CS 282 Lecture 2 3The Usual Operations• Integer and Rational:–Ring and Field operations +- * exact quotient, remainder•GCD, factoring of integers•Approximation via rootfinding•Polynomial operations–Ring, Field, GCD, factor–Truncated power series–Solution of polynomial systems•Matrix operations (add determinant, resultant, eigenvalues, etc.)Richard Fateman CS 282 Lecture 2 4More Operations•Sorting (e.g. of monomials)•Union (collections)•Tests for zero•Extraction of parts (polynomial degree, constant coefficient, leading coefficient)•Conversion to different forms (“expand”, express algebraic function in a minimal extension, “simplify”)Richard Fateman CS 282 Lecture 2 5Yet More OperationsDifferentiateIntegrateLimitProveFind region in which (in)equalities holdConfirm (as: steps in a proof)Expand in seriesRichard Fateman CS 282 Lecture 2 6Yet More OperationsPlotXYZ-2.0 < X < 2.0-1.5 < Y < 2.5-0.43 < Z < 0.43XYZ-2.00-1.001.002.00-1.000.001.002.00-0.250.000.25plot3d(exp(-x^2-y^2)*x,x,-2,2,y,-1.5,2.5)Richard Fateman CS 282 Lecture 2 7Yet More OperationsTypesetting(d13) factor������determinant�����1 x x21 y y21 z z2����������� = (y - x) (z - x) (z - y)Richard Fateman CS 282 Lecture 2 8Integer representations, operations•The ring operations +*-•Euclidean Domain: quotient & remainder, GCD•UFD : factorizationRichard Fateman CS 282 Lecture 2 9Unfortunately computers don’t do these operations directly Addition modulo 231-1 is rarely what we need.How do we do arbitrary precision integer arithmetic? (If we could do this, we could build the rationals, and via intervals or some other construction, we could make reals)Richard Fateman CS 282 Lecture 2 10Is it hard to do arbitrary integer (bignum) arithmetic?•In spite of your knowledge of this subject, there are subtleties, especially in long division!•You must choose fast algorithms (moderate size) or asymptotically optimal algorithms (large size): what’s your target?Richard Fateman CS 282 Lecture 2 11Who cares about integer arithmetic?•You need fast long arithmetic to compute billions of digits of  e.g. DH Bailey's home page•You need fast moderate-length arithmetic to play integer-factoring games.•Arguably, there are sensitive geometric predicates that require very high precision (floats).•You need all lengths to build a computer algebra system: without it your system tells lies.•Every Common Lisp has bignums built in.Richard Fateman CS 282 Lecture 2 12Some ideas just for representing integersIntegers are sequences of characters, 0..9.Integers are sequences of words modulo 109 which is the largest power of 10 less than 231. Integers are sequences of hexadecimal digits.Integers are sequences of 32-bit words.Integers are sequences of 64-bit double-floats (with 8 bits wasted).Sequences are linked listsSequences are vectorsSequences are stored in sequential disk locationsRichard Fateman CS 282 Lecture 2 13Yet more ideasIntegers are sequences of 64-bit double-floats (with 8 bits used to position the bits) e.g. 2-300+2300 takes 2 wordsIntegers are stored in redundant form a+b+…Integer are stored modulo set of different primesIntegers are stored in p-adic form as a sequence of x mod p, x mod p2, …Richard Fateman CS 282 Lecture 2 14To be continued..•Integers and


View Full Document
Download Basic Domains of Interest used in Computer Algebra Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Basic Domains of Interest used in Computer Algebra Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Basic Domains of Interest used in Computer Algebra Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?