Basic Domains of Interest used in Computer Algebra SystemsSome ideas just for representing integersAside: using half the bits in a word is common strategyYet more ideasRedundant (big precision) floatsModular (mod a set of primes q1, q2, …qn)Modular arithmetic is really fast…What’s a p-adic integer?p-adic ordering is odd.How to multiply p-adicallyHow to multiply p-adically approximatelyWhat other p-adic numbers are there??What does this buy us??Multiplication, usual representationInteger DivisionGCDReminder… A Ring R is EuclideanShows the tendency to obfuscate…Where next?Interlude, regarding your homework (the last problem)Trivial parts..Harder parts..Reminder: The Usual CoefficientsPreview: ExtensionsBeware of notationAside 2.1: canonical forms vs. mathematical equivalenceAside 2.2: Simplification is almost everything in this business..Aside 2.3: Computer representation and canonical formsBack to extensionsMore on extensionsOther extensionsThere’s more… Other kinds of symbolic computationRichard Fateman CS 282 Lecture 2b 1Basic Domains of Interest used in Computer Algebra SystemsLecture 2bRichard Fateman CS 282 Lecture 2 2Some 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 3Aside: using half the bits in a word is common strategyIntegers are sequences of 32-bit words, but only the bottom 16 are used: There is some lack of uniformity in architectural support for unsigned 32X32 bit multiply. But 16X16  32 bit is supported, so programs can be portable.Downside: if you multiply two n-bigit numbers in time n2 then with half-length bigits you need twice as many of them and so you take time (2n)2, or 4 times slower and 2X the space.Richard Fateman CS 282 Lecture 2 4Yet more ideasIntegers 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 5Redundant (big precision) floats•Sequences (xn + ….+x2 +x1)•Non-overlapping means each the lsb of xk is more significant than the msb of xk-1. May be big gaps.• Not unique. •(binary values..) 1100 + -10.1 = 1001 + 0.1 = 1000+1+0.1•Easy to tell the sign. Look at the leading term.•Adding must restore non-overlapping property.•Important use by Jonathan Shewchuk (UCB) in geometric predicate calculations.Richard Fateman CS 282 Lecture 2 6Modular (mod a set of primes q1, q2, …qn)•images unique only within multiple of product of the primes Q = q1 ¢ q2 ¢ …¢ qn.•CRA (Chinese Remainder Algorithm) provides a way of going from modular to conventional positional notation, but takes O(n2) in practice.•This and its generalizations heavily used in computer algebra systems and this course.Richard Fateman CS 282 Lecture 2 7Modular arithmetic is really fast…all the arithmetic can be done without carry, in parallel.Not usually used because(a)You can’t tell for sure if a number is +, -, 0 or Q or 3 Q….(b) Parallelism is almost always irrelevant (c) If you must see the answer converted to decimal, the conversion is O(n2)(d)Conversion to decimal may be very common if your application is a bignum calculator.Richard Fateman CS 282 Lecture 2 8What’s a p-adic integer?For the moment assume p is a prime number. Consider representing an integer  = a0+a1.p+a2¢ p2 + … where ai are chosen from integers in the range 0 · ai < p For any finite positive integer , either all the ak are zero in which case  = 0 and ||||p is 0, or some initial set of the ai are zero. Let ar+1 be the first non-zero term. ||||p = p-r. This replaces the absolute-value valuation | | where we consider that x and y are close if x=y mod pk for many values of k=0,1,2,….Richard Fateman CS 282 Lecture 2 9 p-adic ordering is odd.14 3-adically is 2*30+1*31+1*32= 2 + 3 + 9 = 14Which is very close to 5, 3-adically because 5 is 2*30+1*31, and they are the same modulo 30 and 31. ||15-4||3 = 3-1What about negative numbers? pk-1 is possible, but consider pk-1 = (p-1)¢(pk-1+pk-2…+p+1)= (p-1)*1+(p-1)*p+(p-1)*p2+… so -1 3-adically is 2*30+2*31+…. Infinite number of terms (2,2,2,2,2,….)Richard Fateman CS 282 Lecture 2 10How to multiply p-adically(a,b,c)(d,e,f) Compute a*d , a*e, a*f; add columns b*d, b*e; b*f c*d, c*e, c*f Add modulo p, p2, p3 … with a carry.Richard Fateman CS 282 Lecture 2 11How to multiply p-adically approximately(a,b,c …)(d,e,f …) Compute a*d , a*e, a*f; add columns b*d, b*e; b*f c*d, c*e, c*f Add modulo p, p2, p3 … with a carry. Dropping off extra terms is like 3.14159 vs 3.14, but with respect to p-adic distances. Ignore theseRichard Fateman CS 282 Lecture 2 12What other p-adic numbers are there??-1/2 3-adically .. is 1*30+1*31+1*32= (1,1,1,1,1…). Proof:Multiply by 2, which is (2,0,0,0,….) to get (2,2,2,2…) which is -1What about p 7 ?(a0+3*a1+…)2-7=0 (mod 3i+1)Mod 30, a02-7=0 so a0 is 1 or –1. Let’s choose 1.Next solve(1+3*a1+…)2-7=0 (mod 31)= 1+2*3*a1 –7 =0 so a1=1Eventually, p7 = (1,1,1,2,…)Richard Fateman CS 282 Lecture 2 13What does this buy us??Not a great deal for integers, but…We’ll use p-adic representation where p is not a number, but an indeterminate (say x), or a polynomial (x^2-3). Or a polynomial in several variables (x+y+1). If we compute a gcd of 2 polynomials p-adically approximately to high enough degree, we will know the exact GCD. If we can do this computation faster than other means, we have a winner. (This is the case.)Richard Fateman CS 282 Lecture 2 14Multiplication, usual representationExtremely well studied. The usual method takes O(n2), Karatsuba style O(n1.585) or FFT style O(n log n). These will be studied in the context of multiplying polynomials.Note that 345 can be mapped to p(x)=3x2+4x+5 where p(10) is 345.Except for the “carry”, the operation is the same.Richard Fateman CS 282 Lecture 2 15Integer Division•This is too tedious to present in a lecture.•Techniques for guessing the next big digit (bigit) of a