Source file src/math/big/ratconv.go
1 // Copyright 2015 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 rat-to-string conversion functions. 6 7 package big 8 9 import ( 10 "errors" 11 "fmt" 12 "io" 13 "strconv" 14 "strings" 15 ) 16 17 func ratTok(ch rune) bool { 18 return strings.ContainsRune("+-/0123456789.eE", ch) 19 } 20 21 var ratZero Rat 22 var _ fmt.Scanner = &ratZero // *Rat must implement fmt.Scanner 23 24 // Scan is a support routine for fmt.Scanner. It accepts the formats 25 // 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent. 26 func (z *Rat) Scan(s fmt.ScanState, ch rune) error { 27 tok, err := s.Token(true, ratTok) 28 if err != nil { 29 return err 30 } 31 if !strings.ContainsRune("efgEFGv", ch) { 32 return errors.New("Rat.Scan: invalid verb") 33 } 34 if _, ok := z.SetString(string(tok)); !ok { 35 return errors.New("Rat.Scan: invalid syntax") 36 } 37 return nil 38 } 39 40 // SetString sets z to the value of s and returns z and a boolean indicating 41 // success. s can be given as a (possibly signed) fraction "a/b", or as a 42 // floating-point number optionally followed by an exponent. 43 // If a fraction is provided, both the dividend and the divisor may be a 44 // decimal integer or independently use a prefix of “0b”, “0” or “0o”, 45 // or “0x” (or their upper-case variants) to denote a binary, octal, or 46 // hexadecimal integer, respectively. The divisor may not be signed. 47 // If a floating-point number is provided, it may be in decimal form or 48 // use any of the same prefixes as above but for “0” to denote a non-decimal 49 // mantissa. A leading “0” is considered a decimal leading 0; it does not 50 // indicate octal representation in this case. 51 // An optional base-10 “e” or base-2 “p” (or their upper-case variants) 52 // exponent may be provided as well, except for hexadecimal floats which 53 // only accept an (optional) “p” exponent (because an “e” or “E” cannot 54 // be distinguished from a mantissa digit). If the exponent's absolute value 55 // is too large, the operation may fail. 56 // The entire string, not just a prefix, must be valid for success. If the 57 // operation failed, the value of z is undefined but the returned value is nil. 58 func (z *Rat) SetString(s string) (*Rat, bool) { 59 if len(s) == 0 { 60 return nil, false 61 } 62 // len(s) > 0 63 64 // parse fraction a/b, if any 65 if sep := strings.Index(s, "/"); sep >= 0 { 66 if _, ok := z.a.SetString(s[:sep], 0); !ok { 67 return nil, false 68 } 69 r := strings.NewReader(s[sep+1:]) 70 var err error 71 if z.b.abs, _, _, err = z.b.abs.scan(r, 0, false); err != nil { 72 return nil, false 73 } 74 // entire string must have been consumed 75 if _, err = r.ReadByte(); err != io.EOF { 76 return nil, false 77 } 78 if len(z.b.abs) == 0 { 79 return nil, false 80 } 81 return z.norm(), true 82 } 83 84 // parse floating-point number 85 r := strings.NewReader(s) 86 87 // sign 88 neg, err := scanSign(r) 89 if err != nil { 90 return nil, false 91 } 92 93 // mantissa 94 var base int 95 var fcount int // fractional digit count; valid if <= 0 96 z.a.abs, base, fcount, err = z.a.abs.scan(r, 0, true) 97 if err != nil { 98 return nil, false 99 } 100 101 // exponent 102 var exp int64 103 var ebase int 104 exp, ebase, err = scanExponent(r, true, true) 105 if err != nil { 106 return nil, false 107 } 108 109 // there should be no unread characters left 110 if _, err = r.ReadByte(); err != io.EOF { 111 return nil, false 112 } 113 114 // special-case 0 (see also issue #16176) 115 if len(z.a.abs) == 0 { 116 return z.norm(), true 117 } 118 // len(z.a.abs) > 0 119 120 // The mantissa may have a radix point (fcount <= 0) and there 121 // may be a nonzero exponent exp. The radix point amounts to a 122 // division by base**(-fcount), which equals a multiplication by 123 // base**fcount. An exponent means multiplication by ebase**exp. 124 // Multiplications are commutative, so we can apply them in any 125 // order. We only have powers of 2 and 10, and we split powers 126 // of 10 into the product of the same powers of 2 and 5. This 127 // may reduce the size of shift/multiplication factors or 128 // divisors required to create the final fraction, depending 129 // on the actual floating-point value. 130 131 // determine binary or decimal exponent contribution of radix point 132 var exp2, exp5 int64 133 if fcount < 0 { 134 // The mantissa has a radix point ddd.dddd; and 135 // -fcount is the number of digits to the right 136 // of '.'. Adjust relevant exponent accordingly. 137 d := int64(fcount) 138 switch base { 139 case 10: 140 exp5 = d 141 fallthrough // 10**e == 5**e * 2**e 142 case 2: 143 exp2 = d 144 case 8: 145 exp2 = d * 3 // octal digits are 3 bits each 146 case 16: 147 exp2 = d * 4 // hexadecimal digits are 4 bits each 148 default: 149 panic("unexpected mantissa base") 150 } 151 // fcount consumed - not needed anymore 152 } 153 154 // take actual exponent into account 155 switch ebase { 156 case 10: 157 exp5 += exp 158 fallthrough // see fallthrough above 159 case 2: 160 exp2 += exp 161 default: 162 panic("unexpected exponent base") 163 } 164 // exp consumed - not needed anymore 165 166 stk := getStack() 167 defer stk.free() 168 169 // apply exp5 contributions 170 // (start with exp5 so the numbers to multiply are smaller) 171 if exp5 != 0 { 172 n := exp5 173 if n < 0 { 174 n = -n 175 if n < 0 { 176 // This can occur if -n overflows. -(-1 << 63) would become 177 // -1 << 63, which is still negative. 178 return nil, false 179 } 180 } 181 if n > 1e6 { 182 return nil, false // avoid excessively large exponents 183 } 184 pow5 := z.b.abs.expNN(stk, natFive, nat(nil).setWord(Word(n)), nil, false) // use underlying array of z.b.abs 185 if exp5 > 0 { 186 z.a.abs = z.a.abs.mul(stk, z.a.abs, pow5) 187 z.b.abs = z.b.abs.setWord(1) 188 } else { 189 z.b.abs = pow5 190 } 191 } else { 192 z.b.abs = z.b.abs.setWord(1) 193 } 194 195 // apply exp2 contributions 196 if exp2 < -1e7 || exp2 > 1e7 { 197 return nil, false // avoid excessively large exponents 198 } 199 if exp2 > 0 { 200 z.a.abs = z.a.abs.shl(z.a.abs, uint(exp2)) 201 } else if exp2 < 0 { 202 z.b.abs = z.b.abs.shl(z.b.abs, uint(-exp2)) 203 } 204 205 z.a.neg = neg && len(z.a.abs) > 0 // 0 has no sign 206 207 return z.norm(), true 208 } 209 210 // scanExponent scans the longest possible prefix of r representing a base 10 211 // (“e”, “E”) or a base 2 (“p”, “P”) exponent, if any. It returns the 212 // exponent, the exponent base (10 or 2), or a read or syntax error, if any. 213 // 214 // If sepOk is set, an underscore character “_” may appear between successive 215 // exponent digits; such underscores do not change the value of the exponent. 216 // Incorrect placement of underscores is reported as an error if there are no 217 // other errors. If sepOk is not set, underscores are not recognized and thus 218 // terminate scanning like any other character that is not a valid digit. 219 // 220 // exponent = ( "e" | "E" | "p" | "P" ) [ sign ] digits . 221 // sign = "+" | "-" . 222 // digits = digit { [ '_' ] digit } . 223 // digit = "0" ... "9" . 224 // 225 // A base 2 exponent is only permitted if base2ok is set. 226 func scanExponent(r io.ByteScanner, base2ok, sepOk bool) (exp int64, base int, err error) { 227 // one char look-ahead 228 ch, err := r.ReadByte() 229 if err != nil { 230 if err == io.EOF { 231 err = nil 232 } 233 return 0, 10, err 234 } 235 236 // exponent char 237 switch ch { 238 case 'e', 'E': 239 base = 10 240 case 'p', 'P': 241 if base2ok { 242 base = 2 243 break // ok 244 } 245 fallthrough // binary exponent not permitted 246 default: 247 r.UnreadByte() // ch does not belong to exponent anymore 248 return 0, 10, nil 249 } 250 251 // sign 252 var digits []byte 253 ch, err = r.ReadByte() 254 if err == nil && (ch == '+' || ch == '-') { 255 if ch == '-' { 256 digits = append(digits, '-') 257 } 258 ch, err = r.ReadByte() 259 } 260 261 // prev encodes the previously seen char: it is one 262 // of '_', '0' (a digit), or '.' (anything else). A 263 // valid separator '_' may only occur after a digit. 264 prev := '.' 265 invalSep := false 266 267 // exponent value 268 hasDigits := false 269 for err == nil { 270 if '0' <= ch && ch <= '9' { 271 digits = append(digits, ch) 272 prev = '0' 273 hasDigits = true 274 } else if ch == '_' && sepOk { 275 if prev != '0' { 276 invalSep = true 277 } 278 prev = '_' 279 } else { 280 r.UnreadByte() // ch does not belong to number anymore 281 break 282 } 283 ch, err = r.ReadByte() 284 } 285 286 if err == io.EOF { 287 err = nil 288 } 289 if err == nil && !hasDigits { 290 err = errNoDigits 291 } 292 if err == nil { 293 exp, err = strconv.ParseInt(string(digits), 10, 64) 294 } 295 // other errors take precedence over invalid separators 296 if err == nil && (invalSep || prev == '_') { 297 err = errInvalSep 298 } 299 300 return 301 } 302 303 // String returns a string representation of x in the form "a/b" (even if b == 1). 304 func (x *Rat) String() string { 305 return string(x.marshal(nil)) 306 } 307 308 // marshal implements [Rat.String] returning a slice of bytes. 309 // It appends the string representation of x in the form "a/b" (even if b == 1) to buf, 310 // and returns the extended buffer. 311 func (x *Rat) marshal(buf []byte) []byte { 312 buf = x.a.Append(buf, 10) 313 buf = append(buf, '/') 314 if len(x.b.abs) != 0 { 315 buf = x.b.Append(buf, 10) 316 } else { 317 buf = append(buf, '1') 318 } 319 return buf 320 } 321 322 // RatString returns a string representation of x in the form "a/b" if b != 1, 323 // and in the form "a" if b == 1. 324 func (x *Rat) RatString() string { 325 if x.IsInt() { 326 return x.a.String() 327 } 328 return x.String() 329 } 330 331 // FloatString returns a string representation of x in decimal form with prec 332 // digits of precision after the radix point. The last digit is rounded to 333 // nearest, with halves rounded away from zero. 334 func (x *Rat) FloatString(prec int) string { 335 var buf []byte 336 337 if x.IsInt() { 338 buf = x.a.Append(buf, 10) 339 if prec > 0 { 340 buf = append(buf, '.') 341 for i := prec; i > 0; i-- { 342 buf = append(buf, '0') 343 } 344 } 345 return string(buf) 346 } 347 // x.b.abs != 0 348 349 stk := getStack() 350 defer stk.free() 351 q, r := nat(nil).div(stk, nat(nil), x.a.abs, x.b.abs) 352 353 p := natOne 354 if prec > 0 { 355 p = nat(nil).expNN(stk, natTen, nat(nil).setUint64(uint64(prec)), nil, false) 356 } 357 358 r = r.mul(stk, r, p) 359 r, r2 := r.div(stk, nat(nil), r, x.b.abs) 360 361 // see if we need to round up 362 r2 = r2.add(r2, r2) 363 if x.b.abs.cmp(r2) <= 0 { 364 r = r.add(r, natOne) 365 if r.cmp(p) >= 0 { 366 q = nat(nil).add(q, natOne) 367 r = nat(nil).sub(r, p) 368 } 369 } 370 371 if x.a.neg { 372 buf = append(buf, '-') 373 } 374 buf = append(buf, q.utoa(10)...) // itoa ignores sign if q == 0 375 376 if prec > 0 { 377 buf = append(buf, '.') 378 rs := r.utoa(10) 379 for i := prec - len(rs); i > 0; i-- { 380 buf = append(buf, '0') 381 } 382 buf = append(buf, rs...) 383 } 384 385 return string(buf) 386 } 387 388 // Note: FloatPrec (below) is in this file rather than rat.go because 389 // its results are relevant for decimal representation/printing. 390 391 // FloatPrec returns the number n of non-repeating digits immediately 392 // following the decimal point of the decimal representation of x. 393 // The boolean result indicates whether a decimal representation of x 394 // with that many fractional digits is exact or rounded. 395 // 396 // Examples: 397 // 398 // x n exact decimal representation n fractional digits 399 // 0 0 true 0 400 // 1 0 true 1 401 // 1/2 1 true 0.5 402 // 1/3 0 false 0 (0.333... rounded) 403 // 1/4 2 true 0.25 404 // 1/6 1 false 0.2 (0.166... rounded) 405 func (x *Rat) FloatPrec() (n int, exact bool) { 406 stk := getStack() 407 defer stk.free() 408 409 // Determine q and largest p2, p5 such that d = q·2^p2·5^p5. 410 // The results n, exact are: 411 // 412 // n = max(p2, p5) 413 // exact = q == 1 414 // 415 // For details see: 416 // https://en.wikipedia.org/wiki/Repeating_decimal#Reciprocals_of_integers_not_coprime_to_10 417 d := x.Denom().abs // d >= 1 418 419 // Determine p2 by counting factors of 2. 420 // p2 corresponds to the trailing zero bits in d. 421 // Do this first to reduce q as much as possible. 422 var q nat 423 p2 := d.trailingZeroBits() 424 q = q.shr(d, p2) 425 426 // Determine p5 by counting factors of 5. 427 // Build a table starting with an initial power of 5, 428 // and use repeated squaring until the factor doesn't 429 // divide q anymore. Then use the table to determine 430 // the power of 5 in q. 431 const fp = 13 // f == 5^fp 432 var tab []nat // tab[i] == (5^fp)^(2^i) == 5^(fp·2^i) 433 f := nat{1220703125} // == 5^fp (must fit into a uint32 Word) 434 var t, r nat // temporaries 435 for { 436 if _, r = t.div(stk, r, q, f); len(r) != 0 { 437 break // f doesn't divide q evenly 438 } 439 tab = append(tab, f) 440 f = nat(nil).sqr(stk, f) // nat(nil) to ensure a new f for each table entry 441 } 442 443 // Factor q using the table entries, if any. 444 // We start with the largest factor f = tab[len(tab)-1] 445 // that evenly divides q. It does so at most once because 446 // otherwise f·f would also divide q. That can't be true 447 // because f·f is the next higher table entry, contradicting 448 // how f was chosen in the first place. 449 // The same reasoning applies to the subsequent factors. 450 var p5 uint 451 for i := len(tab) - 1; i >= 0; i-- { 452 if t, r = t.div(stk, r, q, tab[i]); len(r) == 0 { 453 p5 += fp * (1 << i) // tab[i] == 5^(fp·2^i) 454 q = q.set(t) 455 } 456 } 457 458 // If fp != 1, we may still have multiples of 5 left. 459 for { 460 if t, r = t.div(stk, r, q, natFive); len(r) != 0 { 461 break 462 } 463 p5++ 464 q = q.set(t) 465 } 466 467 return int(max(p2, p5)), q.cmp(natOne) == 0 468 } 469