From 9a21d2e070c9ee0ef2c003f3a668e635c6ae4401 Mon Sep 17 00:00:00 2001 From: Damien George Date: Sat, 6 Sep 2014 17:15:34 +0100 Subject: py: Make mpz able to use 16 bits per digit; and 32 on 64-bit arch. Previously, mpz was restricted to using at most 15 bits in each digit, where a digit was a uint16_t. With this patch, mpz can use all 16 bits in the uint16_t (improvement to mpn_div was required). This gives small inprovements in speed and RAM usage. It also yields savings in ROM code size because all of the digit masking operations become no-ops. Also, mpz can now use a uint32_t as the digit type, and hence use 32 bits per digit. This will give decent improvements in mpz speed on 64-bit machines. Test for big integer division added. --- py/mpz.h | 29 +++++++++++++++++++++++++---- 1 file changed, 25 insertions(+), 4 deletions(-) (limited to 'py/mpz.h') diff --git a/py/mpz.h b/py/mpz.h index 6eaaf378a..79e5ea231 100644 --- a/py/mpz.h +++ b/py/mpz.h @@ -24,9 +24,34 @@ * THE SOFTWARE. */ +// This mpz module implements arbitrary precision integers. +// +// The storage for each digit is defined by mpz_dig_t. The actual number of +// bits in mpz_dig_t that are used is defined by MPZ_DIG_SIZE. The machine must +// also provide a type that is twice as wide as mpz_dig_t, in both signed and +// unsigned versions. +// +// MPZ_DIG_SIZE can be between 4 and 8*sizeof(mpz_dig_t), but it makes most +// sense to have it as large as possible. Below, the type is auto-detected +// depending on the machine, but it (and MPZ_DIG_SIZE) can be freely changed so +// long as the constraints mentioned above are met. + +#if defined(__x86_64__) +// 64-bit machine, using 32-bit storage for digits +typedef uint32_t mpz_dig_t; +typedef uint64_t mpz_dbl_dig_t; +typedef int64_t mpz_dbl_dig_signed_t; +#define MPZ_DIG_SIZE (32) +#else +// 32-bit machine, using 16-bit storage for digits typedef uint16_t mpz_dig_t; typedef uint32_t mpz_dbl_dig_t; typedef int32_t mpz_dbl_dig_signed_t; +#define MPZ_DIG_SIZE (16) +#endif + +#define MPZ_NUM_DIG_FOR_INT (sizeof(mp_int_t) * 8 / MPZ_DIG_SIZE + 1) +#define MPZ_NUM_DIG_FOR_LL (sizeof(long long) * 8 / MPZ_DIG_SIZE + 1) typedef struct _mpz_t { mp_uint_t neg : 1; @@ -36,10 +61,6 @@ typedef struct _mpz_t { mpz_dig_t *dig; } mpz_t; -#define MPZ_DIG_SIZE (15) // see mpn_div for why this needs to be at most 15 -#define MPZ_NUM_DIG_FOR_INT (sizeof(mp_int_t) * 8 / MPZ_DIG_SIZE + 1) -#define MPZ_NUM_DIG_FOR_LL (sizeof(long long) * 8 / MPZ_DIG_SIZE + 1) - // convenience macro to declare an mpz with a digit array from the stack, initialised by an integer #define MPZ_CONST_INT(z, val) mpz_t z; mpz_dig_t z ## _digits[MPZ_NUM_DIG_FOR_INT]; mpz_init_fixed_from_int(&z, z_digits, MPZ_NUM_DIG_FOR_INT, val); -- cgit v1.2.3