scan.go (1689B)
1 package bigfft 2 3 import ( 4 "math/big" 5 ) 6 7 // FromDecimalString converts the base 10 string 8 // representation of a natural (non-negative) number 9 // into a *big.Int. 10 // Its asymptotic complexity is less than quadratic. 11 func FromDecimalString(s string) *big.Int { 12 var sc scanner 13 z := new(big.Int) 14 sc.scan(z, s) 15 return z 16 } 17 18 type scanner struct { 19 // powers[i] is 10^(2^i * quadraticScanThreshold). 20 powers []*big.Int 21 } 22 23 func (s *scanner) chunkSize(size int) (int, *big.Int) { 24 if size <= quadraticScanThreshold { 25 panic("size < quadraticScanThreshold") 26 } 27 pow := uint(0) 28 for n := size; n > quadraticScanThreshold; n /= 2 { 29 pow++ 30 } 31 // threshold * 2^(pow-1) <= size < threshold * 2^pow 32 return quadraticScanThreshold << (pow - 1), s.power(pow - 1) 33 } 34 35 func (s *scanner) power(k uint) *big.Int { 36 for i := len(s.powers); i <= int(k); i++ { 37 z := new(big.Int) 38 if i == 0 { 39 if quadraticScanThreshold%14 != 0 { 40 panic("quadraticScanThreshold % 14 != 0") 41 } 42 z.Exp(big.NewInt(1e14), big.NewInt(quadraticScanThreshold/14), nil) 43 } else { 44 z.Mul(s.powers[i-1], s.powers[i-1]) 45 } 46 s.powers = append(s.powers, z) 47 } 48 return s.powers[k] 49 } 50 51 func (s *scanner) scan(z *big.Int, str string) { 52 if len(str) <= quadraticScanThreshold { 53 z.SetString(str, 10) 54 return 55 } 56 sz, pow := s.chunkSize(len(str)) 57 // Scan the left half. 58 s.scan(z, str[:len(str)-sz]) 59 // FIXME: reuse temporaries. 60 left := Mul(z, pow) 61 // Scan the right half 62 s.scan(z, str[len(str)-sz:]) 63 z.Add(z, left) 64 } 65 66 // quadraticScanThreshold is the number of digits 67 // below which big.Int.SetString is more efficient 68 // than subquadratic algorithms. 69 // 1232 digits fit in 4096 bits. 70 const quadraticScanThreshold = 1232