OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [math/] [big/] [rat.go] - Blame information for rev 761

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 747 jeremybenn 
// Copyright 2010 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 multi-precision rational numbers.
6 
 
7 
package big
8 
 
9 
import (
10 
        "encoding/binary"
11 
        "errors"
12 
        "fmt"
13 
        "strings"
14 
)
15 
 
16 
// A Rat represents a quotient a/b of arbitrary precision.
17 
// The zero value for a Rat represents the value 0.
18 
type Rat struct {
19 
        a Int
20 
        b nat // len(b) == 0 acts like b == 1
21 
}
22 
 
23 
// NewRat creates a new Rat with numerator a and denominator b.
24 
func NewRat(a, b int64) *Rat {
25 
        return new(Rat).SetFrac64(a, b)
26 
}
27 
 
28 
// SetFrac sets z to a/b and returns z.
29 
func (z *Rat) SetFrac(a, b *Int) *Rat {
30 
        z.a.neg = a.neg != b.neg
31 
        babs := b.abs
32 
        if len(babs) == 0 {
33 
                panic("division by zero")
34 
        }
35 
        if &z.a == b || alias(z.a.abs, babs) {
36 
                babs = nat(nil).set(babs) // make a copy
37 
        }
38 
        z.a.abs = z.a.abs.set(a.abs)
39 
        z.b = z.b.set(babs)
40 
        return z.norm()
41 
}
42 
 
43 
// SetFrac64 sets z to a/b and returns z.
44 
func (z *Rat) SetFrac64(a, b int64) *Rat {
45 
        z.a.SetInt64(a)
46 
        if b == 0 {
47 
                panic("division by zero")
48 
        }
49 
        if b < 0 {
50 
                b = -b
51 
                z.a.neg = !z.a.neg
52 
        }
53 
        z.b = z.b.setUint64(uint64(b))
54 
        return z.norm()
55 
}
56 
 
57 
// SetInt sets z to x (by making a copy of x) and returns z.
58 
func (z *Rat) SetInt(x *Int) *Rat {
59 
        z.a.Set(x)
60 
        z.b = z.b.make(0)
61 
        return z
62 
}
63 
 
64 
// SetInt64 sets z to x and returns z.
65 
func (z *Rat) SetInt64(x int64) *Rat {
66 
        z.a.SetInt64(x)
67 
        z.b = z.b.make(0)
68 
        return z
69 
}
70 
 
71 
// Set sets z to x (by making a copy of x) and returns z.
72 
func (z *Rat) Set(x *Rat) *Rat {
73 
        if z != x {
74 
                z.a.Set(&x.a)
75 
                z.b = z.b.set(x.b)
76 
        }
77 
        return z
78 
}
79 
 
80 
// Abs sets z to |x| (the absolute value of x) and returns z.
81 
func (z *Rat) Abs(x *Rat) *Rat {
82 
        z.Set(x)
83 
        z.a.neg = false
84 
        return z
85 
}
86 
 
87 
// Neg sets z to -x and returns z.
88 
func (z *Rat) Neg(x *Rat) *Rat {
89 
        z.Set(x)
90 
        z.a.neg = len(z.a.abs) > 0 && !z.a.neg // 0 has no sign
91 
        return z
92 
}
93 
 
94 
// Inv sets z to 1/x and returns z.
95 
func (z *Rat) Inv(x *Rat) *Rat {
96 
        if len(x.a.abs) == 0 {
97 
                panic("division by zero")
98 
        }
99 
        z.Set(x)
100 
        a := z.b
101 
        if len(a) == 0 {
102 
                a = a.setWord(1) // materialize numerator
103 
        }
104 
        b := z.a.abs
105 
        if b.cmp(natOne) == 0 {
106 
                b = b.make(0) // normalize denominator
107 
        }
108 
        z.a.abs, z.b = a, b // sign doesn't change
109 
        return z
110 
}
111 
 
112 
// Sign returns:
113 
//
114 
//      -1 if x <  0
115 
//       0 if x == 0
116 
//      +1 if x >  0
117 
//
118 
func (x *Rat) Sign() int {
119 
        return x.a.Sign()
120 
}
121 
 
122 
// IsInt returns true if the denominator of x is 1.
123 
func (x *Rat) IsInt() bool {
124 
        return len(x.b) == 0 || x.b.cmp(natOne) == 0
125 
}
126 
 
127 
// Num returns the numerator of x; it may be <= 0.
128 
// The result is a reference to x's numerator; it
129 
// may change if a new value is assigned to x.
130 
func (x *Rat) Num() *Int {
131 
        return &x.a
132 
}
133 
 
134 
// Denom returns the denominator of x; it is always > 0.
135 
// The result is a reference to x's denominator; it
136 
// may change if a new value is assigned to x.
137 
func (x *Rat) Denom() *Int {
138 
        if len(x.b) == 0 {
139 
                return &Int{abs: nat{1}}
140 
        }
141 
        return &Int{abs: x.b}
142 
}
143 
 
144 
func gcd(x, y nat) nat {
145 
        // Euclidean algorithm.
146 
        var a, b nat
147 
        a = a.set(x)
148 
        b = b.set(y)
149 
        for len(b) != 0 {
150 
                var q, r nat
151 
                _, r = q.div(r, a, b)
152 
                a = b
153 
                b = r
154 
        }
155 
        return a
156 
}
157 
 
158 
func (z *Rat) norm() *Rat {
159 
        switch {
160 
        case len(z.a.abs) == 0:
161 
                // z == 0 - normalize sign and denominator
162 
                z.a.neg = false
163 
                z.b = z.b.make(0)
164 
        case len(z.b) == 0:
165 
                // z is normalized int - nothing to do
166 
        case z.b.cmp(natOne) == 0:
167 
                // z is int - normalize denominator
168 
                z.b = z.b.make(0)
169 
        default:
170 
                if f := gcd(z.a.abs, z.b); f.cmp(natOne) != 0 {
171 
                        z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f)
172 
                        z.b, _ = z.b.div(nil, z.b, f)
173 
                }
174 
        }
175 
        return z
176 
}
177 
 
178 
// mulDenom sets z to the denominator product x*y (by taking into
179 
// account that 0 values for x or y must be interpreted as 1) and
180 
// returns z.
181 
func mulDenom(z, x, y nat) nat {
182 
        switch {
183 
        case len(x) == 0:
184 
                return z.set(y)
185 
        case len(y) == 0:
186 
                return z.set(x)
187 
        }
188 
        return z.mul(x, y)
189 
}
190 
 
191 
// scaleDenom computes x*f.
192 
// If f == 0 (zero value of denominator), the result is (a copy of) x.
193 
func scaleDenom(x *Int, f nat) *Int {
194 
        var z Int
195 
        if len(f) == 0 {
196 
                return z.Set(x)
197 
        }
198 
        z.abs = z.abs.mul(x.abs, f)
199 
        z.neg = x.neg
200 
        return &z
201 
}
202 
 
203 
// Cmp compares x and y and returns:
204 
//
205 
//   -1 if x <  y
206 
//    0 if x == y
207 
//   +1 if x >  y
208 
//
209 
func (x *Rat) Cmp(y *Rat) int {
210 
        return scaleDenom(&x.a, y.b).Cmp(scaleDenom(&y.a, x.b))
211 
}
212 
 
213 
// Add sets z to the sum x+y and returns z.
214 
func (z *Rat) Add(x, y *Rat) *Rat {
215 
        a1 := scaleDenom(&x.a, y.b)
216 
        a2 := scaleDenom(&y.a, x.b)
217 
        z.a.Add(a1, a2)
218 
        z.b = mulDenom(z.b, x.b, y.b)
219 
        return z.norm()
220 
}
221 
 
222 
// Sub sets z to the difference x-y and returns z.
223 
func (z *Rat) Sub(x, y *Rat) *Rat {
224 
        a1 := scaleDenom(&x.a, y.b)
225 
        a2 := scaleDenom(&y.a, x.b)
226 
        z.a.Sub(a1, a2)
227 
        z.b = mulDenom(z.b, x.b, y.b)
228 
        return z.norm()
229 
}
230 
 
231 
// Mul sets z to the product x*y and returns z.
232 
func (z *Rat) Mul(x, y *Rat) *Rat {
233 
        z.a.Mul(&x.a, &y.a)
234 
        z.b = mulDenom(z.b, x.b, y.b)
235 
        return z.norm()
236 
}
237 
 
238 
// Quo sets z to the quotient x/y and returns z.
239 
// If y == 0, a division-by-zero run-time panic occurs.
240 
func (z *Rat) Quo(x, y *Rat) *Rat {
241 
        if len(y.a.abs) == 0 {
242 
                panic("division by zero")
243 
        }
244 
        a := scaleDenom(&x.a, y.b)
245 
        b := scaleDenom(&y.a, x.b)
246 
        z.a.abs = a.abs
247 
        z.b = b.abs
248 
        z.a.neg = a.neg != b.neg
249 
        return z.norm()
250 
}
251 
 
252 
func ratTok(ch rune) bool {
253 
        return strings.IndexRune("+-/0123456789.eE", ch) >= 0
254 
}
255 
 
256 
// Scan is a support routine for fmt.Scanner. It accepts the formats
257 
// 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent.
258 
func (z *Rat) Scan(s fmt.ScanState, ch rune) error {
259 
        tok, err := s.Token(true, ratTok)
260 
        if err != nil {
261 
                return err
262 
        }
263 
        if strings.IndexRune("efgEFGv", ch) < 0 {
264 
                return errors.New("Rat.Scan: invalid verb")
265 
        }
266 
        if _, ok := z.SetString(string(tok)); !ok {
267 
                return errors.New("Rat.Scan: invalid syntax")
268 
        }
269 
        return nil
270 
}
271 
 
272 
// SetString sets z to the value of s and returns z and a boolean indicating
273 
// success. s can be given as a fraction "a/b" or as a floating-point number
274 
// optionally followed by an exponent. If the operation failed, the value of
275 
// z is undefined but the returned value is nil.
276 
func (z *Rat) SetString(s string) (*Rat, bool) {
277 
        if len(s) == 0 {
278 
                return nil, false
279 
        }
280 
 
281 
        // check for a quotient
282 
        sep := strings.Index(s, "/")
283 
        if sep >= 0 {
284 
                if _, ok := z.a.SetString(s[0:sep], 10); !ok {
285 
                        return nil, false
286 
                }
287 
                s = s[sep+1:]
288 
                var err error
289 
                if z.b, _, err = z.b.scan(strings.NewReader(s), 10); err != nil {
290 
                        return nil, false
291 
                }
292 
                return z.norm(), true
293 
        }
294 
 
295 
        // check for a decimal point
296 
        sep = strings.Index(s, ".")
297 
        // check for an exponent
298 
        e := strings.IndexAny(s, "eE")
299 
        var exp Int
300 
        if e >= 0 {
301 
                if e < sep {
302 
                        // The E must come after the decimal point.
303 
                        return nil, false
304 
                }
305 
                if _, ok := exp.SetString(s[e+1:], 10); !ok {
306 
                        return nil, false
307 
                }
308 
                s = s[0:e]
309 
        }
310 
        if sep >= 0 {
311 
                s = s[0:sep] + s[sep+1:]
312 
                exp.Sub(&exp, NewInt(int64(len(s)-sep)))
313 
        }
314 
 
315 
        if _, ok := z.a.SetString(s, 10); !ok {
316 
                return nil, false
317 
        }
318 
        powTen := nat(nil).expNN(natTen, exp.abs, nil)
319 
        if exp.neg {
320 
                z.b = powTen
321 
                z.norm()
322 
        } else {
323 
                z.a.abs = z.a.abs.mul(z.a.abs, powTen)
324 
                z.b = z.b.make(0)
325 
        }
326 
 
327 
        return z, true
328 
}
329 
 
330 
// String returns a string representation of z in the form "a/b" (even if b == 1).
331 
func (x *Rat) String() string {
332 
        s := "/1"
333 
        if len(x.b) != 0 {
334 
                s = "/" + x.b.decimalString()
335 
        }
336 
        return x.a.String() + s
337 
}
338 
 
339 
// RatString returns a string representation of z in the form "a/b" if b != 1,
340 
// and in the form "a" if b == 1.
341 
func (x *Rat) RatString() string {
342 
        if x.IsInt() {
343 
                return x.a.String()
344 
        }
345 
        return x.String()
346 
}
347 
 
348 
// FloatString returns a string representation of z in decimal form with prec
349 
// digits of precision after the decimal point and the last digit rounded.
350 
func (x *Rat) FloatString(prec int) string {
351 
        if x.IsInt() {
352 
                s := x.a.String()
353 
                if prec > 0 {
354 
                        s += "." + strings.Repeat("0", prec)
355 
                }
356 
                return s
357 
        }
358 
        // x.b != 0
359 
 
360 
        q, r := nat(nil).div(nat(nil), x.a.abs, x.b)
361 
 
362 
        p := natOne
363 
        if prec > 0 {
364 
                p = nat(nil).expNN(natTen, nat(nil).setUint64(uint64(prec)), nil)
365 
        }
366 
 
367 
        r = r.mul(r, p)
368 
        r, r2 := r.div(nat(nil), r, x.b)
369 
 
370 
        // see if we need to round up
371 
        r2 = r2.add(r2, r2)
372 
        if x.b.cmp(r2) <= 0 {
373 
                r = r.add(r, natOne)
374 
                if r.cmp(p) >= 0 {
375 
                        q = nat(nil).add(q, natOne)
376 
                        r = nat(nil).sub(r, p)
377 
                }
378 
        }
379 
 
380 
        s := q.decimalString()
381 
        if x.a.neg {
382 
                s = "-" + s
383 
        }
384 
 
385 
        if prec > 0 {
386 
                rs := r.decimalString()
387 
                leadingZeros := prec - len(rs)
388 
                s += "." + strings.Repeat("0", leadingZeros) + rs
389 
        }
390 
 
391 
        return s
392 
}
393 
 
394 
// Gob codec version. Permits backward-compatible changes to the encoding.
395 
const ratGobVersion byte = 1
396 
 
397 
// GobEncode implements the gob.GobEncoder interface.
398 
func (x *Rat) GobEncode() ([]byte, error) {
399 
        buf := make([]byte, 1+4+(len(x.a.abs)+len(x.b))*_S) // extra bytes for version and sign bit (1), and numerator length (4)
400 
        i := x.b.bytes(buf)
401 
        j := x.a.abs.bytes(buf[0:i])
402 
        n := i - j
403 
        if int(uint32(n)) != n {
404 
                // this should never happen
405 
                return nil, errors.New("Rat.GobEncode: numerator too large")
406 
        }
407 
        binary.BigEndian.PutUint32(buf[j-4:j], uint32(n))
408 
        j -= 1 + 4
409 
        b := ratGobVersion << 1 // make space for sign bit
410 
        if x.a.neg {
411 
                b |= 1
412 
        }
413 
        buf[j] = b
414 
        return buf[j:], nil
415 
}
416 
 
417 
// GobDecode implements the gob.GobDecoder interface.
418 
func (z *Rat) GobDecode(buf []byte) error {
419 
        if len(buf) == 0 {
420 
                return errors.New("Rat.GobDecode: no data")
421 
        }
422 
        b := buf[0]
423 
        if b>>1 != ratGobVersion {
424 
                return errors.New(fmt.Sprintf("Rat.GobDecode: encoding version %d not supported", b>>1))
425 
        }
426 
        const j = 1 + 4
427 
        i := j + binary.BigEndian.Uint32(buf[j-4:j])
428 
        z.a.neg = b&1 != 0
429 
        z.a.abs = z.a.abs.setBytes(buf[j:i])
430 
        z.b = z.b.setBytes(buf[i:])
431 
        return nil
432 
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.