1 // Copyright 2014 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 is adapted from https://github.com/robpike/ivy/blob/master/value/loop.go. 6 7 package apd 8 9 import ( 10 "fmt" 11 "math" 12 ) 13 14 type loop struct { 15 c *Context 16 name string // The name of the function we are evaluating. 17 i uint64 // Loop count. 18 precision int32 19 maxIterations uint64 // When to give up. 20 arg *Decimal // original argument to function; only used for diagnostic. 21 prevZ Decimal // Result from the previous iteration. 22 delta Decimal // |Change| from previous iteration. 23 } 24 25 const digitsToBitsRatio = math.Ln10 / math.Ln2 26 27 // newLoop returns a new loop checker. Arguments: 28 // - name: name of the function being calculated (for error messages) 29 // - arg: argument to the function (for error messages) 30 // - precision: desired precision; the loop ends when consecutive estimates 31 // differ less than the desired precision. Note that typically 32 // the inner computations in an iteration need higher precision, 33 // so this is normally lower than the precision in the context. 34 // - maxItersPerDigit: after this many iterations per digit of precision, the 35 // loop ends in error. 36 func (c *Context) newLoop(name string, arg *Decimal, precision uint32, maxItersPerDigit int) *loop { 37 return &loop{ 38 c: c, 39 name: name, 40 arg: new(Decimal).Set(arg), 41 precision: int32(precision), 42 maxIterations: 10 + uint64(maxItersPerDigit*int(precision)), 43 } 44 } 45 46 // done reports whether the loop is done. If it does not converge 47 // after the maximum number of iterations, it returns an error. 48 func (l *loop) done(z *Decimal) (bool, error) { 49 if _, err := l.c.Sub(&l.delta, &l.prevZ, z); err != nil { 50 return false, err 51 } 52 sign := l.delta.Sign() 53 if sign == 0 { 54 return true, nil 55 } 56 if sign < 0 { 57 // Convergence can oscillate when the calculation is nearly 58 // done and we're running out of bits. This stops that. 59 // See next comment. 60 l.delta.Neg(&l.delta) 61 } 62 63 // We stop if the delta is smaller than a change of 1 in the 64 // (l.precision)-th digit of z. Examples: 65 // 66 // p = 4 67 // z = 12345.678 = 12345678 * 10^-3 68 // eps = 10.000 = 10^(-4+8-3) 69 // 70 // p = 3 71 // z = 0.001234 = 1234 * 10^-6 72 // eps = 0.00001 = 10^(-3+4-6) 73 var eps Decimal 74 eps.Coeff.Set(bigOne) 75 eps.Exponent = -l.precision + int32(z.NumDigits()) + z.Exponent 76 if l.delta.Cmp(&eps) <= 0 { 77 return true, nil 78 } 79 l.i++ 80 if l.i == l.maxIterations { 81 return false, fmt.Errorf( 82 "%s %s: did not converge after %d iterations; prev,last result %s,%s delta %s precision: %d", 83 l.name, l.arg.String(), l.maxIterations, z.String(), l.prevZ.String(), l.delta.String(), l.precision, 84 ) 85 } 86 l.prevZ.Set(z) 87 return false, nil 88 } 89