Data Structures | |
struct | QofInt128 |
Functions | |
gboolean | equal128 (QofInt128 a, QofInt128 b) |
gint | cmp128 (QofInt128 a, QofInt128 b) |
QofInt128 | shift128 (QofInt128 x) |
QofInt128 | shiftleft128 (QofInt128 x) |
QofInt128 | inc128 (QofInt128 a) |
QofInt128 | add128 (QofInt128 a, QofInt128 b) |
QofInt128 | mult128 (gint64 a, gint64 b) |
QofInt128 | div128 (QofInt128 n, gint64 d) |
gint64 | rem128 (QofInt128 n, gint64 d) |
guint64 | gcf64 (guint64 num, guint64 denom) |
QofInt128 | lcm128 (guint64 a, guint64 b) |
Quick-n-dirty 128-bit integer math lib. Things seem to mostly work, and have been tested, but not comprehensively tested.
Add a pair of 128-bit numbers, returning a 128-bit number
Definition at line 308 of file qofmath128.c.
00309 { 00310 QofInt128 sum; 00311 if (a.isneg == b.isneg) 00312 { 00313 sum.isneg = a.isneg; 00314 sum.hi = a.hi + b.hi; 00315 sum.lo = a.lo + b.lo; 00316 if ((sum.lo < a.lo) || (sum.lo < b.lo)) 00317 { 00318 sum.hi++; 00319 } 00320 sum.isbig = sum.hi || (sum.lo >> 63); 00321 return sum; 00322 } 00323 if ((b.hi > a.hi) || ((b.hi == a.hi) && (b.lo > a.lo))) 00324 { 00325 QofInt128 tmp = a; 00326 a = b; 00327 b = tmp; 00328 } 00329 00330 sum.isneg = a.isneg; 00331 sum.hi = a.hi - b.hi; 00332 sum.lo = a.lo - b.lo; 00333 00334 if (sum.lo > a.lo) 00335 { 00336 sum.hi--; 00337 } 00338 00339 sum.isbig = sum.hi || (sum.lo >> 63); 00340 return sum; 00341 }
Return returns 1 if a>b, -1 if b>a, 0 if a == b
Definition at line 246 of file qofmath128.c.
00247 { 00248 if ((0 == a.isneg) && b.isneg) 00249 return 1; 00250 if (a.isneg && (0 == b.isneg)) 00251 return -1; 00252 if (0 == a.isneg) 00253 { 00254 if (a.hi > b.hi) 00255 return 1; 00256 if (a.hi < b.hi) 00257 return -1; 00258 if (a.lo > b.lo) 00259 return 1; 00260 if (a.lo < b.lo) 00261 return -1; 00262 return 0; 00263 } 00264 00265 if (a.hi > b.hi) 00266 return -1; 00267 if (a.hi < b.hi) 00268 return 1; 00269 if (a.lo > b.lo) 00270 return -1; 00271 if (a.lo < b.lo) 00272 return 1; 00273 return 0; 00274 }
Divide a signed 128-bit number by a signed 64-bit, returning a signed 128-bit number.
Definition at line 180 of file qofmath128.c.
00181 { 00182 QofInt128 quotient; 00183 int i; 00184 gint64 remainder = 0; 00185 00186 quotient = n; 00187 if (0 > d) 00188 { 00189 d = -d; 00190 quotient.isneg = !quotient.isneg; 00191 } 00192 00193 /* Use grade-school long division algorithm */ 00194 for (i = 0; i < 128; i++) 00195 { 00196 guint64 sbit = HIBIT & quotient.hi; 00197 remainder <<= 1; 00198 if (sbit) 00199 remainder |= 1; 00200 quotient = shiftleft128 (quotient); 00201 if (remainder >= d) 00202 { 00203 remainder -= d; 00204 quotient.lo |= 1; 00205 } 00206 } 00207 00208 /* compute the carry situation */ 00209 quotient.isbig = (quotient.hi || (quotient.lo >> 63)); 00210 00211 return quotient; 00212 }
Return true of two numbers are equal
Definition at line 233 of file qofmath128.c.
guint64 gcf64 | ( | guint64 | num, | |
guint64 | denom | |||
) | [inline] |
Return the greatest common factor of two 64-bit numbers
Definition at line 278 of file qofmath128.c.
00279 { 00280 guint64 t; 00281 00282 t = num % denom; 00283 num = denom; 00284 denom = t; 00285 00286 /* The strategy is to use Euclid's algorithm */ 00287 while (0 != denom) 00288 { 00289 t = num % denom; 00290 num = denom; 00291 denom = t; 00292 } 00293 /* num now holds the GCD (Greatest Common Divisor) */ 00294 return num; 00295 }
QofInt128 lcm128 | ( | guint64 | a, | |
guint64 | b | |||
) | [inline] |
Return the least common multiple of two 64-bit numbers.
Definition at line 299 of file qofmath128.c.
QofInt128 mult128 | ( | gint64 | a, | |
gint64 | b | |||
) | [inline] |
Multiply a pair of signed 64-bit numbers, returning a signed 128-bit number.
Definition at line 41 of file qofmath128.c.
00042 { 00043 QofInt128 prod; 00044 guint64 a0, a1; 00045 guint64 b0, b1; 00046 guint64 d, d0, d1; 00047 guint64 e, e0, e1; 00048 guint64 f, f0, f1; 00049 guint64 g, g0, g1; 00050 guint64 sum, carry, roll, pmax; 00051 00052 prod.isneg = 0; 00053 if (0 > a) 00054 { 00055 prod.isneg = !prod.isneg; 00056 a = -a; 00057 } 00058 00059 if (0 > b) 00060 { 00061 prod.isneg = !prod.isneg; 00062 b = -b; 00063 } 00064 00065 a1 = a >> 32; 00066 a0 = a - (a1 << 32); 00067 00068 b1 = b >> 32; 00069 b0 = b - (b1 << 32); 00070 00071 d = a0 * b0; 00072 d1 = d >> 32; 00073 d0 = d - (d1 << 32); 00074 00075 e = a0 * b1; 00076 e1 = e >> 32; 00077 e0 = e - (e1 << 32); 00078 00079 f = a1 * b0; 00080 f1 = f >> 32; 00081 f0 = f - (f1 << 32); 00082 00083 g = a1 * b1; 00084 g1 = g >> 32; 00085 g0 = g - (g1 << 32); 00086 00087 sum = d1 + e0 + f0; 00088 carry = 0; 00089 /* Can't say 1<<32 cause cpp will goof it up; 1ULL<<32 might work */ 00090 roll = 1 << 30; 00091 roll <<= 2; 00092 00093 pmax = roll - 1; 00094 while (pmax < sum) 00095 { 00096 sum -= roll; 00097 carry++; 00098 } 00099 00100 prod.lo = d0 + (sum << 32); 00101 prod.hi = carry + e1 + f1 + g0 + (g1 << 32); 00102 // prod.isbig = (prod.hi || (sum >> 31)); 00103 prod.isbig = prod.hi || (prod.lo >> 63); 00104 00105 return prod; 00106 }
gint64 rem128 | ( | QofInt128 | n, | |
gint64 | d | |||
) | [inline] |
Return the remainder of a signed 128-bit number modulo a signed 64-bit. That is, return nd in 128-bit math. I beleive that ths algo is overflow-free, but should be audited some more ...
Definition at line 220 of file qofmath128.c.
Shift right by one bit (i.e. divide by two)
Definition at line 110 of file qofmath128.c.
Shift left by one bit (i.e. multiply by two)
Shift leftt by one bit (i.e. multiply by two)
Definition at line 131 of file qofmath128.c.