/src/functions_for_cvp.sage - Diff - CVP - Forge du Centre Blaise Pascal

Révision 62861417 src/functions_for_cvp.sage

         """
         ## A deep copy is not necessary here.
         curVect = copy(vect)
         print "Vector:", vect
         print "cvp_babai - Vector:", vect
         ## From index of last row down to 0.
         for vIndex in xrange(len(redBasis.rows())-1, -1, -1):
             curRBGSO = redBasisGso.row(vIndex)
             curVect = curVect - (round((curVect * curRBGSO)  / (curRBGSO * curRBGSO)) * redBasis.row(vIndex))
         return vect - curVect
     # End cvp_babai
+    #
     def cvp_bkz_reduce(intBasis, blockSize):
         """
         Thin and simplistic wrapper the HKZ function of the FP_LLL module.
-...
         return fplllIntBasis._sage_()
     # End cvp_hkz_reduce.
+    #
     def cvp_common_scaling_factor(floatBasis,
                                   funcVect,
                                   precision ,
                                   precisionFraction = None):
     def cvp_common_scaling_exp(precision,
                                precisionFraction = None):
         """
         Compute the common scaling factor (a power of 2).
         The exponent is made of:
            - a fraction of the precision;
            - an integer depending on the smallest norm of the vectors of the basis.
         The exponent is a fraction of the precision;
         A extra factor is computed for the vector,
         exra factors are computed for the basis vectors, all in the corresponding
         functions.
         """
         ## Set a default value for the precisionFraction to 1/2.
         if precisionFraction is None:
             precisionFraction = 1/2
         ## Compute the norms of the vectors and get the smallest one.
         #  Start with  "oo" (+Infinty)
             precisionFraction = 3/4
         """
         minBasisVectsNorm = oo
         currentNorm = 0
         for vect in floatBasis.rows():
-...
         if powerForMinNorm < 0:
             return 2^(ceil(precision*precisionFraction) - powerFromMinNorm)
         else:
             return 2^(ceil(precision*precisionFraction))
         """
         return ceil(precision * precisionFraction)
     # End cvp_common_scaling_factor.
+    #
     def cvp_extra_scaling_factor(floatBasis,
                                  funcVect,
                                  coeffsPrecList,
                                  minExponentsList):
     def cvp_extra_basis_scaling_exps(precsList, minExponentsList):
         extraScalingExpsList = []
         for minExp, prec in zip(minExponentsList, precsList):
             if minExp - prec < 0:
                 extraScalingExpsList.append(minExp - prec)
             else:
                 extraScalingExpsList.append(0)
         return extraScalingExpsList
     # End cvp_extra_basis_scaling_exps.
+    #
     def cvp_extra_function_scaling_exp(floatBasis,
                                        floatFuncVect,
                                        maxExponentsList):
         """
         Compute the extra scaling factor for each element of the basis.
         Compute the extra scaling exponent for the function vector in ordre to
         guarantee that the maximum exponent can be reached for each element of the
         basis.
         """
         ## Check arguments
         if floatBasis.nrows() == 0 or \
            floatBasis.ncols() == 0 or \
            len(funcVect) == 0:
             return 0
         ## Compute the norm of the function vector.
         funcVectNorm = funcVect.norm()
            len(floatFuncVect)      == 0:
             return 1
         if len(maxExponentsList) != floatBasis.nrows():
             return None
         ## Compute the log of the norm of the function vector.
         funcVectNormLog  = log(floatFuncVect.norm())
         ## Compute the extra scaling factor for each vector of the basis.
         ###  Pass #1 for norms ratios an minExponentsList
         scalingPowers = []
         normsRatio = 0
         for (row, maxExp) in zip(floatBasis.rows(),minExponentsList):
             normsRatio =  funcVectNorm / row.norm()
             normsRatioLog2 = normsRatio.log2().floor()
             print "Current norms ratio:", normsRatio, normsRatioLog2
             scalingPower = normsRatioLog2 + maxExp
             print "Current scaling power:", scalingPower
             scalingPowers.append(scalingPower)
         ### Pass #2 for coefficients precision.
         minScalingPower = oo
         for index in xrange(0,len(scalingPowers)):
             scalingPowers[index] -= coeffsPrecList[index]
             if scalingPowers[index] < minScalingPower:
                 minScalingPower = scalingPowers[index]
                 print "Current scaling power:", scalingPowers[index]
         if minScalingPower < 0:
             scalingFactor = 2^(-minScalingPower)
         else:
             scalingFactor = 1
         return (scalingFactor, scalingPowers)
     # End cvp_extra_scaling_factor.
         #  for norms ratios an maxExponentsList.
         extraScalingExp = 0
         for (row, maxExp) in zip(floatBasis.rows(),maxExponentsList):
             rowNormLog     = log(row.norm())
             normsRatioLog2 = floor((funcVectNormLog - rowNormLog) / log2)
             #print "Current norms ratio log2:", normsRatioLog2
             scalingExpCandidate = normsRatioLog2 - maxExp
             #print "Current scaling exponent candidate:", scalingExpCandidate
             if scalingExpCandidate < 0:
                 if -scalingExpCandidate > extraScalingExp:
                     extraScalingExp = -scalingExpCandidate
         return extraScalingExp
     # End cvp_extra_function_scaling_exp.
+    #
     def cvp_float_basis(monomialsList, pointsList, realField):
         """
-...
         return fplllIntBasis._sage_()
     # End cvp_hkz_reduce.
+    #
     def cvp_int_basis(floatBasis, commonScalingFactor):
     def cvp_int_basis(floatBasis,
                       commonScalingExp,
                       extraScalingExpsList):
         """
         From the float basis and the common scaling factor, compute the
         integral basis.
         From the float basis, the common scaling factor and the extra exponents
         compute the integral basis.
         """
         ## Checking arguments.
         if floatBasis.nrows() != len(extraScalingExpsList):
             return None
         intBasis = matrix(ZZ, floatBasis.nrows(), floatBasis.ncols())
         for rIndex in xrange(0, floatBasis.nrows()):
             for cIndex in xrange(0, floatBasis.ncols()):
                 intBasis[rIndex, cIndex] = \
                 floatBasis[rIndex, cIndex] * commonScalingFactor
                 floatBasis[rIndex, cIndex] * \
 ^(commonScalingExp + extraScalingExpsList[rIndex])
         return intBasis
     # End cvp_int_basis.
+    #
     def cvp_int_vector_for_approx(floatVect, commonScalingFactor, extraScalingFactor):
         totalScalingFactor = commonScalingFactor * extraScalingFactor
     def cvp_int_vector_for_approx(floatVect, commonScalingExp, extraScalingExp):
         totalScalingFactor = 2^(commonScalingExp + extraScalingExp)
         intVect = vector(ZZ, len(floatVect))
         for index in xrange(0, len(floatVect)):
             intVect[index] = (floatVect[index] * totalScalingFactor).round()
-...
         return monomialsList
     # End cvp_monomials_list.
+    #
     def cvp_polynomial_coeffs_from_vect(cvpVectInBasis,
                                        coeffsPrecList,
                                        minCoeffsExpList,
                                        extraFuncScalingExp):
         numElements = len(cvpVectInBasis)
         ## Arguments check.
         if numElements != len(minCoeffsExpList) or \
            numElements != len(coeffsPrecList):
             return None
         polynomialCoeffsList = []
         for index in xrange(0, numElements):
             currentCoeff = cvp_round_to_bits(cvpVectInBasis[index],
                                              coeffsPrecList[index])
             print "cvp_polynomial_coeffs - current coefficient rounded:", currentCoeff
             currentCoeff *= 2^(minCoeffsExpList[index])
             print "cvp_polynomial_coeffs - current coefficient scaled :", currentCoeff
             currentCoeff *= 2^(-coeffsPrecList[index])
             print "cvp_polynomial_coeffs - current coefficient prec corrected :", currentCoeff
             currentCoeff *= 2^(-extraFuncScalingExp)
             print "cvp_polynomial_coeffs - current coefficient extra func scaled :", currentCoeff
             polynomialCoeffsList.append(currentCoeff)
         return polynomialCoeffsList
     # En polynomial_coeffs_from_vect.
+    #
     def cvp_round_to_bits(num, numBits):
         """
         Round "num" to "numBits" bits.
         @param num    : the number to round;
         @param numBits: the number of bits to round to.
         """
         if num == 0:
             return num
         log2ofNum  = 0
         numRounded = 0
         ## Avoid conversion to floating-point if not necessary.
         try:
             log2OfNum = num.abs().log2()
         except:
             log2OfNum = RR(num).abs().log2()
         ## Works equally well for num >= 1 and num < 1.
         log2OfNum = ceil(log2OfNum)
         # print "cvp_round_to_bits - Log2OfNum:", log2OfNum
         divMult = log2OfNum - numBits
         #print "cvp_round_to_bits - DivMult:", divMult
         if divMult != 0:
             numRounded = round(num/2^divMult) * 2^divMult
         else:
             numRounded = num
         return numRounded
     # End cvp_round_to_bits
+    #
     def cvp_vector_in_basis(vect, basis):
         """
         Compute the coordinates of "vect" in "basis" by

Formats disponibles : Unified diff

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

Révision 62861417 src/functions_for_cvp.sage