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). 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