fmpzi.h – Gaussian integers

This module allows working with elements of the ring \(\mathbb{Z}[i]\). At present, only a minimal interface is provided.

Types, macros and constants

type fmpzi_struct

type fmpzi_t

Contains a pairs of integers representing the real and imaginary parts. An fmpzi_t is defined as an array of length one of type fmpzi_struct, permitting an fmpzi_t to be passed by reference.

fmpzi_realref(x)

Macro giving a pointer to the real part of x.

fmpzi_imagref(x)

Macro giving a pointer to the imaginary part of x.

Basic manipulation

void fmpzi_init(fmpzi_t x)

void fmpzi_clear(fmpzi_t x)

void fmpzi_swap(fmpzi_t x, fmpzi_t y)

void fmpzi_zero(fmpzi_t x)

void fmpzi_one(fmpzi_t x)

void fmpzi_set(fmpzi_t res, const fmpzi_t x)

void fmpzi_set_si_si(fmpzi_t res, slong a, slong b)

Input and output

void fmpzi_print(const fmpzi_t x)

Random number generation

void fmpzi_randtest(fmpzi_t res, flint_rand_t state, flint_bitcnt_t bits)

Properties

int fmpzi_equal(const fmpzi_t x, const fmpzi_t y)

int fmpzi_is_zero(const fmpzi_t x)

int fmpzi_is_one(const fmpzi_t x)

Units

int fmpzi_is_unit(const fmpzi_t x)

slong fmpzi_canonical_unit_i_pow(const fmpzi_t x)

void fmpzi_canonicalise_unit(fmpzi_t res, const fmpzi_t x)

Norms

slong fmpzi_bits(const fmpzi_t x)

void fmpzi_norm(fmpz_t res, const fmpzi_t x)

Arithmetic

void fmpzi_conj(fmpzi_t res, const fmpzi_t x)

void fmpzi_neg(fmpzi_t res, const fmpzi_t x)

void fmpzi_add(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_sub(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_sqr(fmpzi_t res, const fmpzi_t x)

void fmpzi_mul(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_pow_ui(fmpzi_t res, const fmpzi_t x, ulong exp)

Division

void fmpzi_divexact(fmpzi_t q, const fmpzi_t x, const fmpzi_t y)

Sets q to the quotient of x and y, assuming that the division is exact.

void fmpzi_divrem(fmpzi_t q, fmpzi_t r, const fmpzi_t x, const fmpzi_t y)

Computes a quotient and remainder satisfying \(x = q y + r\) with \(N(r) \le N(y)/2\), with a canonical choice of remainder when breaking ties.

void fmpzi_divrem_approx(fmpzi_t q, fmpzi_t r, const fmpzi_t x, const fmpzi_t y)

Computes a quotient and remainder satisfying \(x = q y + r\) with \(N(r) < N(y)\), with an implementation-defined, non-canonical choice of remainder.

slong fmpzi_remove_one_plus_i(fmpzi_t res, const fmpzi_t x)

Divide x exactly by the largest possible power \((1+i)^k\) and return the exponent k.

GCD

void fmpzi_gcd_euclidean(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_gcd_euclidean_improved(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_gcd_binary(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_gcd_shortest(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

void fmpzi_gcd(fmpzi_t res, const fmpzi_t x, const fmpzi_t y)

Computes the GCD of x and y. The result is in canonical unit form.

The euclidean version is a straightforward implementation of Euclid’s algorithm. The euclidean_improved version is optimized by performing approximate divisions. The binary version uses a (1+i)-ary analog of the binary GCD algorithm for integers [Wei2000]. The shortest version finds the GCD as the shortest vector in a lattice. The default version chooses an algorithm automatically.

Primality testing

int fmpzi_is_prime(const fmpzi_t n)

Check whether \(n\) is a Gaussian prime.

int fmpzi_is_probabprime(const fmpzi_t n)

Check whether \(n\) is a probable Gaussian prime.

int _fmpzi_poly_mulmid_classical_fft_small(fmpzi_struct *res, const fmpzi_struct *poly1, slong len1, const fmpzi_struct *poly2, slong len2, slong nlo, slong nhi)

Computes the coefficients \([\mathtt{nlo}, \mathtt{nhi})\) of the product of the Gaussian integer polynomials (poly1, len1) and (poly2, len2), with the coefficient arithmetic done pointwise on fft_small transforms: two transforms per coefficient (real and imaginary parts) and four pointwise operations per complex product, the shorter operand’s transforms kept and the longer rolling as in _fmpz_poly_mulmid_classical_fft_small(). Squaring shares transforms, pairs symmetric terms and computes diagonal squares with three multiplications. The lengths may be given in either order. Returns 1 on success and 0 when the transformed representation is unavailable or unprofitable in which case nothing is written and the caller should fall back to a different routine.