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, 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  		}
   173  		if n > 1e6 {
   174  			return nil, false // avoid excessively large exponents
   175  		}
   176  		pow5 := z.b.abs.expNN(natFive, nat(nil).setWord(Word(n)), nil) // use underlying array of z.b.abs
   177  		if exp5 > 0 {
   178  			z.a.abs = z.a.abs.mul(z.a.abs, pow5)
   179  			z.b.abs = z.b.abs.setWord(1)
   180  		} else {
   181  			z.b.abs = pow5
   182  		}
   183  	} else {
   184  		z.b.abs = z.b.abs.setWord(1)
   185  	}
   186  
   187  	// apply exp2 contributions
   188  	if exp2 < -1e7 || exp2 > 1e7 {
   189  		return nil, false // avoid excessively large exponents
   190  	}
   191  	if exp2 > 0 {
   192  		z.a.abs = z.a.abs.shl(z.a.abs, uint(exp2))
   193  	} else if exp2 < 0 {
   194  		z.b.abs = z.b.abs.shl(z.b.abs, uint(-exp2))
   195  	}
   196  
   197  	z.a.neg = neg && len(z.a.abs) > 0 // 0 has no sign
   198  
   199  	return z.norm(), true
   200  }
   201  
   202  // scanExponent scans the longest possible prefix of r representing a base 10
   203  // (``e'', ``E'') or a base 2 (``p'', ``P'') exponent, if any. It returns the
   204  // exponent, the exponent base (10 or 2), or a read or syntax error, if any.
   205  //
   206  // If sepOk is set, an underscore character ``_'' may appear between successive
   207  // exponent digits; such underscores do not change the value of the exponent.
   208  // Incorrect placement of underscores is reported as an error if there are no
   209  // other errors. If sepOk is not set, underscores are not recognized and thus
   210  // terminate scanning like any other character that is not a valid digit.
   211  //
   212  //	exponent = ( "e" | "E" | "p" | "P" ) [ sign ] digits .
   213  //	sign     = "+" | "-" .
   214  //	digits   = digit { [ '_' ] digit } .
   215  //	digit    = "0" ... "9" .
   216  //
   217  // A base 2 exponent is only permitted if base2ok is set.
   218  func scanExponent(r io.ByteScanner, base2ok, sepOk bool) (exp int64, base int, err error) {
   219  	// one char look-ahead
   220  	ch, err := r.ReadByte()
   221  	if err != nil {
   222  		if err == io.EOF {
   223  			err = nil
   224  		}
   225  		return 0, 10, err
   226  	}
   227  
   228  	// exponent char
   229  	switch ch {
   230  	case 'e', 'E':
   231  		base = 10
   232  	case 'p', 'P':
   233  		if base2ok {
   234  			base = 2
   235  			break // ok
   236  		}
   237  		fallthrough // binary exponent not permitted
   238  	default:
   239  		r.UnreadByte() // ch does not belong to exponent anymore
   240  		return 0, 10, nil
   241  	}
   242  
   243  	// sign
   244  	var digits []byte
   245  	ch, err = r.ReadByte()
   246  	if err == nil && (ch == '+' || ch == '-') {
   247  		if ch == '-' {
   248  			digits = append(digits, '-')
   249  		}
   250  		ch, err = r.ReadByte()
   251  	}
   252  
   253  	// prev encodes the previously seen char: it is one
   254  	// of '_', '0' (a digit), or '.' (anything else). A
   255  	// valid separator '_' may only occur after a digit.
   256  	prev := '.'
   257  	invalSep := false
   258  
   259  	// exponent value
   260  	hasDigits := false
   261  	for err == nil {
   262  		if '0' <= ch && ch <= '9' {
   263  			digits = append(digits, ch)
   264  			prev = '0'
   265  			hasDigits = true
   266  		} else if ch == '_' && sepOk {
   267  			if prev != '0' {
   268  				invalSep = true
   269  			}
   270  			prev = '_'
   271  		} else {
   272  			r.UnreadByte() // ch does not belong to number anymore
   273  			break
   274  		}
   275  		ch, err = r.ReadByte()
   276  	}
   277  
   278  	if err == io.EOF {
   279  		err = nil
   280  	}
   281  	if err == nil && !hasDigits {
   282  		err = errNoDigits
   283  	}
   284  	if err == nil {
   285  		exp, err = strconv.ParseInt(string(digits), 10, 64)
   286  	}
   287  	// other errors take precedence over invalid separators
   288  	if err == nil && (invalSep || prev == '_') {
   289  		err = errInvalSep
   290  	}
   291  
   292  	return
   293  }
   294  
   295  // String returns a string representation of x in the form "a/b" (even if b == 1).
   296  func (x *Rat) String() string {
   297  	return string(x.marshal())
   298  }
   299  
   300  // marshal implements String returning a slice of bytes
   301  func (x *Rat) marshal() []byte {
   302  	var buf []byte
   303  	buf = x.a.Append(buf, 10)
   304  	buf = append(buf, '/')
   305  	if len(x.b.abs) != 0 {
   306  		buf = x.b.Append(buf, 10)
   307  	} else {
   308  		buf = append(buf, '1')
   309  	}
   310  	return buf
   311  }
   312  
   313  // RatString returns a string representation of x in the form "a/b" if b != 1,
   314  // and in the form "a" if b == 1.
   315  func (x *Rat) RatString() string {
   316  	if x.IsInt() {
   317  		return x.a.String()
   318  	}
   319  	return x.String()
   320  }
   321  
   322  // FloatString returns a string representation of x in decimal form with prec
   323  // digits of precision after the radix point. The last digit is rounded to
   324  // nearest, with halves rounded away from zero.
   325  func (x *Rat) FloatString(prec int) string {
   326  	var buf []byte
   327  
   328  	if x.IsInt() {
   329  		buf = x.a.Append(buf, 10)
   330  		if prec > 0 {
   331  			buf = append(buf, '.')
   332  			for i := prec; i > 0; i-- {
   333  				buf = append(buf, '0')
   334  			}
   335  		}
   336  		return string(buf)
   337  	}
   338  	// x.b.abs != 0
   339  
   340  	q, r := nat(nil).div(nat(nil), x.a.abs, x.b.abs)
   341  
   342  	p := natOne
   343  	if prec > 0 {
   344  		p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil)
   345  	}
   346  
   347  	r = r.mul(r, p)
   348  	r, r2 := r.div(nat(nil), r, x.b.abs)
   349  
   350  	// see if we need to round up
   351  	r2 = r2.add(r2, r2)
   352  	if x.b.abs.cmp(r2) <= 0 {
   353  		r = r.add(r, natOne)
   354  		if r.cmp(p) >= 0 {
   355  			q = nat(nil).add(q, natOne)
   356  			r = nat(nil).sub(r, p)
   357  		}
   358  	}
   359  
   360  	if x.a.neg {
   361  		buf = append(buf, '-')
   362  	}
   363  	buf = append(buf, q.utoa(10)...) // itoa ignores sign if q == 0
   364  
   365  	if prec > 0 {
   366  		buf = append(buf, '.')
   367  		rs := r.utoa(10)
   368  		for i := prec - len(rs); i > 0; i-- {
   369  			buf = append(buf, '0')
   370  		}
   371  		buf = append(buf, rs...)
   372  	}
   373  
   374  	return string(buf)
   375  }
   376  

View as plain text