decimal.go 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500
  1. // Copyright 2017 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. //go:generate stringer -type RoundingMode
  5. package number
  6. import (
  7. "math"
  8. "strconv"
  9. )
  10. // RoundingMode determines how a number is rounded to the desired precision.
  11. type RoundingMode byte
  12. const (
  13. ToNearestEven RoundingMode = iota // towards the nearest integer, or towards an even number if equidistant.
  14. ToNearestZero // towards the nearest integer, or towards zero if equidistant.
  15. ToNearestAway // towards the nearest integer, or away from zero if equidistant.
  16. ToPositiveInf // towards infinity
  17. ToNegativeInf // towards negative infinity
  18. ToZero // towards zero
  19. AwayFromZero // away from zero
  20. numModes
  21. )
  22. const maxIntDigits = 20
  23. // A Decimal represents a floating point number in decimal format.
  24. // Digits represents a number [0, 1.0), and the absolute value represented by
  25. // Decimal is Digits * 10^Exp. Leading and trailing zeros may be omitted and Exp
  26. // may point outside a valid position in Digits.
  27. //
  28. // Examples:
  29. //
  30. // Number Decimal
  31. // 12345 Digits: [1, 2, 3, 4, 5], Exp: 5
  32. // 12.345 Digits: [1, 2, 3, 4, 5], Exp: 2
  33. // 12000 Digits: [1, 2], Exp: 5
  34. // 12000.00 Digits: [1, 2], Exp: 5
  35. // 0.00123 Digits: [1, 2, 3], Exp: -2
  36. // 0 Digits: [], Exp: 0
  37. type Decimal struct {
  38. digits
  39. buf [maxIntDigits]byte
  40. }
  41. type digits struct {
  42. Digits []byte // mantissa digits, big-endian
  43. Exp int32 // exponent
  44. Neg bool
  45. Inf bool // Takes precedence over Digits and Exp.
  46. NaN bool // Takes precedence over Inf.
  47. }
  48. // Digits represents a floating point number represented in digits of the
  49. // base in which a number is to be displayed. It is similar to Decimal, but
  50. // keeps track of trailing fraction zeros and the comma placement for
  51. // engineering notation. Digits must have at least one digit.
  52. //
  53. // Examples:
  54. //
  55. // Number Decimal
  56. // decimal
  57. // 12345 Digits: [1, 2, 3, 4, 5], Exp: 5 End: 5
  58. // 12.345 Digits: [1, 2, 3, 4, 5], Exp: 2 End: 5
  59. // 12000 Digits: [1, 2], Exp: 5 End: 5
  60. // 12000.00 Digits: [1, 2], Exp: 5 End: 7
  61. // 0.00123 Digits: [1, 2, 3], Exp: -2 End: 3
  62. // 0 Digits: [], Exp: 0 End: 1
  63. // scientific (actual exp is Exp - Comma)
  64. // 0e0 Digits: [0], Exp: 1, End: 1, Comma: 1
  65. // .0e0 Digits: [0], Exp: 0, End: 1, Comma: 0
  66. // 0.0e0 Digits: [0], Exp: 1, End: 2, Comma: 1
  67. // 1.23e4 Digits: [1, 2, 3], Exp: 5, End: 3, Comma: 1
  68. // .123e5 Digits: [1, 2, 3], Exp: 5, End: 3, Comma: 0
  69. // engineering
  70. // 12.3e3 Digits: [1, 2, 3], Exp: 5, End: 3, Comma: 2
  71. type Digits struct {
  72. digits
  73. // End indicates the end position of the number.
  74. End int32 // For decimals Exp <= End. For scientific len(Digits) <= End.
  75. // Comma is used for the comma position for scientific (always 0 or 1) and
  76. // engineering notation (always 0, 1, 2, or 3).
  77. Comma uint8
  78. // IsScientific indicates whether this number is to be rendered as a
  79. // scientific number.
  80. IsScientific bool
  81. }
  82. func (d *Digits) NumFracDigits() int {
  83. if d.Exp >= d.End {
  84. return 0
  85. }
  86. return int(d.End - d.Exp)
  87. }
  88. // normalize returns a new Decimal with leading and trailing zeros removed.
  89. func (d *Decimal) normalize() (n Decimal) {
  90. n = *d
  91. b := n.Digits
  92. // Strip leading zeros. Resulting number of digits is significant digits.
  93. for len(b) > 0 && b[0] == 0 {
  94. b = b[1:]
  95. n.Exp--
  96. }
  97. // Strip trailing zeros
  98. for len(b) > 0 && b[len(b)-1] == 0 {
  99. b = b[:len(b)-1]
  100. }
  101. if len(b) == 0 {
  102. n.Exp = 0
  103. }
  104. n.Digits = b
  105. return n
  106. }
  107. func (d *Decimal) clear() {
  108. b := d.Digits
  109. if b == nil {
  110. b = d.buf[:0]
  111. }
  112. *d = Decimal{}
  113. d.Digits = b[:0]
  114. }
  115. func (x *Decimal) String() string {
  116. if x.NaN {
  117. return "NaN"
  118. }
  119. var buf []byte
  120. if x.Neg {
  121. buf = append(buf, '-')
  122. }
  123. if x.Inf {
  124. buf = append(buf, "Inf"...)
  125. return string(buf)
  126. }
  127. switch {
  128. case len(x.Digits) == 0:
  129. buf = append(buf, '0')
  130. case x.Exp <= 0:
  131. // 0.00ddd
  132. buf = append(buf, "0."...)
  133. buf = appendZeros(buf, -int(x.Exp))
  134. buf = appendDigits(buf, x.Digits)
  135. case /* 0 < */ int(x.Exp) < len(x.Digits):
  136. // dd.ddd
  137. buf = appendDigits(buf, x.Digits[:x.Exp])
  138. buf = append(buf, '.')
  139. buf = appendDigits(buf, x.Digits[x.Exp:])
  140. default: // len(x.Digits) <= x.Exp
  141. // ddd00
  142. buf = appendDigits(buf, x.Digits)
  143. buf = appendZeros(buf, int(x.Exp)-len(x.Digits))
  144. }
  145. return string(buf)
  146. }
  147. func appendDigits(buf []byte, digits []byte) []byte {
  148. for _, c := range digits {
  149. buf = append(buf, c+'0')
  150. }
  151. return buf
  152. }
  153. // appendZeros appends n 0 digits to buf and returns buf.
  154. func appendZeros(buf []byte, n int) []byte {
  155. for ; n > 0; n-- {
  156. buf = append(buf, '0')
  157. }
  158. return buf
  159. }
  160. func (d *digits) round(mode RoundingMode, n int) {
  161. if n >= len(d.Digits) {
  162. return
  163. }
  164. // Make rounding decision: The result mantissa is truncated ("rounded down")
  165. // by default. Decide if we need to increment, or "round up", the (unsigned)
  166. // mantissa.
  167. inc := false
  168. switch mode {
  169. case ToNegativeInf:
  170. inc = d.Neg
  171. case ToPositiveInf:
  172. inc = !d.Neg
  173. case ToZero:
  174. // nothing to do
  175. case AwayFromZero:
  176. inc = true
  177. case ToNearestEven:
  178. inc = d.Digits[n] > 5 || d.Digits[n] == 5 &&
  179. (len(d.Digits) > n+1 || n == 0 || d.Digits[n-1]&1 != 0)
  180. case ToNearestAway:
  181. inc = d.Digits[n] >= 5
  182. case ToNearestZero:
  183. inc = d.Digits[n] > 5 || d.Digits[n] == 5 && len(d.Digits) > n+1
  184. default:
  185. panic("unreachable")
  186. }
  187. if inc {
  188. d.roundUp(n)
  189. } else {
  190. d.roundDown(n)
  191. }
  192. }
  193. // roundFloat rounds a floating point number.
  194. func (r RoundingMode) roundFloat(x float64) float64 {
  195. // Make rounding decision: The result mantissa is truncated ("rounded down")
  196. // by default. Decide if we need to increment, or "round up", the (unsigned)
  197. // mantissa.
  198. abs := x
  199. if x < 0 {
  200. abs = -x
  201. }
  202. i, f := math.Modf(abs)
  203. if f == 0.0 {
  204. return x
  205. }
  206. inc := false
  207. switch r {
  208. case ToNegativeInf:
  209. inc = x < 0
  210. case ToPositiveInf:
  211. inc = x >= 0
  212. case ToZero:
  213. // nothing to do
  214. case AwayFromZero:
  215. inc = true
  216. case ToNearestEven:
  217. // TODO: check overflow
  218. inc = f > 0.5 || f == 0.5 && int64(i)&1 != 0
  219. case ToNearestAway:
  220. inc = f >= 0.5
  221. case ToNearestZero:
  222. inc = f > 0.5
  223. default:
  224. panic("unreachable")
  225. }
  226. if inc {
  227. i += 1
  228. }
  229. if abs != x {
  230. i = -i
  231. }
  232. return i
  233. }
  234. func (x *digits) roundUp(n int) {
  235. if n < 0 || n >= len(x.Digits) {
  236. return // nothing to do
  237. }
  238. // find first digit < 9
  239. for n > 0 && x.Digits[n-1] >= 9 {
  240. n--
  241. }
  242. if n == 0 {
  243. // all digits are 9s => round up to 1 and update exponent
  244. x.Digits[0] = 1 // ok since len(x.Digits) > n
  245. x.Digits = x.Digits[:1]
  246. x.Exp++
  247. return
  248. }
  249. x.Digits[n-1]++
  250. x.Digits = x.Digits[:n]
  251. // x already trimmed
  252. }
  253. func (x *digits) roundDown(n int) {
  254. if n < 0 || n >= len(x.Digits) {
  255. return // nothing to do
  256. }
  257. x.Digits = x.Digits[:n]
  258. trim(x)
  259. }
  260. // trim cuts off any trailing zeros from x's mantissa;
  261. // they are meaningless for the value of x.
  262. func trim(x *digits) {
  263. i := len(x.Digits)
  264. for i > 0 && x.Digits[i-1] == 0 {
  265. i--
  266. }
  267. x.Digits = x.Digits[:i]
  268. if i == 0 {
  269. x.Exp = 0
  270. }
  271. }
  272. // A Converter converts a number into decimals according to the given rounding
  273. // criteria.
  274. type Converter interface {
  275. Convert(d *Decimal, r RoundingContext)
  276. }
  277. const (
  278. signed = true
  279. unsigned = false
  280. )
  281. // Convert converts the given number to the decimal representation using the
  282. // supplied RoundingContext.
  283. func (d *Decimal) Convert(r RoundingContext, number interface{}) {
  284. switch f := number.(type) {
  285. case Converter:
  286. d.clear()
  287. f.Convert(d, r)
  288. case float32:
  289. d.ConvertFloat(r, float64(f), 32)
  290. case float64:
  291. d.ConvertFloat(r, f, 64)
  292. case int:
  293. d.ConvertInt(r, signed, uint64(f))
  294. case int8:
  295. d.ConvertInt(r, signed, uint64(f))
  296. case int16:
  297. d.ConvertInt(r, signed, uint64(f))
  298. case int32:
  299. d.ConvertInt(r, signed, uint64(f))
  300. case int64:
  301. d.ConvertInt(r, signed, uint64(f))
  302. case uint:
  303. d.ConvertInt(r, unsigned, uint64(f))
  304. case uint8:
  305. d.ConvertInt(r, unsigned, uint64(f))
  306. case uint16:
  307. d.ConvertInt(r, unsigned, uint64(f))
  308. case uint32:
  309. d.ConvertInt(r, unsigned, uint64(f))
  310. case uint64:
  311. d.ConvertInt(r, unsigned, f)
  312. default:
  313. d.NaN = true
  314. // TODO:
  315. // case string: if produced by strconv, allows for easy arbitrary pos.
  316. // case reflect.Value:
  317. // case big.Float
  318. // case big.Int
  319. // case big.Rat?
  320. // catch underlyings using reflect or will this already be done by the
  321. // message package?
  322. }
  323. }
  324. // ConvertInt converts an integer to decimals.
  325. func (d *Decimal) ConvertInt(r RoundingContext, signed bool, x uint64) {
  326. if r.Increment > 0 {
  327. // TODO: if uint64 is too large, fall back to float64
  328. if signed {
  329. d.ConvertFloat(r, float64(int64(x)), 64)
  330. } else {
  331. d.ConvertFloat(r, float64(x), 64)
  332. }
  333. return
  334. }
  335. d.clear()
  336. if signed && int64(x) < 0 {
  337. x = uint64(-int64(x))
  338. d.Neg = true
  339. }
  340. d.fillIntDigits(x)
  341. d.Exp = int32(len(d.Digits))
  342. }
  343. // ConvertFloat converts a floating point number to decimals.
  344. func (d *Decimal) ConvertFloat(r RoundingContext, x float64, size int) {
  345. d.clear()
  346. if math.IsNaN(x) {
  347. d.NaN = true
  348. return
  349. }
  350. // Simple case: decimal notation
  351. if r.Increment > 0 {
  352. scale := int(r.IncrementScale)
  353. mult := 1.0
  354. if scale >= len(scales) {
  355. mult = math.Pow(10, float64(scale))
  356. } else {
  357. mult = scales[scale]
  358. }
  359. // We multiply x instead of dividing inc as it gives less rounding
  360. // issues.
  361. x *= mult
  362. x /= float64(r.Increment)
  363. x = r.Mode.roundFloat(x)
  364. x *= float64(r.Increment)
  365. x /= mult
  366. }
  367. abs := x
  368. if x < 0 {
  369. d.Neg = true
  370. abs = -x
  371. }
  372. if math.IsInf(abs, 1) {
  373. d.Inf = true
  374. return
  375. }
  376. // By default we get the exact decimal representation.
  377. verb := byte('g')
  378. prec := -1
  379. // As the strconv API does not return the rounding accuracy, we can only
  380. // round using ToNearestEven.
  381. if r.Mode == ToNearestEven {
  382. if n := r.RoundSignificantDigits(); n >= 0 {
  383. prec = n
  384. } else if n = r.RoundFractionDigits(); n >= 0 {
  385. prec = n
  386. verb = 'f'
  387. }
  388. } else {
  389. // TODO: At this point strconv's rounding is imprecise to the point that
  390. // it is not usable for this purpose.
  391. // See https://github.com/golang/go/issues/21714
  392. // If rounding is requested, we ask for a large number of digits and
  393. // round from there to simulate rounding only once.
  394. // Ideally we would have strconv export an AppendDigits that would take
  395. // a rounding mode and/or return an accuracy. Something like this would
  396. // work:
  397. // AppendDigits(dst []byte, x float64, base, size, prec int) (digits []byte, exp, accuracy int)
  398. hasPrec := r.RoundSignificantDigits() >= 0
  399. hasScale := r.RoundFractionDigits() >= 0
  400. if hasPrec || hasScale {
  401. // prec is the number of mantissa bits plus some extra for safety.
  402. // We need at least the number of mantissa bits as decimals to
  403. // accurately represent the floating point without rounding, as each
  404. // bit requires one more decimal to represent: 0.5, 0.25, 0.125, ...
  405. prec = 60
  406. }
  407. }
  408. b := strconv.AppendFloat(d.Digits[:0], abs, verb, prec, size)
  409. i := 0
  410. k := 0
  411. beforeDot := 1
  412. for i < len(b) {
  413. if c := b[i]; '0' <= c && c <= '9' {
  414. b[k] = c - '0'
  415. k++
  416. d.Exp += int32(beforeDot)
  417. } else if c == '.' {
  418. beforeDot = 0
  419. d.Exp = int32(k)
  420. } else {
  421. break
  422. }
  423. i++
  424. }
  425. d.Digits = b[:k]
  426. if i != len(b) {
  427. i += len("e")
  428. pSign := i
  429. exp := 0
  430. for i++; i < len(b); i++ {
  431. exp *= 10
  432. exp += int(b[i] - '0')
  433. }
  434. if b[pSign] == '-' {
  435. exp = -exp
  436. }
  437. d.Exp = int32(exp) + 1
  438. }
  439. }
  440. func (d *Decimal) fillIntDigits(x uint64) {
  441. if cap(d.Digits) < maxIntDigits {
  442. d.Digits = d.buf[:]
  443. } else {
  444. d.Digits = d.buf[:maxIntDigits]
  445. }
  446. i := 0
  447. for ; x > 0; x /= 10 {
  448. d.Digits[i] = byte(x % 10)
  449. i++
  450. }
  451. d.Digits = d.Digits[:i]
  452. for p := 0; p < i; p++ {
  453. i--
  454. d.Digits[p], d.Digits[i] = d.Digits[i], d.Digits[p]
  455. }
  456. }
  457. var scales [70]float64
  458. func init() {
  459. x := 1.0
  460. for i := range scales {
  461. scales[i] = x
  462. x *= 10
  463. }
  464. }