This file is indexed.

/usr/include/linbox/algorithms/diophantine-solver.inl is in liblinbox-dev 1.3.2-1.1build2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/* linbox/algorithms/diophantine-solver.inl
 * Copyright (C) 2004 David Pritchard
 *
 * Written by David Pritchard <daveagp@mit.edu>
 *
 * ========LICENCE========
 * This file is part of the library LinBox.
 *
  * LinBox is free software: you can redistribute it and/or modify
 * it under the terms of the  GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 * ========LICENCE========
 */

#ifndef __LINBOX_diophantine_solver_INL
#define __LINBOX_diophantine_solver_INL

#include "linbox/blackbox/sparse.h"
#include "linbox/blackbox/lambda-sparse.h"
#include "linbox/algorithms/rational-solver.h"
#include "linbox/algorithms/vector-fraction.h"
#include "linbox/solutions/methods.h"
#include "linbox/util/debug.h"

#include "linbox/linbox-config.h"

//#define DEBUG_DIO
//#define INFO_DIO

#define MONTE_CARLO_BOREDOM 21

namespace LinBox
{


	template<class QSolver>
	template<class IMatrix, class Vector1, class Vector2>
	SolverReturnStatus DiophantineSolver<QSolver>::solve
	(Vector1& x, Integer& den, const IMatrix& A, const Vector2& b, const int maxPrimes, const SolverLevel level)
	{

		SolverReturnStatus result = _rationalSolver.solve(x, den, A, b, false, maxPrimes, level);
		if (result == SS_INCONSISTENT && level >= SL_CERTIFIED)
			lastCertificate.copy(_rationalSolver.lastCertificate);
		return result;
	}

	template<class QSolver>
	template<class IMatrix, class Vector1, class Vector2>
	SolverReturnStatus DiophantineSolver<QSolver>::randomSolve
	(Vector1& x, Integer& den, const IMatrix& A, const Vector2& b, const int maxPrimes, const SolverLevel level)
	{

		SolverReturnStatus result = _rationalSolver.findRandomSolution(x, den, A, b, maxPrimes, level);
		if (result == SS_INCONSISTENT && level >= SL_CERTIFIED)
			lastCertificate.copy(_rationalSolver.lastCertificate);
		return result;
	}

	template<class QSolver>
	template<class IMatrix, class Vector1, class Vector2>
	SolverReturnStatus DiophantineSolver<QSolver>::diophantineSolve
	(Vector1& x, Integer& den, const IMatrix& A, const Vector2& b, const int maxPrimes, const SolverLevel level)
	{

		//here maxPrimes is only used to bound trials of initial solution
		SolverReturnStatus status;

		//this should eliminate all inconsistent systems; when level == SL_MONTECARLO maybe not.
		status = _rationalSolver.monolithicSolve(x, den, A, b, (level >= SL_LASVEGAS), true, maxPrimes, level);
		if (status != SS_OK) {
			if (status == SS_FAILED && maxPrimes > 2)
				std::cout << "ERROR, failed to find original solution and maxPrimes is not too small!" << std::endl;
			if (status == SS_INCONSISTENT && level >= SL_CERTIFIED)
				lastCertificate.copy(_rationalSolver.lastCertificate);
			return status;
		}

		VectorFraction<Ring> y(_ring,x.size());
		y. numer = x;
		y. denom = den;
		VectorFraction<Ring> y0(y);

		Integer ODB = y0.denom, n1; //ODB -- original denominator bound. equal to g(y0) from Muld+Storj.
		if (level >= SL_CERTIFIED) {
			lastCertificate.copy(_rationalSolver.lastCertificate);
			_ring.assign(n1, _rationalSolver.lastZBNumer);
		}

		Integer upperDenBound = ODB;
		Integer lowerDenBound;
		if (level >= SL_LASVEGAS)
			lowerDenBound = _rationalSolver.lastCertifiedDenFactor;
		else
			_ring.init(lowerDenBound, 1);
#ifdef DEBUG_DIO
		std::cout << "lower bound on denominator: " << lowerDenBound << std::endl;
		std::cout << "upper bound on denominator: " << upperDenBound << std::endl;
#endif
		numSolutionsNeeded     = 1;
		numFailedCallsToSolver = 0;
		numRevelantSolutions=1;
		int boredom = 0; //used in monte carlo, when we assume there's a diophantine solution
		while (! _ring.areEqual(upperDenBound, lowerDenBound)) {
			_rationalSolver.chooseNewPrime();
			status = _rationalSolver.monolithicSolve(x, den, A, b, (level >= SL_LASVEGAS), true, 1, level);
			numSolutionsNeeded++;
#ifdef DEBUG_DIO
			std::cout << '.' ;
#endif
			if (status != SS_OK) {
				numFailedCallsToSolver++;
				continue;
			}
			VectorFraction<Ring> yhat(_ring, x.size());
			yhat. numer = x;
			yhat. denom = den;
			// goodCombination first represents whether a decrease in upperDenBound is achieved
			bool goodCombination = y.boundedCombineSolution(yhat, ODB, upperDenBound);

			if (goodCombination) {
				numRevelantSolutions++;
#ifdef DEBUG_DIO
				std::cout << "new gcd(denom, y0.denom): " << upperDenBound << std::endl;
#endif
			}
			// now, goodCombination will be updated as to whether there is an increase in lowerDenBound
			if (level == SL_MONTECARLO) {
				if (goodCombination)
					boredom = 0;
				else
					boredom++;
				if (boredom > MONTE_CARLO_BOREDOM)
					break; //exit while loop
				goodCombination = false;          //since we dont update lowerDenBound, no increase happens
			}
			else if (level == SL_LASVEGAS) {
#ifdef DEBUG_DIO
				goodCombination =
				!_ring.isDivisor(lowerDenBound, _rationalSolver.lastCertifiedDenFactor);
#endif
				_ring.lcmin(lowerDenBound, _rationalSolver.lastCertifiedDenFactor);
			}
			else { //level == SL_CERTIFIED

				// 				paranoid check
				// 				if (_ring.isZero(_rationalSolver.lastCertifiedDenFactor)) {
				// 					std::cout << "ERROR: got a 0 den factor" << std::endl;
				// 					return SS_FAILED;
				// 				}

				goodCombination = lastCertificate.combineCertificate
				(_rationalSolver.lastCertificate, n1, lowerDenBound,
				 _rationalSolver.lastZBNumer,
				 _rationalSolver.lastCertifiedDenFactor);
			}
#ifdef DEBUG_DIO
			if (goodCombination)
				std::cout << "new certified denom factor: " << lowerDenBound << std::endl;
#endif
		}
#ifdef INFO_DIO
		std::cout << "number of solutions needed in total: " << numSolutionsNeeded << std::endl;
		std::cout << "number of failed calls to solver: " << numFailedCallsToSolver << std::endl;
#endif
		y.combineSolution(y0);
		//y.toFVector(x);
		x   = y.numer;
		den = y.denom;
		return SS_OK;
	}

} //end of namespace LinBox

#undef MONTE_CARLO_BOREDOM

#endif //__LINBOX_diophantine_solver_INL


// vim:sts=8:sw=8:ts=8:noet:sr:cino=>s,f0,{0,g0,(0,:0,t0,+0,=s
// Local Variables:
// mode: C++
// tab-width: 8
// indent-tabs-mode: nil
// c-basic-offset: 8
// End: