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).
  55 // The entire string, not just a prefix, must be valid for success. If the
  56 // operation failed, the value of z is undefined but the returned value is nil.
  57 func (z *Rat) SetString(s string) (*Rat, bool) {
  58         if len(s) == 0 {
  59                 return nil, false
  60         }
  61         // len(s) > 0
  62
  63         // parse fraction a/b, if any
  64         if sep := strings.Index(s, "/"); sep >= 0 {
  65                 if _, ok := z.a.SetString(s[:sep], 0); !ok {
  66                         return nil, false
  67                 }
  68                 r := strings.NewReader(s[sep+1:])
  69                 var err error
  70                 if z.b.abs, _, _, err = z.b.abs.scan(r, 0, false); err != nil {
  71                         return nil, false
  72                 }
  73                 // entire string must have been consumed
  74                 if _, err = r.ReadByte(); err != io.EOF {
  75                         return nil, false
  76                 }
  77                 if len(z.b.abs) == 0 {
  78                         return nil, false
  79                 }
  80                 return z.norm(), true
  81         }
  82
  83         // parse floating-point number
  84         r := strings.NewReader(s)
  85
  86         // sign
  87         neg, err := scanSign(r)
  88         if err != nil {
  89                 return nil, false
  90         }
  91
  92         // mantissa
  93         var base int
  94         var fcount int // fractional digit count; valid if <= 0
  95         z.a.abs, base, fcount, err = z.a.abs.scan(r, 0, true)
  96         if err != nil {
  97                 return nil, false
  98         }
  99
 100         // exponent
 101         var exp int64
 102         var ebase int
 103         exp, ebase, err = scanExponent(r, true, true)
 104         if err != nil {
 105                 return nil, false
 106         }
 107
 108         // there should be no unread characters left
 109         if _, err = r.ReadByte(); err != io.EOF {
 110                 return nil, false
 111         }
 112
 113         // special-case 0 (see also issue #16176)
 114         if len(z.a.abs) == 0 {
 115                 return z, true
 116         }
 117         // len(z.a.abs) > 0
 118
 119         // The mantissa may have a radix point (fcount <= 0) and there
 120         // may be a nonzero exponent exp. The radix point amounts to a
 121         // division by base**(-fcount), which equals a multiplication by
 122         // base**fcount. An exponent means multiplication by ebase**exp.
 123         // Multiplications are commutative, so we can apply them in any
 124         // order. We only have powers of 2 and 10, and we split powers
 125         // of 10 into the product of the same powers of 2 and 5. This
 126         // may reduce the the size of shift/multiplication factors or
 127         // divisors required to create the final fraction, depending
 128         // on the actual floating-point value.
 129
 130         // determine binary or decimal exponent contribution of radix point
 131         var exp2, exp5 int64
 132         if fcount < 0 {
 133                 // The mantissa has a radix point ddd.dddd; and
 134                 // -fcount is the number of digits to the right
 135                 // of '.'. Adjust relevant exponent accordingly.
 136                 d := int64(fcount)
 137                 switch base {
 138                 case 10:
 139                         exp5 = d
 140                         fallthrough // 10**e == 5**e * 2**e
 141                 case 2:
 142                         exp2 = d
 143                 case 8:
 144                         exp2 = d * 3 // octal digits are 3 bits each
 145                 case 16:
 146                         exp2 = d * 4 // hexadecimal digits are 4 bits each
 147                 default:
 148                         panic("unexpected mantissa base")
 149                 }
 150                 // fcount consumed - not needed anymore
 151         }
 152
 153         // take actual exponent into account
 154         switch ebase {
 155         case 10:
 156                 exp5 += exp
 157                 fallthrough // see fallthrough above
 158         case 2:
 159                 exp2 += exp
 160         default:
 161                 panic("unexpected exponent base")
 162         }
 163         // exp consumed - not needed anymore
 164
 165         // compute pow5 if needed
 166         pow5 := z.b.abs
 167         if exp5 != 0 {
 168                 n := exp5
 169                 if n < 0 {
 170                         n = -n
 171                 }
 172                 pow5 = pow5.expNN(natFive, nat(nil).setWord(Word(n)), nil)
 173         }
 174
 175         // apply dividend contributions of exponents
 176         // (start with exp5 so the numbers to multiply are smaller)
 177         if exp5 > 0 {
 178                 z.a.abs = z.a.abs.mul(z.a.abs, pow5)
 179                 exp5 = 0
 180         }
 181         if exp2 > 0 {
 182                 if int64(uint(exp2)) != exp2 {
 183                         panic("exponent too large")
 184                 }
 185                 z.a.abs = z.a.abs.shl(z.a.abs, uint(exp2))
 186                 exp2 = 0
 187         }
 188
 189         // apply divisor contributions of exponents
 190         z.b.abs = z.b.abs.setWord(1)
 191         if exp5 < 0 {
 192                 z.b.abs = pow5
 193         }
 194         if exp2 < 0 {
 195                 if int64(uint(-exp2)) != -exp2 {
 196                         panic("exponent too large")
 197                 }
 198                 z.b.abs = z.b.abs.shl(z.b.abs, uint(-exp2))
 199         }
 200
 201         z.a.neg = neg && len(z.a.abs) > 0 // 0 has no sign
 202
 203         return z.norm(), true
 204 }
 205
 206 // scanExponent scans the longest possible prefix of r representing a base 10
 207 // (``e'', ``E'') or a base 2 (``p'', ``P'') exponent, if any. It returns the
 208 // exponent, the exponent base (10 or 2), or a read or syntax error, if any.
 209 //
 210 // If sepOk is set, an underscore character ``_'' may appear between successive
 211 // exponent digits; such underscores do not change the value of the exponent.
 212 // Incorrect placement of underscores is reported as an error if there are no
 213 // other errors. If sepOk is not set, underscores are not recognized and thus
 214 // terminate scanning like any other character that is not a valid digit.
 215 //
 216 //      exponent = ( "e" | "E" | "p" | "P" ) [ sign ] digits .
 217 //      sign     = "+" | "-" .
 218 //      digits   = digit { [ '_' ] digit } .
 219 //      digit    = "0" ... "9" .
 220 //
 221 // A base 2 exponent is only permitted if base2ok is set.
 222 func scanExponent(r io.ByteScanner, base2ok, sepOk bool) (exp int64, base int, err error) {
 223         // one char look-ahead
 224         ch, err := r.ReadByte()
 225         if err != nil {
 226                 if err == io.EOF {
 227                         err = nil
 228                 }
 229                 return 0, 10, err
 230         }
 231
 232         // exponent char
 233         switch ch {
 234         case 'e', 'E':
 235                 base = 10
 236         case 'p', 'P':
 237                 if base2ok {
 238                         base = 2
 239                         break // ok
 240                 }
 241                 fallthrough // binary exponent not permitted
 242         default:
 243                 r.UnreadByte() // ch does not belong to exponent anymore
 244                 return 0, 10, nil
 245         }
 246
 247         // sign
 248         var digits []byte
 249         ch, err = r.ReadByte()
 250         if err == nil && (ch == '+' || ch == '-') {
 251                 if ch == '-' {
 252                         digits = append(digits, '-')
 253                 }
 254                 ch, err = r.ReadByte()
 255         }
 256
 257         // prev encodes the previously seen char: it is one
 258         // of '_', '0' (a digit), or '.' (anything else). A
 259         // valid separator '_' may only occur after a digit.
 260         prev := '.'
 261         invalSep := false
 262
 263         // exponent value
 264         hasDigits := false
 265         for err == nil {
 266                 if '0' <= ch && ch <= '9' {
 267                         digits = append(digits, ch)
 268                         prev = '0'
 269                         hasDigits = true
 270                 } else if ch == '_' && sepOk {
 271                         if prev != '0' {
 272                                 invalSep = true
 273                         }
 274                         prev = '_'
 275                 } else {
 276                         r.UnreadByte() // ch does not belong to number anymore
 277                         break
 278                 }
 279                 ch, err = r.ReadByte()
 280         }
 281
 282         if err == io.EOF {
 283                 err = nil
 284         }
 285         if err == nil && !hasDigits {
 286                 err = errNoDigits
 287         }
 288         if err == nil {
 289                 exp, err = strconv.ParseInt(string(digits), 10, 64)
 290         }
 291         // other errors take precedence over invalid separators
 292         if err == nil && (invalSep || prev == '_') {
 293                 err = errInvalSep
 294         }
 295
 296         return
 297 }
 298
 299 // String returns a string representation of x in the form "a/b" (even if b == 1).
 300 func (x *Rat) String() string {
 301         return string(x.marshal())
 302 }
 303
 304 // marshal implements String returning a slice of bytes
 305 func (x *Rat) marshal() []byte {
 306         var buf []byte
 307         buf = x.a.Append(buf, 10)
 308         buf = append(buf, '/')
 309         if len(x.b.abs) != 0 {
 310                 buf = x.b.Append(buf, 10)
 311         } else {
 312                 buf = append(buf, '1')
 313         }
 314         return buf
 315 }
 316
 317 // RatString returns a string representation of x in the form "a/b" if b != 1,
 318 // and in the form "a" if b == 1.
 319 func (x *Rat) RatString() string {
 320         if x.IsInt() {
 321                 return x.a.String()
 322         }
 323         return x.String()
 324 }
 325
 326 // FloatString returns a string representation of x in decimal form with prec
 327 // digits of precision after the radix point. The last digit is rounded to
 328 // nearest, with halves rounded away from zero.
 329 func (x *Rat) FloatString(prec int) string {
 330         var buf []byte
 331
 332         if x.IsInt() {
 333                 buf = x.a.Append(buf, 10)
 334                 if prec > 0 {
 335                         buf = append(buf, '.')
 336                         for i := prec; i > 0; i-- {
 337                                 buf = append(buf, '0')
 338                         }
 339                 }
 340                 return string(buf)
 341         }
 342         // x.b.abs != 0
 343
 344         q, r := nat(nil).div(nat(nil), x.a.abs, x.b.abs)
 345
 346         p := natOne
 347         if prec > 0 {
 348                 p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil)
 349         }
 350
 351         r = r.mul(r, p)
 352         r, r2 := r.div(nat(nil), r, x.b.abs)
 353
 354         // see if we need to round up
 355         r2 = r2.add(r2, r2)
 356         if x.b.abs.cmp(r2) <= 0 {
 357                 r = r.add(r, natOne)
 358                 if r.cmp(p) >= 0 {
 359                         q = nat(nil).add(q, natOne)
 360                         r = nat(nil).sub(r, p)
 361                 }
 362         }
 363
 364         if x.a.neg {
 365                 buf = append(buf, '-')
 366         }
 367         buf = append(buf, q.utoa(10)...) // itoa ignores sign if q == 0
 368
 369         if prec > 0 {
 370                 buf = append(buf, '.')
 371                 rs := r.utoa(10)
 372                 for i := prec - len(rs); i > 0; i-- {
 373                         buf = append(buf, '0')
 374                 }
 375                 buf = append(buf, rs...)
 376         }
 377
 378         return string(buf)
 379 }