3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
12 * The library is free for all purposes without any express
15 * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
18 /* divide by three (based on routine from MPI and the GMP manual) */
20 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
27 /* b = 2**DIGIT_BIT / 3 */
28 b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);
30 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
37 for (ix = a->used - 1; ix >= 0; ix--) {
38 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
41 /* multiply w by [1/3] */
42 t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);
44 /* now subtract 3 * [w/3] from w, to get the remainder */
47 /* fixup the remainder as required since
48 * the optimization is not exact.
57 q.dp[ix] = (mp_digit)t;
60 /* [optional] store the remainder */
65 /* [optional] store the quotient */
77 /* $Source: /cvs/libtom/libtommath/bn_mp_div_3.c,v $ */
78 /* $Revision: 1.3 $ */
79 /* $Date: 2006/03/31 14:18:44 $ */