Safe and effective determinant evaluation

The problem of evaluating the sign of the determinant of a small matrix aries in many geometric algorithms. Given an n×n matrix A with integer entries, whose columns are all smaller than M in Euclidean norm, the algorithm given evaluates the sign of the determinant det A exactly. The algorithm requires an arithmetic precision of less than 1.5n+2lgM bits. The number of arithmetic operations needed is O(n³ )+O(n²) log OD(A)/β, where OD(A)|det A| is the product of the lengths of the columns of A, and β is the number of `extra´ bits of precision, min{lg(1/u)-1.1n-2lgn-2,lgN-lgM-1.5n-1}, where u is the roundoff error in approximate arithmetic, and N is the largest representable integer. Since OD(A)⩽Mⁿ, the algorithm requires O(n³lgM) time, and O(n³) time when β=Ω(logM)