Source file src/math/big/ratconv.go

Documentation: math/big

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

View as plain text