shared_source/c_datd/gmp_ralg.h

//$Header$
//-------------------------------------------------------------------------------------------------
//This file is part of "David T. Ashley's Shared Source Code", a set of shared components
//integrated into many of David T. Ashley's projects.
//-------------------------------------------------------------------------------------------------
//This source code and any program in which it is compiled/used is provided under the MIT License,
//reproduced below.
//-------------------------------------------------------------------------------------------------
//Permission is hereby granted, free of charge, to any person obtaining a copy of
//this software and associated documentation files(the "Software"), to deal in the
//Software without restriction, including without limitation the rights to use,
//copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the
//Software, and to permit persons to whom the Software is furnished to do so,
//subject to the following conditions :
//
//The above copyright notice and this permission notice shall be included in all
//copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
//SOFTWARE.
//-------------------------------------------------------------------------------------------------
/* GNU multiple precision rational number algorithms 
** (and some extras).
*/

#ifndef GMP_RALG_H_INCLUDED
   #define GMP_RALG_H_INCLUDED

   #ifdef MODULE_GMP_RALG
      #define DECMOD_GMP_RALG
   #else
      #define DECMOD_GMP_RALG extern
   #endif

   typedef struct 
      {
      int n;
         //The number of continued fraction partial quotients
         //and convergents included in this structure.  Indices
         //are only valid until one less than this value.
      int nallocd;
         //The number of slots allocated for partial quotients,
         //convergents, etc.  This goes in blocks of the size
         //below to avoid numerous reallocation calls.
         #define  GMP_RALG_CF_ALLOC_INCREMENT  (10)
      GMP_INTS_mpz_struct num;
         //The numerator of the rational number whose continued
         //fraction decomposition is contained in this structure.
         //It must be non-negative.  The fraction is not
         //required to be reduced.
      GMP_INTS_mpz_struct den;
         //The denominator.  It must be positive.
      GMP_INTS_mpz_struct *a;
         //Pointer to array of arbitrary integers.  Each
         //is one of the partial quotients.  This array
         //is allocated out to nallocd items but only n 
         //are used.
      GMP_INTS_mpz_struct *dividend;
         //The dividend of each division round.
      GMP_INTS_mpz_struct *divisor;
         //The divisor at each round.
      GMP_INTS_mpz_struct *remainder;
         //The remainder of each round.
      GMP_INTS_mpz_struct *p;
      GMP_INTS_mpz_struct *q;
         //The convergents.
      } GMP_RALG_cf_app_struct;


   //This structure type holds a single neighbor to a rational number we wish
   //to approximate in either the Farey series of a certain order or 
   //in a rectangular region of the integer lattice.  These neighbors
   //are manipulated in potentially large arrays.
   typedef struct {
      int index;
         //The relative index of the neighbor.  0 means that it is
         //the reduced and normalized form of the number to be
         //approximated (although at the present time the number to be
         //approximated is never included among the neighbors), 
         //"1" means nearest neighbor to the right,
         //"2" means second nearest neighbor to the right, "-1" means
         //neighbor to the left, etc.
      GMP_RATS_mpq_struct neighbor;
         //The neighbor itself, fully reduced and normalized.
      } GMP_RALG_fab_neighbor_struct;

   //This structure type holds a collection of neighbors which were
   //produced on demand to a rational number, either in a Farey series
   //or in a rectangular region of the integer lattice.  The collection
   //contains the neighbors plus a great deal of other information.
   typedef struct {
      GMP_RATS_mpq_struct rn_in;
         //The rational number which was supplied to have its neighbors
         //found.  This number is raw as supplied by the caller and 
         //not necessarily normalized.
      GMP_INTS_mpz_struct kmax_in;
         //The value of KMAX supplied.
      int hmax_supplied;
         //TRUE if the problem includes a bound on the numerator, i.e.
         //rectangular region of integer lattice rather than Farey series.
      GMP_INTS_mpz_struct hmax_in;
         //The value of HMAX if it was supplied, or zero otherwise.
      char *error;
         //NULL if no error occured in finding the neighbors.  If non-NULL,
         //points to a descriptive string explaining the error.  
         //If this error flag is set, contents of this structure
         //below this point should not be used--they are not 
         //necessarily valid.
      GMP_RATS_mpq_struct corner_point;
         //The normalized (reduced) version of the "corner point"
         //(HMAX/KMAX).  This will only be filled in if
         //HMAX is specified, or it will be 0/1 otherwise.
      GMP_RATS_mpq_struct corner_point_minus_one;
      GMP_RATS_mpq_struct corner_point_plus_one;
         //The points just before and just above the corner point
         //in the rectangular region of interest.      
      GMP_RATS_mpq_struct hmax_over_one;
         //If HMAX is supplied, the rational number which is
         //HMAX/1.  Used for comparisons if we are asked
         //to approximate a number out of range.
      GMP_RATS_mpq_struct norm_rn;
         //The normalized form of the rational number supplied.
      GMP_RATS_mpq_struct abs_norm_rn;
         //The absolute value of the normalized form of the rational 
         //number supplied.
      int rn_is_neg;
         //Set TRUE if the rational number supplied was negative.  This is 
         //not a problem, because symmetry is exploited.  For the purposes
         //of this structure, the Farey series extends on both sides of zero
         //forever, and a rectangular region of the integer lattice extends
         //from -HMAX/1 to HMAX/1.
      int n_left_in;
      int n_right_in;
         //The number of left neighbors to the rational number supplied
         //requested, and the number of right neighbors.  Note that if
         //one of the bounds of the series of interest is encountered,
         //the actual number supplied may be less.
      GMP_RALG_cf_app_struct rn_abs_cf_rep;
         //The CF representation of the absolute value of the
         //rational number supplied.  This always has to be
         //formed, because it is the only way to immediately
         //get neighbors.
      int rn_abs_cf_rep_formed;
         //Boolean flag to indicate if above has been formed.
         //This is necessary because otherwise don't have
         //any obvious clues about whether to free this.
      GMP_RALG_cf_app_struct rn_abs_recip_cf_rep;
         //The CF representation of the reciprocal of the 
         //absolute value of the rational number supplied.
         //If HMAX is supplied, this may need to be formed,
         //because it will allow us to zero in on neighbors
         //where HMAX is the dominant constraint.
      int rn_abs_recip_cf_rep_formed;
         //Boolean flag to indicate if above has been formed.
         //This is necessary because otherwise don't have
         //any obvious clues about whether to free this.
      GMP_RALG_cf_app_struct corner_point_cf_rep;
         //The CF representation of the corner point.  This is
         //necessary to find the predecessor to the corner point 
         //in F_KMAX.  This will only be calculated if HMAX 
         //is specified.
      int corner_point_cf_rep_formed;
         //Boolean flag to indicate if above has been formed.
         //This is necessary because otherwise don't have
         //any obvious clues about whether to free this.
      GMP_RALG_cf_app_struct corner_point_recip_cf_rep;
         //The CF representation of the reciprocal of the
         //corner point.  This is necessary to find the 
         //successor to the corner point along the HMAX constaint
         //in the rectangular region of the integer lattice.
         //This will only be calculated if HMAX is specified.
      int corner_point_recip_cf_rep_formed;
         //Boolean flag to indicate if above has been formed.
         //This is necessary because otherwise don't have
         //any obvious clues about whether to free this.
      int equality;
         //TRUE if the number supplied was already in the series of interest,
         //or FALSE otherwise.      
      int n_left_out;
      int n_right_out;
         //The actual number of neighbors supplied.  These may be less
         //than the number requested only if a boundary of the series of interest
         //was encountered.
      GMP_RALG_fab_neighbor_struct *lefts;
      GMP_RALG_fab_neighbor_struct *rights;
         //Arrays of neighbors in the series of interest.  These are
         //only stuffed as indicated by "n_left_out" and "n_right_out"--anything
         //else will hit on dynamic memory that is not initialized.  The
         //left array begins -1 and proceeds leftward through increasingly 
         //negative indices.  The right begins with 1 and 
         //proceeds through increasingly positive indices.  Each neighbor is 
         //irreducible and normalized.  The rational number to be approximated
         //is NEVER included among the neighbors.
      } GMP_RALG_fab_neighbor_collection_struct;

   /******************************************************************/
   /***  INITIALIZATION AND DESTRUCTION FUNCTIONS  *******************/
   /******************************************************************/
   //Decomposes a rational number into its partial quotients
   //and convergents.  This initializes the "decomp" structure
   //by allocating space, etc.  The numerator must be non-negative
   //and the denominator must be positive, or else there will be
   //a failure.  To make the interface simpler, the destruction
   //call must ALWAYS be made, even in the event of a failure.
   //If a failure occurs, the rational number will be decomposed
   //as if it were 0/1.  This means that if the failure flag
   //is missed, it will still seem to be a valid rational number.
   //It is not required that the rational number be reduced.
   //The two integers passed are not changed at all, but they
   //are copied into the decomp structure without modification.
   //After this operation, the destruction call must be made.
   DECMOD_GMP_RALG void GMP_RALG_cfdecomp_init(
            GMP_RALG_cf_app_struct *decomp,
            int                    *failure,
            GMP_INTS_mpz_struct    *num,
            GMP_INTS_mpz_struct    *den);
   //Destroys all the the data allocated.
   DECMOD_GMP_RALG void GMP_RALG_cfdecomp_destroy(
            GMP_RALG_cf_app_struct *decomp
            );

   /******************************************************************/
   /***  INITIALIZATION AND DESTRUCTION FUNCTIONS  *******************/
   /******************************************************************/
   //Prints out a continued fraction decomposition.  The banner parameter
   //may be NULL, which indicates no banner.  nf flags whether to
   //print with "no format", i.e. unformatted strings, separated by
   //newlines.  dap indicates whether to include decimal approximation
   //information.  The dap_denominator only needs to be non-NULL if
   //"dap" is selected.
   DECMOD_GMP_RALG
   void GMP_RALG_cfdecomp_emit(
                               FILE                   *s,
                               char                   *banner,
                               GMP_RALG_cf_app_struct *decomp,
                               int                    nf,
                               int                    dap,
                               const GMP_INTS_mpz_struct    *dap_denominator);

   /******************************************************************/
   /***  FAREY SERIES PREDECESSOR AND SUCCESSOR FUNCTIONS  ***********/
   /******************************************************************/
   //The two functions below compute Farey predecessors and 
   //successors.  These are straight sequences of arithmetic
   //operations--no checking for overflow is done.  The behavior
   //below zero will probably not be correct, so these should
   //not be used to go below 0/1 or with operands below 0/1.
   DECMOD_GMP_RALG
   void GMP_RALG_farey_predecessor(
                       GMP_RATS_mpq_struct *result,
                 const GMP_RATS_mpq_struct *plus_two,
                 const GMP_RATS_mpq_struct *plus_one,
                 const GMP_INTS_mpz_struct *N);
   DECMOD_GMP_RALG
   void GMP_RALG_farey_successor(
                       GMP_RATS_mpq_struct *result,
                 const GMP_RATS_mpq_struct *minus_two,
                 const GMP_RATS_mpq_struct *minus_one,
                 const GMP_INTS_mpz_struct *N);
   
   //Finds the enclosing Farey neighbors to an arbitrary positive,
   //zero, or negative rational number which may or may not be in
   //the Farey series of order N.
   //
   //INPUTS
   //          rn: Rational number whose neighbors to find.  MUST
   //              be normalized, meaning reduced and sign adjusted
   //              so numerator contains the sign.
   //           N: Order of series.  MUST be positive.
   //      cf_rep: The continued fraction representation of the
   //              non-negative version of the rational number 
   //              whose neighbors to find.  The rational number
   //              need not have been reduced when the continued
   //              fraction representation was formed, i.e. only
   //              partial quotients and convergents are used.
   //OUTPUTS
   //    equality: Set TRUE if the rational number is in the Farey
   //              series, or FALSE otherwise.  This affects the
   //              generation of neighbors.  If the number is
   //              already in the Farey series its other neighbor
   //              is generated, i.e. the rational number of
   //              interest is never one of the neighbors returned.
   //        left: The left neighbor.
   //       right: The right neighbor.
   DECMOD_GMP_RALG
   void GMP_RALG_enclosing_farey_neighbors(
                 const GMP_RATS_mpq_struct    *rn,
                 const GMP_INTS_mpz_struct    *N,
                 const GMP_RALG_cf_app_struct *cf_rep,
                 int                          *equality,
                       GMP_RATS_mpq_struct    *left,
                       GMP_RATS_mpq_struct    *right);

   //Provides up to 2**24 - 1 (in concept--we don't recommend this!) terms in either
   //the Farey series or in a rectangular region of the integer lattice.  The caller
   //must provide the space to be used, and must free it afterwards--this function 
   //performs no dynamic allocation.
   DECMOD_GMP_RALG
   void GMP_RALG_consecutive_fab_terms(
      const GMP_RATS_mpq_struct *rn_in,
         //The rational number whose neighbors are to be found.
      const GMP_INTS_mpz_struct *kmax,
         //Maximum denominator.
      const GMP_INTS_mpz_struct *hmax,
         //Maximum numerator, or a NULL pointer or a non-null pointer but
         //an arbitrary integer value of 0 if only the Farey series is being
         //considered.
      int n_left_in,
         //The number of left neighbors requested.  Must be non-negative.
      int n_right_in,
         //The number of right neighbors requested.  Must be non-negative.
      GMP_RALG_fab_neighbor_collection_struct *result
         //The structure containing all results.  Even if there is an error
         //condition, this must be freed when done by the caller.
      );

   //Frees the dynamic memory consumed by an earlier call to generate the
   //neighbor information.
   DECMOD_GMP_RALG
   void GMP_RALG_consecutive_fab_terms_result_free(
      GMP_RALG_fab_neighbor_collection_struct *arg
         //The structure whose members to free up.  After this call,
         //the structure must be considered invalid.
      );

   //Debugging function.  Dumps the contents of the neighbor structure to the indicated
   //stream for analysis.
   DECMOD_GMP_RALG
   void GMP_RALG_consecutive_fab_terms_result_dump(
         FILE *s,
         GMP_RALG_fab_neighbor_collection_struct *arg);

   /******************************************************************/
   /***  VERSION CONTROL REPORTING FUNCTIONS  ************************/
   /******************************************************************/
   DECMOD_GMP_RALG const char *GMP_RALG_cvcinfo(void);
   DECMOD_GMP_RALG const char *GMP_RALG_hvcinfo(void);
   #define GMP_RALG_H_VERSION ("$Header$")
#endif

//End of gmp_ralg.h.
1	dashley	71	//$Header$
2			//-------------------------------------------------------------------------------------------------
3			//This file is part of "David T. Ashley's Shared Source Code", a set of shared components
4			//integrated into many of David T. Ashley's projects.
5			//-------------------------------------------------------------------------------------------------
6			//This source code and any program in which it is compiled/used is provided under the MIT License,
7			//reproduced below.
8			//-------------------------------------------------------------------------------------------------
9			//Permission is hereby granted, free of charge, to any person obtaining a copy of
10			//this software and associated documentation files(the "Software"), to deal in the
11			//Software without restriction, including without limitation the rights to use,
12			//copy, modify, merge, publish, distribute, sublicense, and / or sell copies of the
13			//Software, and to permit persons to whom the Software is furnished to do so,
14			//subject to the following conditions :
15			//
16			//The above copyright notice and this permission notice shall be included in all
17			//copies or substantial portions of the Software.
18			//
19			//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20			//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21			//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
22			//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23			//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24			//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25			//SOFTWARE.
26			//-------------------------------------------------------------------------------------------------
27			/* GNU multiple precision rational number algorithms
28			** (and some extras).
29			*/
30
31			#ifndef GMP_RALG_H_INCLUDED
32			#define GMP_RALG_H_INCLUDED
33
34			#ifdef MODULE_GMP_RALG
35			#define DECMOD_GMP_RALG
36			#else
37			#define DECMOD_GMP_RALG extern
38			#endif
39
40			typedef struct
41			{
42			int n;
43			//The number of continued fraction partial quotients
44			//and convergents included in this structure. Indices
45			//are only valid until one less than this value.
46			int nallocd;
47			//The number of slots allocated for partial quotients,
48			//convergents, etc. This goes in blocks of the size
49			//below to avoid numerous reallocation calls.
50			#define GMP_RALG_CF_ALLOC_INCREMENT (10)
51			GMP_INTS_mpz_struct num;
52			//The numerator of the rational number whose continued
53			//fraction decomposition is contained in this structure.
54			//It must be non-negative. The fraction is not
55			//required to be reduced.
56			GMP_INTS_mpz_struct den;
57			//The denominator. It must be positive.
58			GMP_INTS_mpz_struct *a;
59			//Pointer to array of arbitrary integers. Each
60			//is one of the partial quotients. This array
61			//is allocated out to nallocd items but only n
62			//are used.
63			GMP_INTS_mpz_struct *dividend;
64			//The dividend of each division round.
65			GMP_INTS_mpz_struct *divisor;
66			//The divisor at each round.
67			GMP_INTS_mpz_struct *remainder;
68			//The remainder of each round.
69			GMP_INTS_mpz_struct *p;
70			GMP_INTS_mpz_struct *q;
71			//The convergents.
72			} GMP_RALG_cf_app_struct;
73
74
75			//This structure type holds a single neighbor to a rational number we wish
76			//to approximate in either the Farey series of a certain order or
77			//in a rectangular region of the integer lattice. These neighbors
78			//are manipulated in potentially large arrays.
79			typedef struct {
80			int index;
81			//The relative index of the neighbor. 0 means that it is
82			//the reduced and normalized form of the number to be
83			//approximated (although at the present time the number to be
84			//approximated is never included among the neighbors),
85			//"1" means nearest neighbor to the right,
86			//"2" means second nearest neighbor to the right, "-1" means
87			//neighbor to the left, etc.
88			GMP_RATS_mpq_struct neighbor;
89			//The neighbor itself, fully reduced and normalized.
90			} GMP_RALG_fab_neighbor_struct;
91
92			//This structure type holds a collection of neighbors which were
93			//produced on demand to a rational number, either in a Farey series
94			//or in a rectangular region of the integer lattice. The collection
95			//contains the neighbors plus a great deal of other information.
96			typedef struct {
97			GMP_RATS_mpq_struct rn_in;
98			//The rational number which was supplied to have its neighbors
99			//found. This number is raw as supplied by the caller and
100			//not necessarily normalized.
101			GMP_INTS_mpz_struct kmax_in;
102			//The value of KMAX supplied.
103			int hmax_supplied;
104			//TRUE if the problem includes a bound on the numerator, i.e.
105			//rectangular region of integer lattice rather than Farey series.
106			GMP_INTS_mpz_struct hmax_in;
107			//The value of HMAX if it was supplied, or zero otherwise.
108			char *error;
109			//NULL if no error occured in finding the neighbors. If non-NULL,
110			//points to a descriptive string explaining the error.
111			//If this error flag is set, contents of this structure
112			//below this point should not be used--they are not
113			//necessarily valid.
114			GMP_RATS_mpq_struct corner_point;
115			//The normalized (reduced) version of the "corner point"
116			//(HMAX/KMAX). This will only be filled in if
117			//HMAX is specified, or it will be 0/1 otherwise.
118			GMP_RATS_mpq_struct corner_point_minus_one;
119			GMP_RATS_mpq_struct corner_point_plus_one;
120			//The points just before and just above the corner point
121			//in the rectangular region of interest.
122			GMP_RATS_mpq_struct hmax_over_one;
123			//If HMAX is supplied, the rational number which is
124			//HMAX/1. Used for comparisons if we are asked
125			//to approximate a number out of range.
126			GMP_RATS_mpq_struct norm_rn;
127			//The normalized form of the rational number supplied.
128			GMP_RATS_mpq_struct abs_norm_rn;
129			//The absolute value of the normalized form of the rational
130			//number supplied.
131			int rn_is_neg;
132			//Set TRUE if the rational number supplied was negative. This is
133			//not a problem, because symmetry is exploited. For the purposes
134			//of this structure, the Farey series extends on both sides of zero
135			//forever, and a rectangular region of the integer lattice extends
136			//from -HMAX/1 to HMAX/1.
137			int n_left_in;
138			int n_right_in;
139			//The number of left neighbors to the rational number supplied
140			//requested, and the number of right neighbors. Note that if
141			//one of the bounds of the series of interest is encountered,
142			//the actual number supplied may be less.
143			GMP_RALG_cf_app_struct rn_abs_cf_rep;
144			//The CF representation of the absolute value of the
145			//rational number supplied. This always has to be
146			//formed, because it is the only way to immediately
147			//get neighbors.
148			int rn_abs_cf_rep_formed;
149			//Boolean flag to indicate if above has been formed.
150			//This is necessary because otherwise don't have
151			//any obvious clues about whether to free this.
152			GMP_RALG_cf_app_struct rn_abs_recip_cf_rep;
153			//The CF representation of the reciprocal of the
154			//absolute value of the rational number supplied.
155			//If HMAX is supplied, this may need to be formed,
156			//because it will allow us to zero in on neighbors
157			//where HMAX is the dominant constraint.
158			int rn_abs_recip_cf_rep_formed;
159			//Boolean flag to indicate if above has been formed.
160			//This is necessary because otherwise don't have
161			//any obvious clues about whether to free this.
162			GMP_RALG_cf_app_struct corner_point_cf_rep;
163			//The CF representation of the corner point. This is
164			//necessary to find the predecessor to the corner point
165			//in F_KMAX. This will only be calculated if HMAX
166			//is specified.
167			int corner_point_cf_rep_formed;
168			//Boolean flag to indicate if above has been formed.
169			//This is necessary because otherwise don't have
170			//any obvious clues about whether to free this.
171			GMP_RALG_cf_app_struct corner_point_recip_cf_rep;
172			//The CF representation of the reciprocal of the
173			//corner point. This is necessary to find the
174			//successor to the corner point along the HMAX constaint
175			//in the rectangular region of the integer lattice.
176			//This will only be calculated if HMAX is specified.
177			int corner_point_recip_cf_rep_formed;
178			//Boolean flag to indicate if above has been formed.
179			//This is necessary because otherwise don't have
180			//any obvious clues about whether to free this.
181			int equality;
182			//TRUE if the number supplied was already in the series of interest,
183			//or FALSE otherwise.
184			int n_left_out;
185			int n_right_out;
186			//The actual number of neighbors supplied. These may be less
187			//than the number requested only if a boundary of the series of interest
188			//was encountered.
189			GMP_RALG_fab_neighbor_struct *lefts;
190			GMP_RALG_fab_neighbor_struct *rights;
191			//Arrays of neighbors in the series of interest. These are
192			//only stuffed as indicated by "n_left_out" and "n_right_out"--anything
193			//else will hit on dynamic memory that is not initialized. The
194			//left array begins -1 and proceeds leftward through increasingly
195			//negative indices. The right begins with 1 and
196			//proceeds through increasingly positive indices. Each neighbor is
197			//irreducible and normalized. The rational number to be approximated
198			//is NEVER included among the neighbors.
199			} GMP_RALG_fab_neighbor_collection_struct;
200
201			/******************************************************************/
202			/* INITIALIZATION AND DESTRUCTION FUNCTIONS *****************/
203			/******************************************************************/
204			//Decomposes a rational number into its partial quotients
205			//and convergents. This initializes the "decomp" structure
206			//by allocating space, etc. The numerator must be non-negative
207			//and the denominator must be positive, or else there will be
208			//a failure. To make the interface simpler, the destruction
209			//call must ALWAYS be made, even in the event of a failure.
210			//If a failure occurs, the rational number will be decomposed
211			//as if it were 0/1. This means that if the failure flag
212			//is missed, it will still seem to be a valid rational number.
213			//It is not required that the rational number be reduced.
214			//The two integers passed are not changed at all, but they
215			//are copied into the decomp structure without modification.
216			//After this operation, the destruction call must be made.
217			DECMOD_GMP_RALG void GMP_RALG_cfdecomp_init(
218			GMP_RALG_cf_app_struct *decomp,
219			int *failure,
220			GMP_INTS_mpz_struct *num,
221			GMP_INTS_mpz_struct *den);
222			//Destroys all the the data allocated.
223			DECMOD_GMP_RALG void GMP_RALG_cfdecomp_destroy(
224			GMP_RALG_cf_app_struct *decomp
225			);
226
227			/******************************************************************/
228			/* INITIALIZATION AND DESTRUCTION FUNCTIONS *****************/
229			/******************************************************************/
230			//Prints out a continued fraction decomposition. The banner parameter
231			//may be NULL, which indicates no banner. nf flags whether to
232			//print with "no format", i.e. unformatted strings, separated by
233			//newlines. dap indicates whether to include decimal approximation
234			//information. The dap_denominator only needs to be non-NULL if
235			//"dap" is selected.
236			DECMOD_GMP_RALG
237			void GMP_RALG_cfdecomp_emit(
238			FILE *s,
239			char *banner,
240			GMP_RALG_cf_app_struct *decomp,
241			int nf,
242			int dap,
243			const GMP_INTS_mpz_struct *dap_denominator);
244
245			/******************************************************************/
246			/* FAREY SERIES PREDECESSOR AND SUCCESSOR FUNCTIONS *********/
247			/******************************************************************/
248			//The two functions below compute Farey predecessors and
249			//successors. These are straight sequences of arithmetic
250			//operations--no checking for overflow is done. The behavior
251			//below zero will probably not be correct, so these should
252			//not be used to go below 0/1 or with operands below 0/1.
253			DECMOD_GMP_RALG
254			void GMP_RALG_farey_predecessor(
255			GMP_RATS_mpq_struct *result,
256			const GMP_RATS_mpq_struct *plus_two,
257			const GMP_RATS_mpq_struct *plus_one,
258			const GMP_INTS_mpz_struct *N);
259			DECMOD_GMP_RALG
260			void GMP_RALG_farey_successor(
261			GMP_RATS_mpq_struct *result,
262			const GMP_RATS_mpq_struct *minus_two,
263			const GMP_RATS_mpq_struct *minus_one,
264			const GMP_INTS_mpz_struct *N);
265
266			//Finds the enclosing Farey neighbors to an arbitrary positive,
267			//zero, or negative rational number which may or may not be in
268			//the Farey series of order N.
269			//
270			//INPUTS
271			// rn: Rational number whose neighbors to find. MUST
272			// be normalized, meaning reduced and sign adjusted
273			// so numerator contains the sign.
274			// N: Order of series. MUST be positive.
275			// cf_rep: The continued fraction representation of the
276			// non-negative version of the rational number
277			// whose neighbors to find. The rational number
278			// need not have been reduced when the continued
279			// fraction representation was formed, i.e. only
280			// partial quotients and convergents are used.
281			//OUTPUTS
282			// equality: Set TRUE if the rational number is in the Farey
283			// series, or FALSE otherwise. This affects the
284			// generation of neighbors. If the number is
285			// already in the Farey series its other neighbor
286			// is generated, i.e. the rational number of
287			// interest is never one of the neighbors returned.
288			// left: The left neighbor.
289			// right: The right neighbor.
290			DECMOD_GMP_RALG
291			void GMP_RALG_enclosing_farey_neighbors(
292			const GMP_RATS_mpq_struct *rn,
293			const GMP_INTS_mpz_struct *N,
294			const GMP_RALG_cf_app_struct *cf_rep,
295			int *equality,
296			GMP_RATS_mpq_struct *left,
297			GMP_RATS_mpq_struct *right);
298
299			//Provides up to 2**24 - 1 (in concept--we don't recommend this!) terms in either
300			//the Farey series or in a rectangular region of the integer lattice. The caller
301			//must provide the space to be used, and must free it afterwards--this function
302			//performs no dynamic allocation.
303			DECMOD_GMP_RALG
304			void GMP_RALG_consecutive_fab_terms(
305			const GMP_RATS_mpq_struct *rn_in,
306			//The rational number whose neighbors are to be found.
307			const GMP_INTS_mpz_struct *kmax,
308			//Maximum denominator.
309			const GMP_INTS_mpz_struct *hmax,
310			//Maximum numerator, or a NULL pointer or a non-null pointer but
311			//an arbitrary integer value of 0 if only the Farey series is being
312			//considered.
313			int n_left_in,
314			//The number of left neighbors requested. Must be non-negative.
315			int n_right_in,
316			//The number of right neighbors requested. Must be non-negative.
317			GMP_RALG_fab_neighbor_collection_struct *result
318			//The structure containing all results. Even if there is an error
319			//condition, this must be freed when done by the caller.
320			);
321
322			//Frees the dynamic memory consumed by an earlier call to generate the
323			//neighbor information.
324			DECMOD_GMP_RALG
325			void GMP_RALG_consecutive_fab_terms_result_free(
326			GMP_RALG_fab_neighbor_collection_struct *arg
327			//The structure whose members to free up. After this call,
328			//the structure must be considered invalid.
329			);
330
331			//Debugging function. Dumps the contents of the neighbor structure to the indicated
332			//stream for analysis.
333			DECMOD_GMP_RALG
334			void GMP_RALG_consecutive_fab_terms_result_dump(
335			FILE *s,
336			GMP_RALG_fab_neighbor_collection_struct *arg);
337
338			/******************************************************************/
339			/* VERSION CONTROL REPORTING FUNCTIONS **********************/
340			/******************************************************************/
341			DECMOD_GMP_RALG const char *GMP_RALG_cvcinfo(void);
342			DECMOD_GMP_RALG const char *GMP_RALG_hvcinfo(void);
343			#define GMP_RALG_H_VERSION ("$Header$")
344			#endif
345
346			//End of gmp_ralg.h.