Source file src/pkg/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		// 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