Source file src/pkg/math/big/rat.go
1 // Copyright 2010 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // This file implements multi-precision rational numbers. 6 7 package big 8 9 import ( 10 "encoding/binary" 11 "errors" 12 "fmt" 13 "strings" 14 ) 15 16 // A Rat represents a quotient a/b of arbitrary precision. 17 // The zero value for a Rat represents the value 0. 18 type Rat struct { 19 a Int 20 b nat // len(b) == 0 acts like b == 1 21 } 22 23 // NewRat creates a new Rat with numerator a and denominator b. 24 func NewRat(a, b int64) *Rat { 25 return new(Rat).SetFrac64(a, b) 26 } 27 28 // SetFrac sets z to a/b and returns z. 29 func (z *Rat) SetFrac(a, b *Int) *Rat { 30 z.a.neg = a.neg != b.neg 31 babs := b.abs 32 if len(babs) == 0 { 33 panic("division by zero") 34 } 35 if &z.a == b || alias(z.a.abs, babs) { 36 babs = nat(nil).set(babs) // make a copy 37 } 38 z.a.abs = z.a.abs.set(a.abs) 39 z.b = z.b.set(babs) 40 return z.norm() 41 } 42 43 // SetFrac64 sets z to a/b and returns z. 44 func (z *Rat) SetFrac64(a, b int64) *Rat { 45 z.a.SetInt64(a) 46 if b == 0 { 47 panic("division by zero") 48 } 49 if b < 0 { 50 b = -b 51 z.a.neg = !z.a.neg 52 } 53 z.b = z.b.setUint64(uint64(b)) 54 return z.norm() 55 } 56 57 // SetInt sets z to x (by making a copy of x) and returns z. 58 func (z *Rat) SetInt(x *Int) *Rat { 59 z.a.Set(x) 60 z.b = z.b.make(0) 61 return z 62 } 63 64 // SetInt64 sets z to x and returns z. 65 func (z *Rat) SetInt64(x int64) *Rat { 66 z.a.SetInt64(x) 67 z.b = z.b.make(0) 68 return z 69 } 70 71 // Set sets z to x (by making a copy of x) and returns z. 72 func (z *Rat) Set(x *Rat) *Rat { 73 if z != x { 74 z.a.Set(&x.a) 75 z.b = z.b.set(x.b) 76 } 77 return z 78 } 79 80 // Abs sets z to |x| (the absolute value of x) and returns z. 81 func (z *Rat) Abs(x *Rat) *Rat { 82 z.Set(x) 83 z.a.neg = false 84 return z 85 } 86 87 // Neg sets z to -x and returns z. 88 func (z *Rat) Neg(x *Rat) *Rat { 89 z.Set(x) 90 z.a.neg = len(z.a.abs) > 0 && !z.a.neg // 0 has no sign 91 return z 92 } 93 94 // Inv sets z to 1/x and returns z. 95 func (z *Rat) Inv(x *Rat) *Rat { 96 if len(x.a.abs) == 0 { 97 panic("division by zero") 98 } 99 z.Set(x) 100 a := z.b 101 if len(a) == 0 { 102 a = a.setWord(1) // materialize numerator 103 } 104 b := z.a.abs 105 if b.cmp(natOne) == 0 { 106 b = b.make(0) // normalize denominator 107 } 108 z.a.abs, z.b = a, b // sign doesn't change 109 return z 110 } 111 112 // Sign returns: 113 // 114 // -1 if x < 0 115 // 0 if x == 0 116 // +1 if x > 0 117 // 118 func (x *Rat) Sign() int { 119 return x.a.Sign() 120 } 121 122 // IsInt returns true if the denominator of x is 1. 123 func (x *Rat) IsInt() bool { 124 return len(x.b) == 0 || x.b.cmp(natOne) == 0 125 } 126 127 // Num returns the numerator of x; it may be <= 0. 128 // The result is a reference to x's numerator; it 129 // may change if a new value is assigned to x. 130 func (x *Rat) Num() *Int { 131 return &x.a 132 } 133 134 // Denom returns the denominator of x; it is always > 0. 135 // The result is a reference to x's denominator; it 136 // may change if a new value is assigned to x. 137 func (x *Rat) Denom() *Int { 138 if len(x.b) == 0 { 139 return &Int{abs: nat{1}} 140 } 141 return &Int{abs: x.b} 142 } 143 144 func gcd(x, y nat) nat { 145 // Euclidean algorithm. 146 var a, b nat 147 a = a.set(x) 148 b = b.set(y) 149 for len(b) != 0 { 150 var q, r nat 151 _, r = q.div(r, a, b) 152 a = b 153 b = r 154 } 155 return a 156 } 157 158 func (z *Rat) norm() *Rat { 159 switch { 160 case len(z.a.abs) == 0: 161 // z == 0 - normalize sign and denominator 162 z.a.neg = false 163 z.b = z.b.make(0) 164 case len(z.b) == 0: 165 // z is normalized int - nothing to do 166 case z.b.cmp(natOne) == 0: 167 // z is int - normalize denominator 168 z.b = z.b.make(0) 169 default: 170 if f := gcd(z.a.abs, z.b); f.cmp(natOne) != 0 { 171 z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f) 172 z.b, _ = z.b.div(nil, z.b, f) 173 } 174 } 175 return z 176 } 177 178 // mulDenom sets z to the denominator product x*y (by taking into 179 // account that 0 values for x or y must be interpreted as 1) and 180 // returns z. 181 func mulDenom(z, x, y nat) nat { 182 switch { 183 case len(x) == 0: 184 return z.set(y) 185 case len(y) == 0: 186 return z.set(x) 187 } 188 return z.mul(x, y) 189 } 190 191 // scaleDenom computes x*f. 192 // If f == 0 (zero value of denominator), the result is (a copy of) x. 193 func scaleDenom(x *Int, f nat) *Int { 194 var z Int 195 if len(f) == 0 { 196 return z.Set(x) 197 } 198 z.abs = z.abs.mul(x.abs, f) 199 z.neg = x.neg 200 return &z 201 } 202 203 // Cmp compares x and y and returns: 204 // 205 // -1 if x < y 206 // 0 if x == y 207 // +1 if x > y 208 // 209 func (x *Rat) Cmp(y *Rat) int { 210 return scaleDenom(&x.a, y.b).Cmp(scaleDenom(&y.a, x.b)) 211 } 212 213 // Add sets z to the sum x+y and returns z. 214 func (z *Rat) Add(x, y *Rat) *Rat { 215 a1 := scaleDenom(&x.a, y.b) 216 a2 := scaleDenom(&y.a, x.b) 217 z.a.Add(a1, a2) 218 z.b = mulDenom(z.b, x.b, y.b) 219 return z.norm() 220 } 221 222 // Sub sets z to the difference x-y and returns z. 223 func (z *Rat) Sub(x, y *Rat) *Rat { 224 a1 := scaleDenom(&x.a, y.b) 225 a2 := scaleDenom(&y.a, x.b) 226 z.a.Sub(a1, a2) 227 z.b = mulDenom(z.b, x.b, y.b) 228 return z.norm() 229 } 230 231 // Mul sets z to the product x*y and returns z. 232 func (z *Rat) Mul(x, y *Rat) *Rat { 233 z.a.Mul(&x.a, &y.a) 234 z.b = mulDenom(z.b, x.b, y.b) 235 return z.norm() 236 } 237 238 // Quo sets z to the quotient x/y and returns z. 239 // If y == 0, a division-by-zero run-time panic occurs. 240 func (z *Rat) Quo(x, y *Rat) *Rat { 241 if len(y.a.abs) == 0 { 242 panic("division by zero") 243 } 244 a := scaleDenom(&x.a, y.b) 245 b := scaleDenom(&y.a, x.b) 246 z.a.abs = a.abs 247 z.b = b.abs 248 z.a.neg = a.neg != b.neg 249 return z.norm() 250 } 251 252 func ratTok(ch rune) bool { 253 return strings.IndexRune("+-/0123456789.eE", ch) >= 0 254 } 255 256 // Scan is a support routine for fmt.Scanner. It accepts the formats 257 // 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent. 258 func (z *Rat) Scan(s fmt.ScanState, ch rune) error { 259 tok, err := s.Token(true, ratTok) 260 if err != nil { 261 return err 262 } 263 if strings.IndexRune("efgEFGv", ch) < 0 { 264 return errors.New("Rat.Scan: invalid verb") 265 } 266 if _, ok := z.SetString(string(tok)); !ok { 267 return errors.New("Rat.Scan: invalid syntax") 268 } 269 return nil 270 } 271 272 // SetString sets z to the value of s and returns z and a boolean indicating 273 // success. s can be given as a fraction "a/b" or as a floating-point number 274 // optionally followed by an exponent. If the operation failed, the value of 275 // z is undefined but the returned value is nil. 276 func (z *Rat) SetString(s string) (*Rat, bool) { 277 if len(s) == 0 { 278 return nil, false 279 } 280 281 // check for a quotient 282 sep := strings.Index(s, "/") 283 if sep >= 0 { 284 if _, ok := z.a.SetString(s[0:sep], 10); !ok { 285 return nil, false 286 } 287 s = s[sep+1:] 288 var err error 289 if z.b, _, err = z.b.scan(strings.NewReader(s), 10); err != nil { 290 return nil, false 291 } 292 return z.norm(), true 293 } 294 295 // check for a decimal point 296 sep = strings.Index(s, ".") 297 // check for an exponent 298 e := strings.IndexAny(s, "eE") 299 var exp Int 300 if e >= 0 { 301 if e < sep { 302 // The E must come after the decimal point. 303 return nil, false 304 } 305 if _, ok := exp.SetString(s[e+1:], 10); !ok { 306 return nil, false 307 } 308 s = s[0:e] 309 } 310 if sep >= 0 { 311 s = s[0:sep] + s[sep+1:] 312 exp.Sub(&exp, NewInt(int64(len(s)-sep))) 313 } 314 315 if _, ok := z.a.SetString(s, 10); !ok { 316 return nil, false 317 } 318 powTen := nat(nil).expNN(natTen, exp.abs, nil) 319 if exp.neg { 320 z.b = powTen 321 z.norm() 322 } else { 323 z.a.abs = z.a.abs.mul(z.a.abs, powTen) 324 z.b = z.b.make(0) 325 } 326 327 return z, true 328 } 329 330 // String returns a string representation of z in the form "a/b" (even if b == 1). 331 func (x *Rat) String() string { 332 s := "/1" 333 if len(x.b) != 0 { 334 s = "/" + x.b.decimalString() 335 } 336 return x.a.String() + s 337 } 338 339 // RatString returns a string representation of z in the form "a/b" if b != 1, 340 // and in the form "a" if b == 1. 341 func (x *Rat) RatString() string { 342 if x.IsInt() { 343 return x.a.String() 344 } 345 return x.String() 346 } 347 348 // FloatString returns a string representation of z in decimal form with prec 349 // digits of precision after the decimal point and the last digit rounded. 350 func (x *Rat) FloatString(prec int) string { 351 if x.IsInt() { 352 s := x.a.String() 353 if prec > 0 { 354 s += "." + strings.Repeat("0", prec) 355 } 356 return s 357 } 358 // x.b != 0 359 360 q, r := nat(nil).div(nat(nil), x.a.abs, x.b) 361 362 p := natOne 363 if prec > 0 { 364 p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil) 365 } 366 367 r = r.mul(r, p) 368 r, r2 := r.div(nat(nil), r, x.b) 369 370 // see if we need to round up 371 r2 = r2.add(r2, r2) 372 if x.b.cmp(r2) <= 0 { 373 r = r.add(r, natOne) 374 if r.cmp(p) >= 0 { 375 q = nat(nil).add(q, natOne) 376 r = nat(nil).sub(r, p) 377 } 378 } 379 380 s := q.decimalString() 381 if x.a.neg { 382 s = "-" + s 383 } 384 385 if prec > 0 { 386 rs := r.decimalString() 387 leadingZeros := prec - len(rs) 388 s += "." + strings.Repeat("0", leadingZeros) + rs 389 } 390 391 return s 392 } 393 394 // Gob codec version. Permits backward-compatible changes to the encoding. 395 const ratGobVersion byte = 1 396 397 // GobEncode implements the gob.GobEncoder interface. 398 func (x *Rat) GobEncode() ([]byte, error) { 399 buf := make([]byte, 1+4+(len(x.a.abs)+len(x.b))*_S) // extra bytes for version and sign bit (1), and numerator length (4) 400 i := x.b.bytes(buf) 401 j := x.a.abs.bytes(buf[0:i]) 402 n := i - j 403 if int(uint32(n)) != n { 404 // this should never happen 405 return nil, errors.New("Rat.GobEncode: numerator too large") 406 } 407 binary.BigEndian.PutUint32(buf[j-4:j], uint32(n)) 408 j -= 1 + 4 409 b := ratGobVersion << 1 // make space for sign bit 410 if x.a.neg { 411 b |= 1 412 } 413 buf[j] = b 414 return buf[j:], nil 415 } 416 417 // GobDecode implements the gob.GobDecoder interface. 418 func (z *Rat) GobDecode(buf []byte) error { 419 if len(buf) == 0 { 420 return errors.New("Rat.GobDecode: no data") 421 } 422 b := buf[0] 423 if b>>1 != ratGobVersion { 424 return errors.New(fmt.Sprintf("Rat.GobDecode: encoding version %d not supported", b>>1)) 425 } 426 const j = 1 + 4 427 i := j + binary.BigEndian.Uint32(buf[j-4:j]) 428 z.a.neg = b&1 != 0 429 z.a.abs = z.a.abs.setBytes(buf[j:i]) 430 z.b = z.b.setBytes(buf[i:]) 431 return nil 432 }