longlong.h – support functions for multiword arithmetic¶
Bit manipulation¶

flint_clz(x)¶
Returns the number of zerobits from the msb to the first nonzero bit in the limb \(x\). This is the number of steps \(x\) needs to be shifted left to set the most significant bit in \(x\). If \(x\) is zero then the return value is undefined.

flint_ctz(x)¶
As for
flint_clz()
, but counts from the least significant end. If \(x\) is zero then the return value is undefined.

flint_bitcnt_t FLINT_BIT_COUNT(ulong x)¶
Returns the number of binary bits required to represent x. If x is zero it returns 0. This is an inlinefunction only.
Addition and subtraction¶
Note
When aliasing inputs with outputs in these addition and subtraction macros, make sure to have \(s_{i}\) aliased with \(a_{i}\) for addition macros, and \(d_{i}\) aliased with \(m_{i}\) for optimal performance. Moreover, keep immediates (in other words, constants known to the compiler) in the \(b_{i}\) variables for addition and \(s_{i}\) for subtraction.

add_ssaaaa(s1, s0, a1, a0, b1, b0)¶
Sets \(s_1\) and \(s_0\) according to \(c B^2 + s_1 B + s_0 = (a_1 B + a_0) + (b_1 B + b_0)\), where \(B = 2^{\mathtt{FLINT\_BITS}}\) is the base, and \(c\) is the carry from the addition which is not stored anywhere.

add_sssaaaaaa(s2, s1, s0, a2, a1, a0, b2, b1, b0)¶
Works like
add_ssaaaa
, but for two threelimbed integers. Carry is lost.

sub_ddmmss(d1, d0, m1, m0, s1, s0)¶
Sets \(d_1\) and \(d_0\) to the difference between the twolimbed integers \(m_1 B + m_0\) and \(s_1 B + s_0\), where \(B = 2^{\mathtt{FLINT\_BITS}}\). Borrow from the subtraction is not stored anywhere.

sub_dddmmmsss(d2, d1, d0, m2, m1, m0, s2, s1, s0)¶
Works like
sub_dddmmmsss
, but for two threelimbed integers. Borrow is lost.
Multiplication¶

umul_ppmm(p1, p0, u, v)¶
Computes \(p_1 B + p0 = u v\), where \(B = 2^{\mathtt{FLINT\_BITS}}\).

smul_ppmm(p1, p0, u, v)¶
Works like
umul_ppmm
but for signed numbers.
Division¶

udiv_qrnnd(q, r, n1, n0, d)¶
Computes the nonnegative integers \(q\) and \(r\) in \(d q + r = n_1 B + n_0\), where \(B = 2^{\mathtt{FLINT\_BITS}}\). Assumes that \(n_1 < d\).

sdiv_qrnnd(quotient, remainder, high_numerator, low_numerator, denominator)¶
Works like
udiv_qrnnd
, but for signed numbers.

udiv_qrnnd_preinv(q, r, n1, n0, d, di)¶
Works like
udiv_qrnnd
, but takes a precomputed inversedi
as computed byn_preinvert_limb_prenorm()
. This function assumesd
is normalised, i.e. with most significant bit set.