# Source file src/math/big/ratconv.go

2  // Use of this source code is governed by a BSD-style
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  		}
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
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
115  	if len(z.a.abs) == 0 {
116  		return z.norm(), 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, false) // 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) {
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
251  	if err == nil && (ch == '+' || ch == '-') {
252  		if ch == '-' {
253  			digits = append(digits, '-')
254  		}
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  		}
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, false)
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
357  	if x.b.abs.cmp(r2) <= 0 {
359  		if r.cmp(p) >= 0 {
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
382  // Note: FloatPrec (below) is in this file rather than rat.go because
383  //       its results are relevant for decimal representation/printing.
384
385  // FloatPrec returns the number n of non-repeating digits immediately
386  // following the decimal point of the decimal representation of x.
387  // The boolean result indicates whether a decimal representation of x
388  // with that many fractional digits is exact or rounded.
389  //
390  // Examples:
391  //
392  //	x      n    exact    decimal representation n fractional digits
393  //	0      0    true     0
394  //	1      0    true     1
395  //	1/2    1    true     0.5
396  //	1/3    0    false    0       (0.333... rounded)
397  //	1/4    2    true     0.25
398  //	1/6    1    false    0.2     (0.166... rounded)
399  func (x *Rat) FloatPrec() (n int, exact bool) {
400  	// Determine q and largest p2, p5 such that d = q·2^p2·5^p5.
401  	// The results n, exact are:
402  	//
403  	//     n = max(p2, p5)
404  	//     exact = q == 1
405  	//
406  	// For details see:
407  	// https://en.wikipedia.org/wiki/Repeating_decimal#Reciprocals_of_integers_not_coprime_to_10
408  	d := x.Denom().abs // d >= 1
409
410  	// Determine p2 by counting factors of 2.
411  	// p2 corresponds to the trailing zero bits in d.
412  	// Do this first to reduce q as much as possible.
413  	var q nat
414  	p2 := d.trailingZeroBits()
415  	q = q.shr(d, p2)
416
417  	// Determine p5 by counting factors of 5.
418  	// Build a table starting with an initial power of 5,
419  	// and use repeated squaring until the factor doesn't
420  	// divide q anymore. Then use the table to determine
421  	// the power of 5 in q.
422  	const fp = 13        // f == 5^fp
423  	var tab []nat        // tab[i] == (5^fp)^(2^i) == 5^(fp·2^i)
424  	f := nat{1220703125} // == 5^fp (must fit into a uint32 Word)
425  	var t, r nat         // temporaries
426  	for {
427  		if _, r = t.div(r, q, f); len(r) != 0 {
428  			break // f doesn't divide q evenly
429  		}
430  		tab = append(tab, f)
431  		f = nat(nil).sqr(f) // nat(nil) to ensure a new f for each table entry
432  	}
433
434  	// Factor q using the table entries, if any.
436  	// that evenly divides q. It does so at most once because
437  	// otherwise f·f would also divide q. That can't be true
438  	// because f·f is the next higher table entry, contradicting
439  	// how f was chosen in the first place.
440  	// The same reasoning applies to the subsequent factors.
441  	var p5 uint
442  	for i := len(tab) - 1; i >= 0; i-- {
443  		if t, r = t.div(r, q, tab[i]); len(r) == 0 {
444  			p5 += fp * (1 << i) // tab[i] == 5^(fp·2^i)
445  			q = q.set(t)
446  		}
447  	}
448
449  	// If fp != 1, we may still have multiples of 5 left.
450  	for {
451  		if t, r = t.div(r, q, natFive); len(r) != 0 {
452  			break
453  		}
454  		p5++
455  		q = q.set(t)
456  	}
457
458  	return int(max(p2, p5)), q.cmp(natOne) == 0
459  }
460

View as plain text