1 /* 2 Name: imrat.h 3 Purpose: Arbitrary precision rational arithmetic routines. 4 Author: M. J. Fromberger 5 6 Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved. 7 8 Permission is hereby granted, free of charge, to any person obtaining a copy 9 of this software and associated documentation files (the "Software"), to deal 10 in the Software without restriction, including without limitation the rights 11 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 12 copies of the Software, and to permit persons to whom the Software is 13 furnished to do so, subject to the following conditions: 14 15 The above copyright notice and this permission notice shall be included in 16 all copies or substantial portions of the Software. 17 18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 21 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 22 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 23 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 24 SOFTWARE. 25 */ 26 27 #ifndef IMRAT_H_ 28 #define IMRAT_H_ 29 30 #include <stdbool.h> 31 32 #include "imath.h" 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 typedef struct { 39 mpz_t num; /* Numerator */ 40 mpz_t den; /* Denominator, <> 0 */ 41 } mpq_t, *mp_rat; 42 43 /* Return a pointer to the numerator. */ 44 static inline mp_int MP_NUMER_P(mp_rat Q) { return &(Q->num); } 45 46 /* Return a pointer to the denominator. */ 47 static inline mp_int MP_DENOM_P(mp_rat Q) { return &(Q->den); } 48 49 /* Rounding constants */ 50 typedef enum { 51 MP_ROUND_DOWN, 52 MP_ROUND_HALF_UP, 53 MP_ROUND_UP, 54 MP_ROUND_HALF_DOWN 55 } mp_round_mode; 56 57 /** Initializes `r` with 1-digit precision and sets it to zero. This function 58 cannot fail unless `r` is NULL. */ 59 mp_result mp_rat_init(mp_rat r); 60 61 /** Allocates a fresh zero-valued `mpq_t` on the heap, returning NULL in case 62 of error. The only possible error is out-of-memory. */ 63 mp_rat mp_rat_alloc(void); 64 65 /** Reduces `r` in-place to lowest terms and canonical form. 66 67 Zero is represented as 0/1, one as 1/1, and signs are adjusted so that the 68 sign of the value is carried by the numerator. */ 69 mp_result mp_rat_reduce(mp_rat r); 70 71 /** Initializes `r` with at least `n_prec` digits of storage for the numerator 72 and `d_prec` digits of storage for the denominator, and value zero. 73 74 If either precision is zero, the default precision is used, rounded up to 75 the nearest word size. */ 76 mp_result mp_rat_init_size(mp_rat r, mp_size n_prec, mp_size d_prec); 77 78 /** Initializes `r` to be a copy of an already-initialized value in `old`. The 79 new copy does not share storage with the original. */ 80 mp_result mp_rat_init_copy(mp_rat r, mp_rat old); 81 82 /** Sets the value of `r` to the ratio of signed `numer` to signed `denom`. It 83 returns `MP_UNDEF` if `denom` is zero. */ 84 mp_result mp_rat_set_value(mp_rat r, mp_small numer, mp_small denom); 85 86 /** Sets the value of `r` to the ratio of unsigned `numer` to unsigned 87 `denom`. It returns `MP_UNDEF` if `denom` is zero. */ 88 mp_result mp_rat_set_uvalue(mp_rat r, mp_usmall numer, mp_usmall denom); 89 90 /** Releases the storage used by `r`. */ 91 void mp_rat_clear(mp_rat r); 92 93 /** Releases the storage used by `r` and also `r` itself. 94 This should only be used for `r` allocated by `mp_rat_alloc()`. */ 95 void mp_rat_free(mp_rat r); 96 97 /** Sets `z` to a copy of the numerator of `r`. */ 98 mp_result mp_rat_numer(mp_rat r, mp_int z); 99 100 /** Returns a pointer to the numerator of `r`. */ 101 mp_int mp_rat_numer_ref(mp_rat r); 102 103 /** Sets `z` to a copy of the denominator of `r`. */ 104 mp_result mp_rat_denom(mp_rat r, mp_int z); 105 106 /** Returns a pointer to the denominator of `r`. */ 107 mp_int mp_rat_denom_ref(mp_rat r); 108 109 /** Reports the sign of `r`. */ 110 mp_sign mp_rat_sign(mp_rat r); 111 112 /** Sets `c` to a copy of the value of `a`. No new memory is allocated unless a 113 term of `a` has more significant digits than the corresponding term of `c` 114 has allocated. */ 115 mp_result mp_rat_copy(mp_rat a, mp_rat c); 116 117 /** Sets `r` to zero. The allocated storage of `r` is not changed. */ 118 void mp_rat_zero(mp_rat r); 119 120 /** Sets `c` to the absolute value of `a`. */ 121 mp_result mp_rat_abs(mp_rat a, mp_rat c); 122 123 /** Sets `c` to the absolute value of `a`. */ 124 mp_result mp_rat_neg(mp_rat a, mp_rat c); 125 126 /** Sets `c` to the reciprocal of `a` if the reciprocal is defined. 127 It returns `MP_UNDEF` if `a` is zero. */ 128 mp_result mp_rat_recip(mp_rat a, mp_rat c); 129 130 /** Sets `c` to the sum of `a` and `b`. */ 131 mp_result mp_rat_add(mp_rat a, mp_rat b, mp_rat c); 132 133 /** Sets `c` to the difference of `a` less `b`. */ 134 mp_result mp_rat_sub(mp_rat a, mp_rat b, mp_rat c); 135 136 /** Sets `c` to the product of `a` and `b`. */ 137 mp_result mp_rat_mul(mp_rat a, mp_rat b, mp_rat c); 138 139 /** Sets `c` to the ratio `a / b` if that ratio is defined. 140 It returns `MP_UNDEF` if `b` is zero. */ 141 mp_result mp_rat_div(mp_rat a, mp_rat b, mp_rat c); 142 143 /** Sets `c` to the sum of `a` and integer `b`. */ 144 mp_result mp_rat_add_int(mp_rat a, mp_int b, mp_rat c); 145 146 /** Sets `c` to the difference of `a` less integer `b`. */ 147 mp_result mp_rat_sub_int(mp_rat a, mp_int b, mp_rat c); 148 149 /** Sets `c` to the product of `a` and integer `b`. */ 150 mp_result mp_rat_mul_int(mp_rat a, mp_int b, mp_rat c); 151 152 /** Sets `c` to the ratio `a / b` if that ratio is defined. 153 It returns `MP_UNDEF` if `b` is zero. */ 154 mp_result mp_rat_div_int(mp_rat a, mp_int b, mp_rat c); 155 156 /** Sets `c` to the value of `a` raised to the `b` power. 157 It returns `MP_RANGE` if `b < 0`. */ 158 mp_result mp_rat_expt(mp_rat a, mp_small b, mp_rat c); 159 160 /** Returns the comparator of `a` and `b`. */ 161 int mp_rat_compare(mp_rat a, mp_rat b); 162 163 /** Returns the comparator of the magnitudes of `a` and `b`, disregarding their 164 signs. Neither `a` nor `b` is modified by the comparison. */ 165 int mp_rat_compare_unsigned(mp_rat a, mp_rat b); 166 167 /** Returns the comparator of `r` and zero. */ 168 int mp_rat_compare_zero(mp_rat r); 169 170 /** Returns the comparator of `r` and the signed ratio `n / d`. 171 It returns `MP_UNDEF` if `d` is zero. */ 172 int mp_rat_compare_value(mp_rat r, mp_small n, mp_small d); 173 174 /** Reports whether `r` is an integer, having canonical denominator 1. */ 175 bool mp_rat_is_integer(mp_rat r); 176 177 /** Reports whether the numerator and denominator of `r` can be represented as 178 small signed integers, and if so stores the corresponding values to `num` 179 and `den`. It returns `MP_RANGE` if either cannot be so represented. */ 180 mp_result mp_rat_to_ints(mp_rat r, mp_small *num, mp_small *den); 181 182 /** Converts `r` to a zero-terminated string of the format `"n/d"` with `n` and 183 `d` in the specified radix and writing no more than `limit` bytes to the 184 given output buffer `str`. The output of the numerator includes a sign flag 185 if `r` is negative. Requires `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. */ 186 mp_result mp_rat_to_string(mp_rat r, mp_size radix, char *str, int limit); 187 188 /** Converts the value of `r` to a string in decimal-point notation with the 189 specified radix, writing no more than `limit` bytes of data to the given 190 output buffer. It generates `prec` digits of precision, and requires 191 `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. 192 193 Ratios usually must be rounded when they are being converted for output as 194 a decimal value. There are four rounding modes currently supported: 195 196 MP_ROUND_DOWN 197 Truncates the value toward zero. 198 Example: 12.009 to 2dp becomes 12.00 199 200 MP_ROUND_UP 201 Rounds the value away from zero: 202 Example: 12.001 to 2dp becomes 12.01, but 203 12.000 to 2dp remains 12.00 204 205 MP_ROUND_HALF_DOWN 206 Rounds the value to nearest digit, half goes toward zero. 207 Example: 12.005 to 2dp becomes 12.00, but 208 12.006 to 2dp becomes 12.01 209 210 MP_ROUND_HALF_UP 211 Rounds the value to nearest digit, half rounds upward. 212 Example: 12.005 to 2dp becomes 12.01, but 213 12.004 to 2dp becomes 12.00 214 */ 215 mp_result mp_rat_to_decimal(mp_rat r, mp_size radix, mp_size prec, 216 mp_round_mode round, char *str, int limit); 217 218 /** Reports the minimum number of characters required to represent `r` as a 219 zero-terminated string in the given `radix`. 220 Requires `MP_MIN_RADIX <= radix <= MP_MAX_RADIX`. */ 221 mp_result mp_rat_string_len(mp_rat r, mp_size radix); 222 223 /** Reports the length in bytes of the buffer needed to convert `r` using the 224 `mp_rat_to_decimal()` function with the specified `radix` and `prec`. The 225 buffer size estimate may slightly exceed the actual required capacity. */ 226 mp_result mp_rat_decimal_len(mp_rat r, mp_size radix, mp_size prec); 227 228 /** Sets `r` to the value represented by a zero-terminated string `str` in the 229 format `"n/d"` including a sign flag. It returns `MP_UNDEF` if the encoded 230 denominator has value zero. */ 231 mp_result mp_rat_read_string(mp_rat r, mp_size radix, const char *str); 232 233 /** Sets `r` to the value represented by a zero-terminated string `str` in the 234 format `"n/d"` including a sign flag. It returns `MP_UNDEF` if the encoded 235 denominator has value zero. If `end` is not NULL then `*end` is set to 236 point to the first unconsumed character in the string, after parsing. 237 */ 238 mp_result mp_rat_read_cstring(mp_rat r, mp_size radix, const char *str, 239 char **end); 240 241 /** Sets `r` to the value represented by a zero-terminated string `str` having 242 one of the following formats, each with an optional leading sign flag: 243 244 n : integer format, e.g. "123" 245 n/d : ratio format, e.g., "-12/5" 246 z.ffff : decimal format, e.g., "1.627" 247 248 It returns `MP_UNDEF` if the effective denominator is zero. If `end` is not 249 NULL then `*end` is set to point to the first unconsumed character in the 250 string, after parsing. 251 */ 252 mp_result mp_rat_read_ustring(mp_rat r, mp_size radix, const char *str, 253 char **end); 254 255 /** Sets `r` to the value represented by a zero-terminated string `str` in the 256 format `"z.ffff"` including a sign flag. It returns `MP_UNDEF` if the 257 effective denominator. */ 258 mp_result mp_rat_read_decimal(mp_rat r, mp_size radix, const char *str); 259 260 /** Sets `r` to the value represented by a zero-terminated string `str` in the 261 format `"z.ffff"` including a sign flag. It returns `MP_UNDEF` if the 262 effective denominator. If `end` is not NULL then `*end` is set to point to 263 the first unconsumed character in the string, after parsing. */ 264 mp_result mp_rat_read_cdecimal(mp_rat r, mp_size radix, const char *str, 265 char **end); 266 267 #ifdef __cplusplus 268 } 269 #endif 270 #endif /* IMRAT_H_ */ 271