1// Copyright (c) 2014 The mathutil 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// Package mathutil provides utilities supplementing the standard 'math' and 6// 'math/rand' packages. 7// 8// Release history and compatibility issues 9// 10// 2017-10-14: New variadic functions for Max/Min. Ex: 11// func MaxVal(val int, vals ...int) int { 12// func MinVal(val int, vals ...int) int { 13// func MaxByteVal(val byte, vals ...byte) byte { 14// func MinByteVal(val byte, vals ...byte) byte { 15// ... 16// 17// 2016-10-10: New functions QuadPolyDiscriminant and QuadPolyFactors. 18// 19// 2013-12-13: The following functions have been REMOVED 20// 21// func Uint64ToBigInt(n uint64) *big.Int 22// func Uint64FromBigInt(n *big.Int) (uint64, bool) 23// 24// 2013-05-13: The following functions are now DEPRECATED 25// 26// func Uint64ToBigInt(n uint64) *big.Int 27// func Uint64FromBigInt(n *big.Int) (uint64, bool) 28// 29// These functions will be REMOVED with Go release 1.1+1. 30// 31// 2013-01-21: The following functions have been REMOVED 32// 33// func MaxInt() int 34// func MinInt() int 35// func MaxUint() uint 36// func UintPtrBits() int 37// 38// They are now replaced by untyped constants 39// 40// MaxInt 41// MinInt 42// MaxUint 43// UintPtrBits 44// 45// Additionally one more untyped constant was added 46// 47// IntBits 48// 49// This change breaks any existing code depending on the above removed 50// functions. They should have not been published in the first place, that was 51// unfortunate. Instead, defining such architecture and/or implementation 52// specific integer limits and bit widths as untyped constants improves 53// performance and allows for static dead code elimination if it depends on 54// these values. Thanks to minux for pointing it out in the mail list 55// (https://groups.google.com/d/msg/golang-nuts/tlPpLW6aJw8/NT3mpToH-a4J). 56// 57// 2012-12-12: The following functions will be DEPRECATED with Go release 58// 1.0.3+1 and REMOVED with Go release 1.0.3+2, b/c of 59// http://code.google.com/p/go/source/detail?r=954a79ee3ea8 60// 61// func Uint64ToBigInt(n uint64) *big.Int 62// func Uint64FromBigInt(n *big.Int) (uint64, bool) 63package mathutil 64 65import ( 66 "math" 67 "math/big" 68) 69 70// Architecture and/or implementation specific integer limits and bit widths. 71const ( 72 MaxInt = 1<<(IntBits-1) - 1 73 MinInt = -MaxInt - 1 74 MaxUint = 1<<IntBits - 1 75 IntBits = 1 << (^uint(0)>>32&1 + ^uint(0)>>16&1 + ^uint(0)>>8&1 + 3) 76 UintPtrBits = 1 << (^uintptr(0)>>32&1 + ^uintptr(0)>>16&1 + ^uintptr(0)>>8&1 + 3) 77) 78 79var ( 80 _1 = big.NewInt(1) 81 _2 = big.NewInt(2) 82) 83 84// GCDByte returns the greatest common divisor of a and b. Based on: 85// http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations 86func GCDByte(a, b byte) byte { 87 for b != 0 { 88 a, b = b, a%b 89 } 90 return a 91} 92 93// GCDUint16 returns the greatest common divisor of a and b. 94func GCDUint16(a, b uint16) uint16 { 95 for b != 0 { 96 a, b = b, a%b 97 } 98 return a 99} 100 101// GCDUint32 returns the greatest common divisor of a and b. 102func GCDUint32(a, b uint32) uint32 { 103 for b != 0 { 104 a, b = b, a%b 105 } 106 return a 107} 108 109// GCDUint64 returns the greatest common divisor of a and b. 110func GCDUint64(a, b uint64) uint64 { 111 for b != 0 { 112 a, b = b, a%b 113 } 114 return a 115} 116 117// ISqrt returns floor(sqrt(n)). Typical run time is few hundreds of ns. 118func ISqrt(n uint32) (x uint32) { 119 if n == 0 { 120 return 121 } 122 123 if n >= math.MaxUint16*math.MaxUint16 { 124 return math.MaxUint16 125 } 126 127 var px, nx uint32 128 for x = n; ; px, x = x, nx { 129 nx = (x + n/x) / 2 130 if nx == x || nx == px { 131 break 132 } 133 } 134 return 135} 136 137// SqrtUint64 returns floor(sqrt(n)). Typical run time is about 0.5 µs. 138func SqrtUint64(n uint64) (x uint64) { 139 if n == 0 { 140 return 141 } 142 143 if n >= math.MaxUint32*math.MaxUint32 { 144 return math.MaxUint32 145 } 146 147 var px, nx uint64 148 for x = n; ; px, x = x, nx { 149 nx = (x + n/x) / 2 150 if nx == x || nx == px { 151 break 152 } 153 } 154 return 155} 156 157// SqrtBig returns floor(sqrt(n)). It panics on n < 0. 158func SqrtBig(n *big.Int) (x *big.Int) { 159 switch n.Sign() { 160 case -1: 161 panic(-1) 162 case 0: 163 return big.NewInt(0) 164 } 165 166 var px, nx big.Int 167 x = big.NewInt(0) 168 x.SetBit(x, n.BitLen()/2+1, 1) 169 for { 170 nx.Rsh(nx.Add(x, nx.Div(n, x)), 1) 171 if nx.Cmp(x) == 0 || nx.Cmp(&px) == 0 { 172 break 173 } 174 px.Set(x) 175 x.Set(&nx) 176 } 177 return 178} 179 180// Log2Byte returns log base 2 of n. It's the same as index of the highest 181// bit set in n. For n == 0 -1 is returned. 182func Log2Byte(n byte) int { 183 return log2[n] 184} 185 186// Log2Uint16 returns log base 2 of n. It's the same as index of the highest 187// bit set in n. For n == 0 -1 is returned. 188func Log2Uint16(n uint16) int { 189 if b := n >> 8; b != 0 { 190 return log2[b] + 8 191 } 192 193 return log2[n] 194} 195 196// Log2Uint32 returns log base 2 of n. It's the same as index of the highest 197// bit set in n. For n == 0 -1 is returned. 198func Log2Uint32(n uint32) int { 199 if b := n >> 24; b != 0 { 200 return log2[b] + 24 201 } 202 203 if b := n >> 16; b != 0 { 204 return log2[b] + 16 205 } 206 207 if b := n >> 8; b != 0 { 208 return log2[b] + 8 209 } 210 211 return log2[n] 212} 213 214// Log2Uint64 returns log base 2 of n. It's the same as index of the highest 215// bit set in n. For n == 0 -1 is returned. 216func Log2Uint64(n uint64) int { 217 if b := n >> 56; b != 0 { 218 return log2[b] + 56 219 } 220 221 if b := n >> 48; b != 0 { 222 return log2[b] + 48 223 } 224 225 if b := n >> 40; b != 0 { 226 return log2[b] + 40 227 } 228 229 if b := n >> 32; b != 0 { 230 return log2[b] + 32 231 } 232 233 if b := n >> 24; b != 0 { 234 return log2[b] + 24 235 } 236 237 if b := n >> 16; b != 0 { 238 return log2[b] + 16 239 } 240 241 if b := n >> 8; b != 0 { 242 return log2[b] + 8 243 } 244 245 return log2[n] 246} 247 248// ModPowByte computes (b^e)%m. It panics for m == 0 || b == e == 0. 249// 250// See also: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method 251func ModPowByte(b, e, m byte) byte { 252 if b == 0 && e == 0 { 253 panic(0) 254 } 255 256 if m == 1 { 257 return 0 258 } 259 260 r := uint16(1) 261 for b, m := uint16(b), uint16(m); e > 0; b, e = b*b%m, e>>1 { 262 if e&1 == 1 { 263 r = r * b % m 264 } 265 } 266 return byte(r) 267} 268 269// ModPowUint16 computes (b^e)%m. It panics for m == 0 || b == e == 0. 270func ModPowUint16(b, e, m uint16) uint16 { 271 if b == 0 && e == 0 { 272 panic(0) 273 } 274 275 if m == 1 { 276 return 0 277 } 278 279 r := uint32(1) 280 for b, m := uint32(b), uint32(m); e > 0; b, e = b*b%m, e>>1 { 281 if e&1 == 1 { 282 r = r * b % m 283 } 284 } 285 return uint16(r) 286} 287 288// ModPowUint32 computes (b^e)%m. It panics for m == 0 || b == e == 0. 289func ModPowUint32(b, e, m uint32) uint32 { 290 if b == 0 && e == 0 { 291 panic(0) 292 } 293 294 if m == 1 { 295 return 0 296 } 297 298 r := uint64(1) 299 for b, m := uint64(b), uint64(m); e > 0; b, e = b*b%m, e>>1 { 300 if e&1 == 1 { 301 r = r * b % m 302 } 303 } 304 return uint32(r) 305} 306 307// ModPowUint64 computes (b^e)%m. It panics for m == 0 || b == e == 0. 308func ModPowUint64(b, e, m uint64) (r uint64) { 309 if b == 0 && e == 0 { 310 panic(0) 311 } 312 313 if m == 1 { 314 return 0 315 } 316 317 return modPowBigInt(big.NewInt(0).SetUint64(b), big.NewInt(0).SetUint64(e), big.NewInt(0).SetUint64(m)).Uint64() 318} 319 320func modPowBigInt(b, e, m *big.Int) (r *big.Int) { 321 r = big.NewInt(1) 322 for i, n := 0, e.BitLen(); i < n; i++ { 323 if e.Bit(i) != 0 { 324 r.Mod(r.Mul(r, b), m) 325 } 326 b.Mod(b.Mul(b, b), m) 327 } 328 return 329} 330 331// ModPowBigInt computes (b^e)%m. Returns nil for e < 0. It panics for m == 0 || b == e == 0. 332func ModPowBigInt(b, e, m *big.Int) (r *big.Int) { 333 if b.Sign() == 0 && e.Sign() == 0 { 334 panic(0) 335 } 336 337 if m.Cmp(_1) == 0 { 338 return big.NewInt(0) 339 } 340 341 if e.Sign() < 0 { 342 return 343 } 344 345 return modPowBigInt(big.NewInt(0).Set(b), big.NewInt(0).Set(e), m) 346} 347 348var uint64ToBigIntDelta big.Int 349 350func init() { 351 uint64ToBigIntDelta.SetBit(&uint64ToBigIntDelta, 63, 1) 352} 353 354var uintptrBits int 355 356func init() { 357 x := uint64(math.MaxUint64) 358 uintptrBits = BitLenUintptr(uintptr(x)) 359} 360 361// UintptrBits returns the bit width of an uintptr at the executing machine. 362func UintptrBits() int { 363 return uintptrBits 364} 365 366// AddUint128_64 returns the uint128 sum of uint64 a and b. 367func AddUint128_64(a, b uint64) (hi uint64, lo uint64) { 368 lo = a + b 369 if lo < a { 370 hi = 1 371 } 372 return hi, lo 373} 374 375// MulUint128_64 returns the uint128 bit product of uint64 a and b. 376func MulUint128_64(a, b uint64) (hi, lo uint64) { 377 /* 378 2^(2 W) ahi bhi + 2^W alo bhi + 2^W ahi blo + alo blo 379 380 FEDCBA98 76543210 FEDCBA98 76543210 381 ---- alo*blo ---- 382 ---- alo*bhi ---- 383 ---- ahi*blo ---- 384 ---- ahi*bhi ---- 385 */ 386 const w = 32 387 const m = 1<<w - 1 388 ahi, bhi, alo, blo := a>>w, b>>w, a&m, b&m 389 lo = alo * blo 390 mid1 := alo * bhi 391 mid2 := ahi * blo 392 c1, lo := AddUint128_64(lo, mid1<<w) 393 c2, lo := AddUint128_64(lo, mid2<<w) 394 _, hi = AddUint128_64(ahi*bhi, mid1>>w+mid2>>w+c1+c2) 395 return 396} 397 398// PowerizeBigInt returns (e, p) such that e is the smallest number for which p 399// == b^e is greater or equal n. For n < 0 or b < 2 (0, nil) is returned. 400// 401// NOTE: Run time for large values of n (above about 2^1e6 ~= 1e300000) can be 402// significant and/or unacceptabe. For any smaller values of n the function 403// typically performs in sub second time. For "small" values of n (cca bellow 404// 2^1e3 ~= 1e300) the same can be easily below 10 µs. 405// 406// A special (and trivial) case of b == 2 is handled separately and performs 407// much faster. 408func PowerizeBigInt(b, n *big.Int) (e uint32, p *big.Int) { 409 switch { 410 case b.Cmp(_2) < 0 || n.Sign() < 0: 411 return 412 case n.Sign() == 0 || n.Cmp(_1) == 0: 413 return 0, big.NewInt(1) 414 case b.Cmp(_2) == 0: 415 p = big.NewInt(0) 416 e = uint32(n.BitLen() - 1) 417 p.SetBit(p, int(e), 1) 418 if p.Cmp(n) < 0 { 419 p.Mul(p, _2) 420 e++ 421 } 422 return 423 } 424 425 bw := b.BitLen() 426 nw := n.BitLen() 427 p = big.NewInt(1) 428 var bb, r big.Int 429 for { 430 switch p.Cmp(n) { 431 case -1: 432 x := uint32((nw - p.BitLen()) / bw) 433 if x == 0 { 434 x = 1 435 } 436 e += x 437 switch x { 438 case 1: 439 p.Mul(p, b) 440 default: 441 r.Set(_1) 442 bb.Set(b) 443 e := x 444 for { 445 if e&1 != 0 { 446 r.Mul(&r, &bb) 447 } 448 if e >>= 1; e == 0 { 449 break 450 } 451 452 bb.Mul(&bb, &bb) 453 } 454 p.Mul(p, &r) 455 } 456 case 0, 1: 457 return 458 } 459 } 460} 461 462// PowerizeUint32BigInt returns (e, p) such that e is the smallest number for 463// which p == b^e is greater or equal n. For n < 0 or b < 2 (0, nil) is 464// returned. 465// 466// More info: see PowerizeBigInt. 467func PowerizeUint32BigInt(b uint32, n *big.Int) (e uint32, p *big.Int) { 468 switch { 469 case b < 2 || n.Sign() < 0: 470 return 471 case n.Sign() == 0 || n.Cmp(_1) == 0: 472 return 0, big.NewInt(1) 473 case b == 2: 474 p = big.NewInt(0) 475 e = uint32(n.BitLen() - 1) 476 p.SetBit(p, int(e), 1) 477 if p.Cmp(n) < 0 { 478 p.Mul(p, _2) 479 e++ 480 } 481 return 482 } 483 484 var bb big.Int 485 bb.SetInt64(int64(b)) 486 return PowerizeBigInt(&bb, n) 487} 488 489/* 490ProbablyPrimeUint32 returns true if n is prime or n is a pseudoprime to base a. 491It implements the Miller-Rabin primality test for one specific value of 'a' and 492k == 1. 493 494Wrt pseudocode shown at 495http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time 496 497 Input: n > 3, an odd integer to be tested for primality; 498 Input: k, a parameter that determines the accuracy of the test 499 Output: composite if n is composite, otherwise probably prime 500 write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1 501 LOOP: repeat k times: 502 pick a random integer a in the range [2, n − 2] 503 x ← a^d mod n 504 if x = 1 or x = n − 1 then do next LOOP 505 for r = 1 .. s − 1 506 x ← x^2 mod n 507 if x = 1 then return composite 508 if x = n − 1 then do next LOOP 509 return composite 510 return probably prime 511 512... this function behaves like passing 1 for 'k' and additionally a 513fixed/non-random 'a'. Otherwise it's the same algorithm. 514 515See also: http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html 516*/ 517func ProbablyPrimeUint32(n, a uint32) bool { 518 d, s := n-1, 0 519 for ; d&1 == 0; d, s = d>>1, s+1 { 520 } 521 x := uint64(ModPowUint32(a, d, n)) 522 if x == 1 || uint32(x) == n-1 { 523 return true 524 } 525 526 for ; s > 1; s-- { 527 if x = x * x % uint64(n); x == 1 { 528 return false 529 } 530 531 if uint32(x) == n-1 { 532 return true 533 } 534 } 535 return false 536} 537 538// ProbablyPrimeUint64_32 returns true if n is prime or n is a pseudoprime to 539// base a. It implements the Miller-Rabin primality test for one specific value 540// of 'a' and k == 1. See also ProbablyPrimeUint32. 541func ProbablyPrimeUint64_32(n uint64, a uint32) bool { 542 d, s := n-1, 0 543 for ; d&1 == 0; d, s = d>>1, s+1 { 544 } 545 x := ModPowUint64(uint64(a), d, n) 546 if x == 1 || x == n-1 { 547 return true 548 } 549 550 bx, bn := big.NewInt(0).SetUint64(x), big.NewInt(0).SetUint64(n) 551 for ; s > 1; s-- { 552 if x = bx.Mod(bx.Mul(bx, bx), bn).Uint64(); x == 1 { 553 return false 554 } 555 556 if x == n-1 { 557 return true 558 } 559 } 560 return false 561} 562 563// ProbablyPrimeBigInt_32 returns true if n is prime or n is a pseudoprime to 564// base a. It implements the Miller-Rabin primality test for one specific value 565// of 'a' and k == 1. See also ProbablyPrimeUint32. 566func ProbablyPrimeBigInt_32(n *big.Int, a uint32) bool { 567 var d big.Int 568 d.Set(n) 569 d.Sub(&d, _1) // d <- n-1 570 s := 0 571 for ; d.Bit(s) == 0; s++ { 572 } 573 nMinus1 := big.NewInt(0).Set(&d) 574 d.Rsh(&d, uint(s)) 575 576 x := ModPowBigInt(big.NewInt(int64(a)), &d, n) 577 if x.Cmp(_1) == 0 || x.Cmp(nMinus1) == 0 { 578 return true 579 } 580 581 for ; s > 1; s-- { 582 if x = x.Mod(x.Mul(x, x), n); x.Cmp(_1) == 0 { 583 return false 584 } 585 586 if x.Cmp(nMinus1) == 0 { 587 return true 588 } 589 } 590 return false 591} 592 593// ProbablyPrimeBigInt returns true if n is prime or n is a pseudoprime to base 594// a. It implements the Miller-Rabin primality test for one specific value of 595// 'a' and k == 1. See also ProbablyPrimeUint32. 596func ProbablyPrimeBigInt(n, a *big.Int) bool { 597 var d big.Int 598 d.Set(n) 599 d.Sub(&d, _1) // d <- n-1 600 s := 0 601 for ; d.Bit(s) == 0; s++ { 602 } 603 nMinus1 := big.NewInt(0).Set(&d) 604 d.Rsh(&d, uint(s)) 605 606 x := ModPowBigInt(a, &d, n) 607 if x.Cmp(_1) == 0 || x.Cmp(nMinus1) == 0 { 608 return true 609 } 610 611 for ; s > 1; s-- { 612 if x = x.Mod(x.Mul(x, x), n); x.Cmp(_1) == 0 { 613 return false 614 } 615 616 if x.Cmp(nMinus1) == 0 { 617 return true 618 } 619 } 620 return false 621} 622 623// Max returns the larger of a and b. 624func Max(a, b int) int { 625 if a > b { 626 return a 627 } 628 629 return b 630} 631 632// Min returns the smaller of a and b. 633func Min(a, b int) int { 634 if a < b { 635 return a 636 } 637 638 return b 639} 640 641// MaxVal returns the largest argument passed. 642func MaxVal(val int, vals ...int) int { 643 res := val 644 for _, v := range vals { 645 if v > res { 646 res = v 647 } 648 } 649 return res 650} 651 652// MinVal returns the smallest argument passed. 653func MinVal(val int, vals ...int) int { 654 res := val 655 for _, v := range vals { 656 if v < res { 657 res = v 658 } 659 } 660 return res 661} 662 663// Clamp returns a value restricted between lo and hi. 664func Clamp(v, lo, hi int) int { 665 return Min(Max(v, lo), hi) 666} 667 668// UMax returns the larger of a and b. 669func UMax(a, b uint) uint { 670 if a > b { 671 return a 672 } 673 674 return b 675} 676 677// UMin returns the smaller of a and b. 678func UMin(a, b uint) uint { 679 if a < b { 680 return a 681 } 682 683 return b 684} 685 686// UMaxVal returns the largest argument passed. 687func UMaxVal(val uint, vals ...uint) uint { 688 res := val 689 for _, v := range vals { 690 if v > res { 691 res = v 692 } 693 } 694 return res 695} 696 697// UMinVal returns the smallest argument passed. 698func UMinVal(val uint, vals ...uint) uint { 699 res := val 700 for _, v := range vals { 701 if v < res { 702 res = v 703 } 704 } 705 return res 706} 707 708// UClamp returns a value restricted between lo and hi. 709func UClamp(v, lo, hi uint) uint { 710 return UMin(UMax(v, lo), hi) 711} 712 713// MaxByte returns the larger of a and b. 714func MaxByte(a, b byte) byte { 715 if a > b { 716 return a 717 } 718 719 return b 720} 721 722// MinByte returns the smaller of a and b. 723func MinByte(a, b byte) byte { 724 if a < b { 725 return a 726 } 727 728 return b 729} 730 731// MaxByteVal returns the largest argument passed. 732func MaxByteVal(val byte, vals ...byte) byte { 733 res := val 734 for _, v := range vals { 735 if v > res { 736 res = v 737 } 738 } 739 return res 740} 741 742// MinByteVal returns the smallest argument passed. 743func MinByteVal(val byte, vals ...byte) byte { 744 res := val 745 for _, v := range vals { 746 if v < res { 747 res = v 748 } 749 } 750 return res 751} 752 753// ClampByte returns a value restricted between lo and hi. 754func ClampByte(v, lo, hi byte) byte { 755 return MinByte(MaxByte(v, lo), hi) 756} 757 758// MaxInt8 returns the larger of a and b. 759func MaxInt8(a, b int8) int8 { 760 if a > b { 761 return a 762 } 763 764 return b 765} 766 767// MinInt8 returns the smaller of a and b. 768func MinInt8(a, b int8) int8 { 769 if a < b { 770 return a 771 } 772 773 return b 774} 775 776// MaxInt8Val returns the largest argument passed. 777func MaxInt8Val(val int8, vals ...int8) int8 { 778 res := val 779 for _, v := range vals { 780 if v > res { 781 res = v 782 } 783 } 784 return res 785} 786 787// MinInt8Val returns the smallest argument passed. 788func MinInt8Val(val int8, vals ...int8) int8 { 789 res := val 790 for _, v := range vals { 791 if v < res { 792 res = v 793 } 794 } 795 return res 796} 797 798// ClampInt8 returns a value restricted between lo and hi. 799func ClampInt8(v, lo, hi int8) int8 { 800 return MinInt8(MaxInt8(v, lo), hi) 801} 802 803// MaxUint16 returns the larger of a and b. 804func MaxUint16(a, b uint16) uint16 { 805 if a > b { 806 return a 807 } 808 809 return b 810} 811 812// MinUint16 returns the smaller of a and b. 813func MinUint16(a, b uint16) uint16 { 814 if a < b { 815 return a 816 } 817 818 return b 819} 820 821// MaxUint16Val returns the largest argument passed. 822func MaxUint16Val(val uint16, vals ...uint16) uint16 { 823 res := val 824 for _, v := range vals { 825 if v > res { 826 res = v 827 } 828 } 829 return res 830} 831 832// MinUint16Val returns the smallest argument passed. 833func MinUint16Val(val uint16, vals ...uint16) uint16 { 834 res := val 835 for _, v := range vals { 836 if v < res { 837 res = v 838 } 839 } 840 return res 841} 842 843// ClampUint16 returns a value restricted between lo and hi. 844func ClampUint16(v, lo, hi uint16) uint16 { 845 return MinUint16(MaxUint16(v, lo), hi) 846} 847 848// MaxInt16 returns the larger of a and b. 849func MaxInt16(a, b int16) int16 { 850 if a > b { 851 return a 852 } 853 854 return b 855} 856 857// MinInt16 returns the smaller of a and b. 858func MinInt16(a, b int16) int16 { 859 if a < b { 860 return a 861 } 862 863 return b 864} 865 866// MaxInt16Val returns the largest argument passed. 867func MaxInt16Val(val int16, vals ...int16) int16 { 868 res := val 869 for _, v := range vals { 870 if v > res { 871 res = v 872 } 873 } 874 return res 875} 876 877// MinInt16Val returns the smallest argument passed. 878func MinInt16Val(val int16, vals ...int16) int16 { 879 res := val 880 for _, v := range vals { 881 if v < res { 882 res = v 883 } 884 } 885 return res 886} 887 888// ClampInt16 returns a value restricted between lo and hi. 889func ClampInt16(v, lo, hi int16) int16 { 890 return MinInt16(MaxInt16(v, lo), hi) 891} 892 893// MaxUint32 returns the larger of a and b. 894func MaxUint32(a, b uint32) uint32 { 895 if a > b { 896 return a 897 } 898 899 return b 900} 901 902// MinUint32 returns the smaller of a and b. 903func MinUint32(a, b uint32) uint32 { 904 if a < b { 905 return a 906 } 907 908 return b 909} 910 911// MaxUint32Val returns the largest argument passed. 912func MaxUint32Val(val uint32, vals ...uint32) uint32 { 913 res := val 914 for _, v := range vals { 915 if v > res { 916 res = v 917 } 918 } 919 return res 920} 921 922// MinUint32Val returns the smallest argument passed. 923func MinUint32Val(val uint32, vals ...uint32) uint32 { 924 res := val 925 for _, v := range vals { 926 if v < res { 927 res = v 928 } 929 } 930 return res 931} 932 933// ClampUint32 returns a value restricted between lo and hi. 934func ClampUint32(v, lo, hi uint32) uint32 { 935 return MinUint32(MaxUint32(v, lo), hi) 936} 937 938// MaxInt32 returns the larger of a and b. 939func MaxInt32(a, b int32) int32 { 940 if a > b { 941 return a 942 } 943 944 return b 945} 946 947// MinInt32 returns the smaller of a and b. 948func MinInt32(a, b int32) int32 { 949 if a < b { 950 return a 951 } 952 953 return b 954} 955 956// MaxInt32Val returns the largest argument passed. 957func MaxInt32Val(val int32, vals ...int32) int32 { 958 res := val 959 for _, v := range vals { 960 if v > res { 961 res = v 962 } 963 } 964 return res 965} 966 967// MinInt32Val returns the smallest argument passed. 968func MinInt32Val(val int32, vals ...int32) int32 { 969 res := val 970 for _, v := range vals { 971 if v < res { 972 res = v 973 } 974 } 975 return res 976} 977 978// ClampInt32 returns a value restricted between lo and hi. 979func ClampInt32(v, lo, hi int32) int32 { 980 return MinInt32(MaxInt32(v, lo), hi) 981} 982 983// MaxUint64 returns the larger of a and b. 984func MaxUint64(a, b uint64) uint64 { 985 if a > b { 986 return a 987 } 988 989 return b 990} 991 992// MinUint64 returns the smaller of a and b. 993func MinUint64(a, b uint64) uint64 { 994 if a < b { 995 return a 996 } 997 998 return b 999} 1000 1001// MaxUint64Val returns the largest argument passed. 1002func MaxUint64Val(val uint64, vals ...uint64) uint64 { 1003 res := val 1004 for _, v := range vals { 1005 if v > res { 1006 res = v 1007 } 1008 } 1009 return res 1010} 1011 1012// MinUint64Val returns the smallest argument passed. 1013func MinUint64Val(val uint64, vals ...uint64) uint64 { 1014 res := val 1015 for _, v := range vals { 1016 if v < res { 1017 res = v 1018 } 1019 } 1020 return res 1021} 1022 1023// ClampUint64 returns a value restricted between lo and hi. 1024func ClampUint64(v, lo, hi uint64) uint64 { 1025 return MinUint64(MaxUint64(v, lo), hi) 1026} 1027 1028// MaxInt64 returns the larger of a and b. 1029func MaxInt64(a, b int64) int64 { 1030 if a > b { 1031 return a 1032 } 1033 1034 return b 1035} 1036 1037// MinInt64 returns the smaller of a and b. 1038func MinInt64(a, b int64) int64 { 1039 if a < b { 1040 return a 1041 } 1042 1043 return b 1044} 1045 1046// MaxInt64Val returns the largest argument passed. 1047func MaxInt64Val(val int64, vals ...int64) int64 { 1048 res := val 1049 for _, v := range vals { 1050 if v > res { 1051 res = v 1052 } 1053 } 1054 return res 1055} 1056 1057// MinInt64Val returns the smallest argument passed. 1058func MinInt64Val(val int64, vals ...int64) int64 { 1059 res := val 1060 for _, v := range vals { 1061 if v < res { 1062 res = v 1063 } 1064 } 1065 return res 1066} 1067 1068// ClampInt64 returns a value restricted between lo and hi. 1069func ClampInt64(v, lo, hi int64) int64 { 1070 return MinInt64(MaxInt64(v, lo), hi) 1071} 1072 1073// ToBase produces n in base b. For example 1074// 1075// ToBase(2047, 22) -> [1, 5, 4] 1076// 1077// 1 * 22^0 1 1078// 5 * 22^1 110 1079// 4 * 22^2 1936 1080// ---- 1081// 2047 1082// 1083// ToBase panics for bases < 2. 1084func ToBase(n *big.Int, b int) []int { 1085 var nn big.Int 1086 nn.Set(n) 1087 if b < 2 { 1088 panic("invalid base") 1089 } 1090 1091 k := 1 1092 switch nn.Sign() { 1093 case -1: 1094 nn.Neg(&nn) 1095 k = -1 1096 case 0: 1097 return []int{0} 1098 } 1099 1100 bb := big.NewInt(int64(b)) 1101 var r []int 1102 rem := big.NewInt(0) 1103 for nn.Sign() != 0 { 1104 nn.QuoRem(&nn, bb, rem) 1105 r = append(r, k*int(rem.Int64())) 1106 } 1107 return r 1108} 1109