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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [strconv/] [decimal.go] - Blame information for rev 867

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


// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
// Multiprecision decimal numbers.
// For floating-point formatting only; not general purpose.
// Only operations are assign and (binary) left/right shift.
// Can do binary floating point in multiprecision decimal precisely
// because 2 divides 10; cannot do decimal floating point
// in multiprecision binary precisely.
 
package strconv
 
type decimal struct {
        // TODO(rsc): Can make d[] a bit smaller and add
        // truncated bool;
        d   [800]byte // digits
        nd  int       // number of digits used
        dp  int       // decimal point
        neg bool
}
 
func (a *decimal) String() string {
        n := 10 + a.nd
        if a.dp > 0 {
                n += a.dp
        }
        if a.dp < 0 {
                n += -a.dp
        }
 
        buf := make([]byte, n)
        w := 0
        switch {
        case a.nd == 0:
                return "0"
 
        case a.dp <= 0:
                // zeros fill space between decimal point and digits
                buf[w] = '0'
                w++
                buf[w] = '.'
                w++
                w += digitZero(buf[w : w+-a.dp])
                w += copy(buf[w:], a.d[0:a.nd])
 
        case a.dp < a.nd:
                // decimal point in middle of digits
                w += copy(buf[w:], a.d[0:a.dp])
                buf[w] = '.'
                w++
                w += copy(buf[w:], a.d[a.dp:a.nd])
 
        default:
                // zeros fill space between digits and decimal point
                w += copy(buf[w:], a.d[0:a.nd])
                w += digitZero(buf[w : w+a.dp-a.nd])
        }
        return string(buf[0:w])
}
 
func digitZero(dst []byte) int {
        for i := range dst {
                dst[i] = '0'
        }
        return len(dst)
}
 
// trim trailing zeros from number.
// (They are meaningless; the decimal point is tracked
// independent of the number of digits.)
func trim(a *decimal) {
        for a.nd > 0 && a.d[a.nd-1] == '0' {
                a.nd--
        }
        if a.nd == 0 {
                a.dp = 0
        }
}
 
// Assign v to a.
func (a *decimal) Assign(v uint64) {
        var buf [50]byte
 
        // Write reversed decimal in buf.
        n := 0
        for v > 0 {
                v1 := v / 10
                v -= 10 * v1
                buf[n] = byte(v + '0')
                n++
                v = v1
        }
 
        // Reverse again to produce forward decimal in a.d.
        a.nd = 0
        for n--; n >= 0; n-- {
                a.d[a.nd] = buf[n]
                a.nd++
        }
        a.dp = a.nd
        trim(a)
}
 
// Maximum shift that we can do in one pass without overflow.
// Signed int has 31 bits, and we have to be able to accommodate 9<
const maxShift = 27
 
// Binary shift right (* 2) by k bits.  k <= maxShift to avoid overflow.
func rightShift(a *decimal, k uint) {
        r := 0 // read pointer
        w := 0 // write pointer
 
        // Pick up enough leading digits to cover first shift.
        n := 0
        for ; n>>k == 0; r++ {
                if r >= a.nd {
                        if n == 0 {
                                // a == 0; shouldn't get here, but handle anyway.
                                a.nd = 0
                                return
                        }
                        for n>>k == 0 {
                                n = n * 10
                                r++
                        }
                        break
                }
                c := int(a.d[r])
                n = n*10 + c - '0'
        }
        a.dp -= r - 1
 
        // Pick up a digit, put down a digit.
        for ; r < a.nd; r++ {
                c := int(a.d[r])
                dig := n >> k
                n -= dig << k
                a.d[w] = byte(dig + '0')
                w++
                n = n*10 + c - '0'
        }
 
        // Put down extra digits.
        for n > 0 {
                dig := n >> k
                n -= dig << k
                a.d[w] = byte(dig + '0')
                w++
                n = n * 10
        }
 
        a.nd = w
        trim(a)
}
 
// Cheat sheet for left shift: table indexed by shift count giving
// number of new digits that will be introduced by that shift.
//
// For example, leftcheats[4] = {2, "625"}.  That means that
// if we are shifting by 4 (multiplying by 16), it will add 2 digits
// when the string prefix is "625" through "999", and one fewer digit
// if the string prefix is "000" through "624".
//
// Credit for this trick goes to Ken.
 
type leftCheat struct {
        delta  int    // number of new digits
        cutoff string //   minus one digit if original < a.
}
 
var leftcheats = []leftCheat{
        // Leading digits of 1/2^i = 5^i.
        // 5^23 is not an exact 64-bit floating point number,
        // so have to use bc for the math.
        /*
                seq 27 | sed 's/^/5^/' | bc |
                awk 'BEGIN{ print "\tleftCheat{ 0, \"\" }," }
                {
                        log2 = log(2)/log(10)
                        printf("\tleftCheat{ %d, \"%s\" },\t// * %d\n",
                                int(log2*NR+1), $0, 2**NR)
                }'
        */
        {0, ""},
        {1, "5"},                   // * 2
        {1, "25"},                  // * 4
        {1, "125"},                 // * 8
        {2, "625"},                 // * 16
        {2, "3125"},                // * 32
        {2, "15625"},               // * 64
        {3, "78125"},               // * 128
        {3, "390625"},              // * 256
        {3, "1953125"},             // * 512
        {4, "9765625"},             // * 1024
        {4, "48828125"},            // * 2048
        {4, "244140625"},           // * 4096
        {4, "1220703125"},          // * 8192
        {5, "6103515625"},          // * 16384
        {5, "30517578125"},         // * 32768
        {5, "152587890625"},        // * 65536
        {6, "762939453125"},        // * 131072
        {6, "3814697265625"},       // * 262144
        {6, "19073486328125"},      // * 524288
        {7, "95367431640625"},      // * 1048576
        {7, "476837158203125"},     // * 2097152
        {7, "2384185791015625"},    // * 4194304
        {7, "11920928955078125"},   // * 8388608
        {8, "59604644775390625"},   // * 16777216
        {8, "298023223876953125"},  // * 33554432
        {8, "1490116119384765625"}, // * 67108864
        {9, "7450580596923828125"}, // * 134217728
}
 
// Is the leading prefix of b lexicographically less than s?
func prefixIsLessThan(b []byte, s string) bool {
        for i := 0; i < len(s); i++ {
                if i >= len(b) {
                        return true
                }
                if b[i] != s[i] {
                        return b[i] < s[i]
                }
        }
        return false
}
 
// Binary shift left (/ 2) by k bits.  k <= maxShift to avoid overflow.
func leftShift(a *decimal, k uint) {
        delta := leftcheats[k].delta
        if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) {
                delta--
        }
 
        r := a.nd         // read index
        w := a.nd + delta // write index
        n := 0
 
        // Pick up a digit, put down a digit.
        for r--; r >= 0; r-- {
                n += (int(a.d[r]) - '0') << k
                quo := n / 10
                rem := n - 10*quo
                w--
                a.d[w] = byte(rem + '0')
                n = quo
        }
 
        // Put down extra digits.
        for n > 0 {
                quo := n / 10
                rem := n - 10*quo
                w--
                a.d[w] = byte(rem + '0')
                n = quo
        }
 
        a.nd += delta
        a.dp += delta
        trim(a)
}
 
// Binary shift left (k > 0) or right (k < 0).
func (a *decimal) Shift(k int) {
        switch {
        case a.nd == 0:
                // nothing to do: a == 0
        case k > 0:
                for k > maxShift {
                        leftShift(a, maxShift)
                        k -= maxShift
                }
                leftShift(a, uint(k))
        case k < 0:
                for k < -maxShift {
                        rightShift(a, maxShift)
                        k += maxShift
                }
                rightShift(a, uint(-k))
        }
}
 
// If we chop a at nd digits, should we round up?
func shouldRoundUp(a *decimal, nd int) bool {
        if nd < 0 || nd >= a.nd {
                return false
        }
        if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even
                return nd > 0 && (a.d[nd-1]-'0')%2 != 0
        }
        // not halfway - digit tells all
        return a.d[nd] >= '5'
}
 
// Round a to nd digits (or fewer).
// Returns receiver for convenience.
// If nd is zero, it means we're rounding
// just to the left of the digits, as in
// 0.09 -> 0.1.
func (a *decimal) Round(nd int) {
        if nd < 0 || nd >= a.nd {
                return
        }
        if shouldRoundUp(a, nd) {
                a.RoundUp(nd)
        } else {
                a.RoundDown(nd)
        }
}
 
// Round a down to nd digits (or fewer).
// Returns receiver for convenience.
func (a *decimal) RoundDown(nd int) {
        if nd < 0 || nd >= a.nd {
                return
        }
        a.nd = nd
        trim(a)
}
 
// Round a up to nd digits (or fewer).
// Returns receiver for convenience.
func (a *decimal) RoundUp(nd int) {
        if nd < 0 || nd >= a.nd {
                return
        }
 
        // round up
        for i := nd - 1; i >= 0; i-- {
                c := a.d[i]
                if c < '9' { // can stop after this digit
                        a.d[i]++
                        a.nd = i + 1
                        return
                }
        }
 
        // Number is all 9s.
        // Change to single 1 with adjusted decimal point.
        a.d[0] = '1'
        a.nd = 1
        a.dp++
}
 
// Extract integer part, rounded appropriately.
// No guarantees about overflow.
func (a *decimal) RoundedInteger() uint64 {
        if a.dp > 20 {
                return 0xFFFFFFFFFFFFFFFF
        }
        var i int
        n := uint64(0)
        for i = 0; i < a.dp && i < a.nd; i++ {
                n = n*10 + uint64(a.d[i]-'0')
        }
        for ; i < a.dp; i++ {
                n *= 10
        }
        if shouldRoundUp(a, a.dp) {
                n++
        }
        return n
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [strconv/] [decimal.go] - Blame information for rev 867

Line No.	Rev	Author	Line
1	747	jeremybenn	`// Copyright 2009 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			`// Multiprecision decimal numbers.`
6			`// For floating-point formatting only; not general purpose.`
7			`// Only operations are assign and (binary) left/right shift.`
8			`// Can do binary floating point in multiprecision decimal precisely`
9			`// because 2 divides 10; cannot do decimal floating point`
10			`// in multiprecision binary precisely.`
11
12			`package strconv`
13
14			`type decimal struct {`
15			`// TODO(rsc): Can make d[] a bit smaller and add`
16			`// truncated bool;`
17			`d [800]byte // digits`
18			`nd int // number of digits used`
19			`dp int // decimal point`
20			`neg bool`
21			`}`
22
23			`func (a *decimal) String() string {`
24			`n := 10 + a.nd`
25			`if a.dp > 0 {`
26			`n += a.dp`
27			`}`
28			`if a.dp < 0 {`
29			`n += -a.dp`
30			`}`
31
32			`buf := make([]byte, n)`
33			`w := 0`
34			`switch {`
35			`case a.nd == 0:`
36			`return "0"`
37
38			`case a.dp <= 0:`
39			`// zeros fill space between decimal point and digits`
40			`buf[w] = '0'`
41			`w++`
42			`buf[w] = '.'`
43			`w++`
44			`w += digitZero(buf[w : w+-a.dp])`
45			`w += copy(buf[w:], a.d[0:a.nd])`
46
47			`case a.dp < a.nd:`
48			`// decimal point in middle of digits`
49			`w += copy(buf[w:], a.d[0:a.dp])`
50			`buf[w] = '.'`
51			`w++`
52			`w += copy(buf[w:], a.d[a.dp:a.nd])`
53
54			`default:`
55			`// zeros fill space between digits and decimal point`
56			`w += copy(buf[w:], a.d[0:a.nd])`
57			`w += digitZero(buf[w : w+a.dp-a.nd])`
58			`}`
59			`return string(buf[0:w])`
60			`}`
61
62			`func digitZero(dst []byte) int {`
63			`for i := range dst {`
64			`dst[i] = '0'`
65			`}`
66			`return len(dst)`
67			`}`
68
69			`// trim trailing zeros from number.`
70			`// (They are meaningless; the decimal point is tracked`
71			`// independent of the number of digits.)`
72			`func trim(a *decimal) {`
73			`for a.nd > 0 && a.d[a.nd-1] == '0' {`
74			`a.nd--`
75			`}`
76			`if a.nd == 0 {`
77			`a.dp = 0`
78			`}`
79			`}`
80
81			`// Assign v to a.`
82			`func (a *decimal) Assign(v uint64) {`
83			`var buf [50]byte`
84
85			`// Write reversed decimal in buf.`
86			`n := 0`
87			`for v > 0 {`
88			`v1 := v / 10`
89			`v -= 10 * v1`
90			`buf[n] = byte(v + '0')`
91			`n++`
92			`v = v1`
93			`}`
94
95			`// Reverse again to produce forward decimal in a.d.`
96			`a.nd = 0`
97			`for n--; n >= 0; n-- {`
98			`a.d[a.nd] = buf[n]`
99			`a.nd++`
100			`}`
101			`a.dp = a.nd`
102			`trim(a)`
103			`}`
104
105			`// Maximum shift that we can do in one pass without overflow.`
106			`// Signed int has 31 bits, and we have to be able to accommodate 9<`
107			`const maxShift = 27`
108
109			`// Binary shift right (* 2) by k bits. k <= maxShift to avoid overflow.`
110			`func rightShift(a *decimal, k uint) {`
111			`r := 0 // read pointer`
112			`w := 0 // write pointer`
113
114			`// Pick up enough leading digits to cover first shift.`
115			`n := 0`
116			`for ; n>>k == 0; r++ {`
117			`if r >= a.nd {`
118			`if n == 0 {`
119			`// a == 0; shouldn't get here, but handle anyway.`
120			`a.nd = 0`
121			`return`
122			`}`
123			`for n>>k == 0 {`
124			`n = n * 10`
125			`r++`
126			`}`
127			`break`
128			`}`
129			`c := int(a.d[r])`
130			`n = n*10 + c - '0'`
131			`}`
132			`a.dp -= r - 1`
133
134			`// Pick up a digit, put down a digit.`
135			`for ; r < a.nd; r++ {`
136			`c := int(a.d[r])`
137			`dig := n >> k`
138			`n -= dig << k`
139			`a.d[w] = byte(dig + '0')`
140			`w++`
141			`n = n*10 + c - '0'`
142			`}`
143
144			`// Put down extra digits.`
145			`for n > 0 {`
146			`dig := n >> k`
147			`n -= dig << k`
148			`a.d[w] = byte(dig + '0')`
149			`w++`
150			`n = n * 10`
151			`}`
152
153			`a.nd = w`
154			`trim(a)`
155			`}`
156
157			`// Cheat sheet for left shift: table indexed by shift count giving`
158			`// number of new digits that will be introduced by that shift.`
159			`//`
160			`// For example, leftcheats[4] = {2, "625"}. That means that`
161			`// if we are shifting by 4 (multiplying by 16), it will add 2 digits`
162			`// when the string prefix is "625" through "999", and one fewer digit`
163			`// if the string prefix is "000" through "624".`
164			`//`
165			`// Credit for this trick goes to Ken.`
166
167			`type leftCheat struct {`
168			`delta int // number of new digits`
169			`cutoff string // minus one digit if original < a.`
170			`}`
171
172			`var leftcheats = []leftCheat{`
173			`// Leading digits of 1/2^i = 5^i.`
174			`// 5^23 is not an exact 64-bit floating point number,`
175			`// so have to use bc for the math.`
176			`/*`
177			`seq 27 \| sed 's/^/5^/' \| bc \|`
178			`awk 'BEGIN{ print "\tleftCheat{ 0, \"\" }," }`
179			`{`
180			`log2 = log(2)/log(10)`
181			`printf("\tleftCheat{ %d, \"%s\" },\t// * %d\n",`
182			`int(log2NR+1), $0, 2*NR)`
183			`}'`
184			`*/`
185			`{0, ""},`
186			`{1, "5"}, // * 2`
187			`{1, "25"}, // * 4`
188			`{1, "125"}, // * 8`
189			`{2, "625"}, // * 16`
190			`{2, "3125"}, // * 32`
191			`{2, "15625"}, // * 64`
192			`{3, "78125"}, // * 128`
193			`{3, "390625"}, // * 256`
194			`{3, "1953125"}, // * 512`
195			`{4, "9765625"}, // * 1024`
196			`{4, "48828125"}, // * 2048`
197			`{4, "244140625"}, // * 4096`
198			`{4, "1220703125"}, // * 8192`
199			`{5, "6103515625"}, // * 16384`
200			`{5, "30517578125"}, // * 32768`
201			`{5, "152587890625"}, // * 65536`
202			`{6, "762939453125"}, // * 131072`
203			`{6, "3814697265625"}, // * 262144`
204			`{6, "19073486328125"}, // * 524288`
205			`{7, "95367431640625"}, // * 1048576`
206			`{7, "476837158203125"}, // * 2097152`
207			`{7, "2384185791015625"}, // * 4194304`
208			`{7, "11920928955078125"}, // * 8388608`
209			`{8, "59604644775390625"}, // * 16777216`
210			`{8, "298023223876953125"}, // * 33554432`
211			`{8, "1490116119384765625"}, // * 67108864`
212			`{9, "7450580596923828125"}, // * 134217728`
213			`}`
214
215			`// Is the leading prefix of b lexicographically less than s?`
216			`func prefixIsLessThan(b []byte, s string) bool {`
217			`for i := 0; i < len(s); i++ {`
218			`if i >= len(b) {`
219			`return true`
220			`}`
221			`if b[i] != s[i] {`
222			`return b[i] < s[i]`
223			`}`
224			`}`
225			`return false`
226			`}`
227
228			`// Binary shift left (/ 2) by k bits. k <= maxShift to avoid overflow.`
229			`func leftShift(a *decimal, k uint) {`
230			`delta := leftcheats[k].delta`
231			`if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) {`
232			`delta--`
233			`}`
234
235			`r := a.nd // read index`
236			`w := a.nd + delta // write index`
237			`n := 0`
238
239			`// Pick up a digit, put down a digit.`
240			`for r--; r >= 0; r-- {`
241			`n += (int(a.d[r]) - '0') << k`
242			`quo := n / 10`
243			`rem := n - 10*quo`
244			`w--`
245			`a.d[w] = byte(rem + '0')`
246			`n = quo`
247			`}`
248
249			`// Put down extra digits.`
250			`for n > 0 {`
251			`quo := n / 10`
252			`rem := n - 10*quo`
253			`w--`
254			`a.d[w] = byte(rem + '0')`
255			`n = quo`
256			`}`
257
258			`a.nd += delta`
259			`a.dp += delta`
260			`trim(a)`
261			`}`
262
263			`// Binary shift left (k > 0) or right (k < 0).`
264			`func (a *decimal) Shift(k int) {`
265			`switch {`
266			`case a.nd == 0:`
267			`// nothing to do: a == 0`
268			`case k > 0:`
269			`for k > maxShift {`
270			`leftShift(a, maxShift)`
271			`k -= maxShift`
272			`}`
273			`leftShift(a, uint(k))`
274			`case k < 0:`
275			`for k < -maxShift {`
276			`rightShift(a, maxShift)`
277			`k += maxShift`
278			`}`
279			`rightShift(a, uint(-k))`
280			`}`
281			`}`
282
283			`// If we chop a at nd digits, should we round up?`
284			`func shouldRoundUp(a *decimal, nd int) bool {`
285			`if nd < 0 \|\| nd >= a.nd {`
286			`return false`
287			`}`
288			`if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even`
289			`return nd > 0 && (a.d[nd-1]-'0')%2 != 0`
290			`}`
291			`// not halfway - digit tells all`
292			`return a.d[nd] >= '5'`
293			`}`
294
295			`// Round a to nd digits (or fewer).`
296			`// Returns receiver for convenience.`
297			`// If nd is zero, it means we're rounding`
298			`// just to the left of the digits, as in`
299			`// 0.09 -> 0.1.`
300			`func (a *decimal) Round(nd int) {`
301			`if nd < 0 \|\| nd >= a.nd {`
302			`return`
303			`}`
304			`if shouldRoundUp(a, nd) {`
305			`a.RoundUp(nd)`
306			`} else {`
307			`a.RoundDown(nd)`
308			`}`
309			`}`
310
311			`// Round a down to nd digits (or fewer).`
312			`// Returns receiver for convenience.`
313			`func (a *decimal) RoundDown(nd int) {`
314			`if nd < 0 \|\| nd >= a.nd {`
315			`return`
316			`}`
317			`a.nd = nd`
318			`trim(a)`
319			`}`
320
321			`// Round a up to nd digits (or fewer).`
322			`// Returns receiver for convenience.`
323			`func (a *decimal) RoundUp(nd int) {`
324			`if nd < 0 \|\| nd >= a.nd {`
325			`return`
326			`}`
327
328			`// round up`
329			`for i := nd - 1; i >= 0; i-- {`
330			`c := a.d[i]`
331			`if c < '9' { // can stop after this digit`
332			`a.d[i]++`
333			`a.nd = i + 1`
334			`return`
335			`}`
336			`}`
337
338			`// Number is all 9s.`
339			`// Change to single 1 with adjusted decimal point.`
340			`a.d[0] = '1'`
341			`a.nd = 1`
342			`a.dp++`
343			`}`
344
345			`// Extract integer part, rounded appropriately.`
346			`// No guarantees about overflow.`
347			`func (a *decimal) RoundedInteger() uint64 {`
348			`if a.dp > 20 {`
349			`return 0xFFFFFFFFFFFFFFFF`
350			`}`
351			`var i int`
352			`n := uint64(0)`
353			`for i = 0; i < a.dp && i < a.nd; i++ {`
354			`n = n*10 + uint64(a.d[i]-'0')`
355			`}`
356			`for ; i < a.dp; i++ {`
357			`n *= 10`
358			`}`
359			`if shouldRoundUp(a, a.dp) {`
360			`n++`
361			`}`
362			`return n`
363			`}`