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  			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) // 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)
   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
View as plain text