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         // apply exp5 contributions
 167         // (start with exp5 so the numbers to multiply are smaller)
 168         if exp5 != 0 {
 169                 n := exp5
 170                 if n < 0 {
 171                         n = -n
 172                         if n < 0 {
 173                                 // This can occur if -n overflows. -(-1 << 63) would become
 174                                 // -1 << 63, which is still negative.
 175                                 return nil, false
 176                         }
 177                 }
 178                 if n > 1e6 {
 179                         return nil, false // avoid excessively large exponents
 180                 }
 181                 pow5 := z.b.abs.expNN(natFive, nat(nil).setWord(Word(n)), nil, false) // use underlying array of z.b.abs
 182                 if exp5 > 0 {
 183                         z.a.abs = z.a.abs.mul(z.a.abs, pow5)
 184                         z.b.abs = z.b.abs.setWord(1)
 185                 } else {
 186                         z.b.abs = pow5
 187                 }
 188         } else {
 189                 z.b.abs = z.b.abs.setWord(1)
 190         }
 191
 192         // apply exp2 contributions
 193         if exp2 < -1e7 || exp2 > 1e7 {
 194                 return nil, false // avoid excessively large exponents
 195         }
 196         if exp2 > 0 {
 197                 z.a.abs = z.a.abs.shl(z.a.abs, uint(exp2))
 198         } else if exp2 < 0 {
 199                 z.b.abs = z.b.abs.shl(z.b.abs, uint(-exp2))
 200         }
 201
 202         z.a.neg = neg && len(z.a.abs) > 0 // 0 has no sign
 203
 204         return z.norm(), true
 205 }
 206
 207 // scanExponent scans the longest possible prefix of r representing a base 10
 208 // (“e”, “E”) or a base 2 (“p”, “P”) exponent, if any. It returns the
 209 // exponent, the exponent base (10 or 2), or a read or syntax error, if any.
 210 //
 211 // If sepOk is set, an underscore character “_” may appear between successive
 212 // exponent digits; such underscores do not change the value of the exponent.
 213 // Incorrect placement of underscores is reported as an error if there are no
 214 // other errors. If sepOk is not set, underscores are not recognized and thus
 215 // terminate scanning like any other character that is not a valid digit.
 216 //
 217 //      exponent = ( "e" | "E" | "p" | "P" ) [ sign ] digits .
 218 //      sign     = "+" | "-" .
 219 //      digits   = digit { [ '_' ] digit } .
 220 //      digit    = "0" ... "9" .
 221 //
 222 // A base 2 exponent is only permitted if base2ok is set.
 223 func scanExponent(r io.ByteScanner, base2ok, sepOk bool) (exp int64, base int, err error) {
 224         // one char look-ahead
 225         ch, err := r.ReadByte()
 226         if err != nil {
 227                 if err == io.EOF {
 228                         err = nil
 229                 }
 230                 return 0, 10, err
 231         }
 232
 233         // exponent char
 234         switch ch {
 235         case 'e', 'E':
 236                 base = 10
 237         case 'p', 'P':
 238                 if base2ok {
 239                         base = 2
 240                         break // ok
 241                 }
 242                 fallthrough // binary exponent not permitted
 243         default:
 244                 r.UnreadByte() // ch does not belong to exponent anymore
 245                 return 0, 10, nil
 246         }
 247
 248         // sign
 249         var digits []byte
 250         ch, err = r.ReadByte()
 251         if err == nil && (ch == '+' || ch == '-') {
 252                 if ch == '-' {
 253                         digits = append(digits, '-')
 254                 }
 255                 ch, err = r.ReadByte()
 256         }
 257
 258         // prev encodes the previously seen char: it is one
 259         // of '_', '0' (a digit), or '.' (anything else). A
 260         // valid separator '_' may only occur after a digit.
 261         prev := '.'
 262         invalSep := false
 263
 264         // exponent value
 265         hasDigits := false
 266         for err == nil {
 267                 if '0' <= ch && ch <= '9' {
 268                         digits = append(digits, ch)
 269                         prev = '0'
 270                         hasDigits = true
 271                 } else if ch == '_' && sepOk {
 272                         if prev != '0' {
 273                                 invalSep = true
 274                         }
 275                         prev = '_'
 276                 } else {
 277                         r.UnreadByte() // ch does not belong to number anymore
 278                         break
 279                 }
 280                 ch, err = r.ReadByte()
 281         }
 282
 283         if err == io.EOF {
 284                 err = nil
 285         }
 286         if err == nil && !hasDigits {
 287                 err = errNoDigits
 288         }
 289         if err == nil {
 290                 exp, err = strconv.ParseInt(string(digits), 10, 64)
 291         }
 292         // other errors take precedence over invalid separators
 293         if err == nil && (invalSep || prev == '_') {
 294                 err = errInvalSep
 295         }
 296
 297         return
 298 }
 299
 300 // String returns a string representation of x in the form "a/b" (even if b == 1).
 301 func (x *Rat) String() string {
 302         return string(x.marshal())
 303 }
 304
 305 // marshal implements String returning a slice of bytes
 306 func (x *Rat) marshal() []byte {
 307         var buf []byte
 308         buf = x.a.Append(buf, 10)
 309         buf = append(buf, '/')
 310         if len(x.b.abs) != 0 {
 311                 buf = x.b.Append(buf, 10)
 312         } else {
 313                 buf = append(buf, '1')
 314         }
 315         return buf
 316 }
 317
 318 // RatString returns a string representation of x in the form "a/b" if b != 1,
 319 // and in the form "a" if b == 1.
 320 func (x *Rat) RatString() string {
 321         if x.IsInt() {
 322                 return x.a.String()
 323         }
 324         return x.String()
 325 }
 326
 327 // FloatString returns a string representation of x in decimal form with prec
 328 // digits of precision after the radix point. The last digit is rounded to
 329 // nearest, with halves rounded away from zero.
 330 func (x *Rat) FloatString(prec int) string {
 331         var buf []byte
 332
 333         if x.IsInt() {
 334                 buf = x.a.Append(buf, 10)
 335                 if prec > 0 {
 336                         buf = append(buf, '.')
 337                         for i := prec; i > 0; i-- {
 338                                 buf = append(buf, '0')
 339                         }
 340                 }
 341                 return string(buf)
 342         }
 343         // x.b.abs != 0
 344
 345         q, r := nat(nil).div(nat(nil), x.a.abs, x.b.abs)
 346
 347         p := natOne
 348         if prec > 0 {
 349                 p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil, false)
 350         }
 351
 352         r = r.mul(r, p)
 353         r, r2 := r.div(nat(nil), r, x.b.abs)
 354
 355         // see if we need to round up
 356         r2 = r2.add(r2, r2)
 357         if x.b.abs.cmp(r2) <= 0 {
 358                 r = r.add(r, natOne)
 359                 if r.cmp(p) >= 0 {
 360                         q = nat(nil).add(q, natOne)
 361                         r = nat(nil).sub(r, p)
 362                 }
 363         }
 364
 365         if x.a.neg {
 366                 buf = append(buf, '-')
 367         }
 368         buf = append(buf, q.utoa(10)...) // itoa ignores sign if q == 0
 369
 370         if prec > 0 {
 371                 buf = append(buf, '.')
 372                 rs := r.utoa(10)
 373                 for i := prec - len(rs); i > 0; i-- {
 374                         buf = append(buf, '0')
 375                 }
 376                 buf = append(buf, rs...)
 377         }
 378
 379         return string(buf)
 380 }
 381
 382 // Note: FloatPrec (below) is in this file rather than rat.go because
 383 //       its results are relevant for decimal representation/printing.
 384
 385 // FloatPrec returns the number n of non-repeating digits immediately
 386 // following the decimal point of the decimal representation of x.
 387 // The boolean result indicates whether a decimal representation of x
 388 // with that many fractional digits is exact or rounded.
 389 //
 390 // Examples:
 391 //
 392 //      x      n    exact    decimal representation n fractional digits
 393 //      0      0    true     0
 394 //      1      0    true     1
 395 //      1/2    1    true     0.5
 396 //      1/3    0    false    0       (0.333... rounded)
 397 //      1/4    2    true     0.25
 398 //      1/6    1    false    0.2     (0.166... rounded)
 399 func (x *Rat) FloatPrec() (n int, exact bool) {
 400         // Determine q and largest p2, p5 such that d = q·2^p2·5^p5.
 401         // The results n, exact are:
 402         //
 403         //     n = max(p2, p5)
 404         //     exact = q == 1
 405         //
 406         // See https://en.wikipedia.org/wiki/Repeating_decimal for
 407         // details.
 408         d := x.Denom().abs // d >= 1
 409
 410         // Determine p2 by counting factors of 2.
 411         // p2 corresponds to the trailing zero bits in d.
 412         // Do this first to reduce q as much as possible.
 413         var q nat
 414         p2 := d.trailingZeroBits()
 415         q = q.shr(d, p2)
 416
 417         // Determine p5 by counting factors of 5.
 418
 419         // Build a table starting with an initial power of 5,
 420         // and using repeated squaring until the factor doesn't
 421         // divide q anymore. Then use the table to determine
 422         // the power of 5 in q.
 423         //
 424         // Setting the table limit to 0 turns this off;
 425         // a limit of 1 uses just one factor 5^fp.
 426         // Larger values build up a more comprehensive table.
 427         const fp = 13        // f == 5^fp
 428         const limit = 100    // table size limit
 429         var tab []nat        // tab[i] == 5^(fp·2^i)
 430         f := nat{1220703125} // == 5^fp (must fit into a uint32 Word)
 431         var t, r nat         // temporaries
 432         for len(tab) < limit {
 433                 if _, r = t.div(r, q, f); len(r) != 0 {
 434                         break // f doesn't divide q evenly
 435                 }
 436                 tab = append(tab, f)
 437                 f = f.sqr(f)
 438         }
 439
 440         // TODO(gri) Optimization: don't waste the successful
 441         //           division q/f above; instead reduce q and
 442         //           count the multiples.
 443
 444         // Factor q using the table entries, if any.
 445         var p5, p uint
 446         for i := len(tab) - 1; i >= 0; i-- {
 447                 q, p = multiples(q, tab[i])
 448                 p5 += p << i * fp
 449         }
 450
 451         q, p = multiples(q, natFive)
 452         p5 += p
 453
 454         return int(max(p2, p5)), q.cmp(natOne) == 0
 455 }
 456
 457 // multiples returns d and largest p such that x = d·f^p.
 458 // x and f must not be 0.
 459 func multiples(x, f nat) (d nat, p uint) {
 460         // Determine p through repeated division.
 461         d = d.set(x)
 462         // p == 0
 463         var q, r nat
 464         for {
 465                 // invariant x == d·f^p
 466                 q, r = q.div(r, d, f)
 467                 if len(r) != 0 {
 468                         return
 469                 }
 470                 // q == d/f
 471                 // x == q·f·f^p
 472                 p++
 473                 // x == q·f^p
 474                 d = d.set(q)
 475         }
 476 }