Function REDI_KB

IntegerProgramming/LLL.cc:8–50

// subroutines for the LLL-algorithms

void REDI_KB(const short& k, const short& l, BigInt** b,
             const short& number_of_vectors, const short& vector_dimension,
             BigInt** H, BigInt* d, BigInt** lambda)
// the REDI procedure for relations(...) (to compute the Kernel Basis,
// algorithm 2.7.2 in Cohen's book)
{
#ifdef GMP
  if(abs(BigInt(2)*lambda[k][l])<=d[l+1])
#else   // GMP
  if(labs(2*lambda[k][l])<=d[l+1])
    // labs is the abs-function for long ints
#endif  // GMP
    return;

#ifdef GMP
  BigInt q=(BigInt(2)*lambda[k][l]+d[l+1])/(BigInt(2)*d[l+1]);
#else   // GMP
  long q=(long int) floor(((float)(2*lambda[k][l]+d[l+1]))/(2*d[l+1]));
#endif  // GMP

  // q is the integer quotient of the division
  // (2*lambda[k][l]+d[l+1])/(2*d[l+1]).
  // Because of the rounding mode (always towards zero) of GNU C++,
  // we cannot use the built-in integer division
  // here; it causes errors when dealing with negative numbers. Therefore
  // the complicated casts: The divident is first casted to a float which
  // causes the division result to be a float. This result is explicitly
  // rounded downwards. As the floor-function returns a double (for range
  // reasons), this has to be casted to an integer again.

  for(short n=0;n<number_of_vectors;n++)
    H[k][n]-=q*H[l][n];
  // H[k]=H[k]-q*H[l]

  for(short m=0;m<vector_dimension;m++)
    b[k][m]-=q*b[l][m];
  // b[k]=b[k]-q*b[l]

  lambda[k][l]-=q*d[l+1];

  for(short i=0;i<=l-1;i++)
    lambda[k][i]-=q*lambda[l][i];
}