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	//$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.