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

"""

@file functions_for_cvp.sage

@package functions_for_cvp

@author S.T.

    @param: lowerBound (of the target interval)

    @param: upperBound (of the target interval)

def cvp_candidate_vectors(intVect, diffsList):

    """

    Computes a list of best approximation vectors based on the CVP

    computed vector using the differences between this vector and the 

    target function vector.

    @param intVect the vector from which candidates are built

    @param diffsList the list of the values that will be appended to the

           initial vector to form the candidates

    @return A matrix made of candidates rows or None if there is some invalid

            argument.

    @par How it works

    The idea is to create all the possible vectors based on the computed CVP

    vector and its differences to the target. Those are collected in 

    diffsList.@n

    From the vector we create all the possible combinations between the original

    value and the differences in diffsList. Some of those can be equal to 0.

    They are not taken into account. If nonZeroDiffsCount is the number of 

    diffsList element different from 0, there are 2^nonZeroDiffsCount 

    possible variants.@n

    To compute those, we build a 2^nonZeroDiffsCount rows matrix. For the

    first element in the vector corresponding to a non-zero in diffsList, we

    switch values in the matrix at every row.@n

    For the second such element (non-zero corresponding diffsList element), we

    switch values in the matrix at every second row for a string of two similar 

    values.@n

    For the third such element, change happens at every fourth row, for a 

    string of four similar values. And so on...

    @par Example

    @verbatim

    vect        =  [10, 20, 30, 40, 50]

    diffsList   =  [ 1,  0, -1,  0,  1]

    vectCandMat = [[10, 20, 30, 40, 50],

                   [11, 20, 30, 40, 50],

                   [10, 20, 29, 40, 50],

                   [11, 20, 29, 40, 50],

                   [10, 20, 30, 40, 51],

                   [11, 20, 30, 40, 51],

                   [10, 20, 29, 40, 51],

                   [11, 20, 29, 40, 51]]

    @endverbatim

"""

    ## Arguments check.

    vectLen = len(intVect)

    if vectLen != len(diffsList):

        return None

    #

    ## Compute the number of diffsList elements different from 0.

    nonZeroDiffsCount = 0

    for elem in diffsList:

        if elem != 0:

            nonZeroDiffsCount += 1

    if nonZeroDiffsCount == 0:

        return matrix(ZZ, 0, vectLen)

    numRows = 2^nonZeroDiffsCount

    vectMat = matrix(ZZ, numRows, vectLen)

    for rowIndex in xrange(0,numRows):

        effColIndex = 0

        for colIndex in xrange(0,vectLen):

            vectMat[rowIndex, colIndex] = intVect[colIndex]

            if diffsList[colIndex] != 0:

                if (rowIndex % 2^(effColIndex + 1)) >= 2^effColIndex:

                    vectMat[rowIndex, colIndex] += diffsList[colIndex]

                effColIndex += 1

    return vectMat

# End cvp_candidate_vectors

#

    """

    Computes the exponents for the extra scaling down of the elements of the

    basis.

    This extra scaling down is necessary when there are elements of the 

    basis that have negative exponents.

    """

                                    coeffsPrecList, 

                                    minCoeffsExpList,

                                    extraFuncScalingExp):

    """

    Computes polynomial coefficients out of the elements of the CVP vector.

    @todo

    Rewrite the code with a single exponentiation, at the very end.

    """

def cvp_remez_all_poly_error_func_maxis(funct, 

    ## If no realField argument is given try to retrieve it from the 

    #  bounds. If impossible (e.g. rational bound), fall back on RR. 

    if realField is None:

        try:

            ### Force failure if parent does not have prec() member.

            lowerBound.parent().prec()

            ### If no exception is thrown, set realField.

            realField = lowerBound.parent()

        except:

            realField = RR

    #print "Real field:", realField

    funcSa         = func

    funcAsStringSa = func._assume_str().replace("_SAGE_VAR_","",100)

    print "Function as a string:", funcAsStringSa

    ## Create the Sollya version of the function and compute the

    #  Remez approximant

    funcSo  = pobyso_parse_string(funcAsStringSa)

    pStarSo = pobyso_remez_canonical_sa_so(funcAsStringSa, 

                                           maxDegree, 

                                           lowerBound,

                                           upperBound)

    ## Compute the error function and its derivative

    ### First create the error function with copies since they are needed later.

    errorFuncSo = sollya_lib_build_function_sub(sollya_lib_copy_obj(pStarSo), 

                                                sollya_lib_copy_obj(funcSo))

    intervalSo = pobyso_range_from_bounds_sa_so(lowerBound, upperBound)

    diffErrorFuncSo = pobyso_diff_so_so(errorFuncSo)

    pobyso_clear_obj(errorFuncSo)

    ## Compute the zeros of the derivative.

    errorFuncZerosSo = pobyso_dirty_find_zeros_so_so(diffErrorFuncSo, intervalSo)

    pobyso_clear_obj(diffErrorFuncSo)

    errorFuncZerosSa = pobyso_float_list_so_sa(errorFuncZerosSo)

    pobyso_clear_obj(errorFuncZerosSo)

    ## Compute the truncated Remez polynomial and the error function.

    truncFormatListSo = pobyso_build_list_of_ints_sa_so(*precsList)

    pTruncSo = pobyso_round_coefficients_so_so(pStarSo, truncFormatListSo)

    pobyso_clear_obj(pStarSo)

    ### Compute the error function. This time we consume both the function

    #   and the polynomial.

    errorFuncSo = sollya_lib_build_function_sub(pTruncSo, funcSo)

    ## Compute the derivative.

    diffErrorFuncSo = pobyso_diff_so_so(errorFuncSo)

    pobyso_clear_obj(errorFuncSo)

    ## Compute the zeros of the derivative.

    errorFuncZerosSo = pobyso_dirty_find_zeros_so_so(diffErrorFuncSo, intervalSo)

    pobyso_clear_obj(diffErrorFuncSo)

    pobyso_clear_obj(intervalSo)

    errorFuncTruncZerosSa = pobyso_float_list_so_sa(errorFuncZerosSo)

    pobyso_clear_obj(errorFuncZerosSo)

    errorFuncZerosSa += errorFuncTruncZerosSa

    errorFuncZerosSa.sort()

    ## If required, convert the numbers to rational numbers.

    if not contFracMaxErr is None:

        for index in xrange(0, len(errorFuncZerosSa)):

            errorFuncZerosSa[index] = \

                errorFuncZerosSa[index].nearby_rational(contFracMaxErr)

    return errorFuncZerosSa

# End cvp_remez_all_poly_error_func_maxis.

    function over the interval.

    #pobyso_autoprint(truncFormatListSo)

    #pobyso_autoprint(errorFuncZerosSo)

    @param vect  the vector we want to compute the coordinates of

    @param basis the basis we want to compute the coordinates in

    ## Solve the equations system. The solution dictionary is needed

    ## This code is deactivated: did not solve the problem.

    """

    if len(solutions) == 0:

        print "Trying Maxima to_poly_sove."

        solutions = solve(equationsList,varsList, solution_dict=True, to_poly_solve = 'force')

    """

    #   Here, there is only one (or none). For each solution, each