Laboratoire de l'Informatique et du Parallélisme » Pobyso

    #print polyRingSa

degree and range, it also returns the approximation error (refered to, in the sequel, 

as the

		<span class="langElem">computedError</span> and the center of

the interval as well).

	</p>

<p>Very often, we want to solve a slightly different problem: for a given

function, degree, lower bound and approximation error (referred to,  in the 

sequel, as the

		<span class="langElem">targetError</span> ), compute the

it and the lower bound for which the approximation error stands.

	</p>

<p>The idea is to break a given initially &ldquo;large&rdquo; interval into a

<p>The most naive approach is to:</p>

  <li>give it a try with the initial data (a very probably too high upper bound

      for the given <span class="langElem">targetError</span>);</li>

error is below or equal to the expected error. But you must not decrease the

interval width too agressively:  there is no point in getting a too small 

approximation error since it multiplies the number of interval (and

maximum width (compatible with the target error).</p>

<p>We use two strategies.</p>

	<p>The first is in the inner function that computes the first approximation 

	   polynomial. If the upper bound is too high, we shrink the interval by a non

	   linear (and complex) factor computed from the ratio beetwen the obtained 

	   error and the target error.<br>The whole idea is not to end up with a too 

	   small interval.</p>

	<p>This only takes into account aspect 1</p>.   

	<p>The second strategy is in the outer function. In this function the 

	    computed intervals returned by the inner function give all correct 

	    approximation errors. The computation of  next upper bound will take into 

	    account the value of the previous interval and that of the previous 

	    computed error.</p>

	<p>If the errors ratio is lower than 2, we try the same interval length 

	   as given by the previous computation.  If larger we increase the next 

	   interval but by a small margin (log2(errorsRatio).</p>

   <p>In this case, aspects 1 and 2 are considered </p>

<p>For the moment, we do not resort to more complex forcasting techniques 

   (using the derivative of the function?). This could be an option if the 

   present strategies did not output enough performance. </p>

def spo_norm(poly, degree):

    """

    Behaves more or less (no infinity defined) as the norm for the

    univariate polynomials.

    Quoting the Sage documentation:

    Definition: For integer p, the p-norm of a polynomial is the pth root of 

    the sum of the pth powers of the absolute values of the coefficients of 

    the polynomial.

    """

    # TODO: check the arguments.

    norm = 0

    for coefficient in poly.coefficients():

        norm +=  (coefficient^degree).abs()

    return pow(norm, 1/degree)

# end spo_norm

print "sagePolynomialOperations loaded..."

        sollya_lib_clear_obj(polySo)

        sollya_lib_clear_obj(intervalCenterSo)

        shrinkFactorSa = RRR('5.0')/(maxErrorSa/approxPrecSa).log2().abs()

        #shrinkFactorSa = 1.5/(maxErrorSa/approxPrecSa)

        #errorRatioSa = approxPrecSa/maxErrorSa

        if shrinkFactorSa > intervalShrinkConstFactorSa:

            actualShrinkFactorSa = intervalShrinkConstFactorSa

            #print "Fixed"

            actualShrinkFactorSa = shrinkFactorSa

            #print "Computed",shrinkFactorSa,maxErrorSa

            #print shrinkFactorSa, maxErrorSa

        currentUpperBoundSa = currentLowerBoundSa + \

                                   actualShrinkFactorSa

# End slz_compute_polynomial_and_interval

    # Compute the next upper bound.

    # If the error of approximation is more than half of the target,

    # use the same interval.

    # If it is less, increase it a bit.

    errorSa = pobyso_get_constant_as_rn_with_rf_so_sa(maxErrorSo)

    currentErrorRatio = approxPrecSa / errorSa

    currentScaledUpperBoundSa = boundsSa.endpoints()[1]

    if currentErrorRatio  < 2 :

        currentScaledUpperBoundSa += \

            (boundsSa.endpoints()[1] - boundsSa.endpoints()[0])

    else:

        currentScaledUpperBoundSa += \

            (boundsSa.endpoints()[1] - boundsSa.endpoints()[0]) \

                         * currentErrorRatio.log2() * 2

    if currentScaledUpperBoundSa > scaledUpperBoundSa:

        currentScaledUpperBoundSa = scaledUpperBoundSa

                                            currentScaledUpperBoundSa, 

                                            approxPrecSa, 

        # Compute the next upper bound.

        # If the error of approximation is more than half of the target,

        # use the same interval.

        # If it is less, increase it a bit.

        errorSa = pobyso_get_constant_as_rn_with_rf_so_sa(maxErrorSo)

        currentErrorRatio = approxPrecSa / errorSa

        if currentErrorRatio  < RR('1.5') :

            currentScaledUpperBoundSa = \

                            boundsSa.endpoints()[1] + \

                            (boundsSa.endpoints()[1] - boundsSa.endpoints()[0])

        elif currentErrorRatio < 2:

            currentScaledUpperBoundSa = \

                            boundsSa.endpoints()[1] + \

                            (boundsSa.endpoints()[1] - boundsSa.endpoints()[0]) \

                             * currentErrorRatio.log2()

        else:

            currentScaledUpperBoundSa = \

                            boundsSa.endpoints()[1] + \

                            (boundsSa.endpoints()[1] - boundsSa.endpoints()[0]) \

                             * currentErrorRatio.log2() * 2

        if currentScaledUpperBoundSa > scaledUpperBoundSa:

            currentScaledUpperBoundSa = scaledUpperBoundSa

# End slz_get_intervals_and_polynomials

# End sro_numerators

print "sageRationalOperations loaded..."