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 747

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.