Click or drag to resize
gmp_libmpn_divexact_by3c Method
Divide {sp, n} by 3, expecting it to divide exactly, and writing the result to {rp, n}.

Namespace:  Math.Gmp.Native
Assembly:  Math.Gmp.Native (in Math.Gmp.Native.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
public static mp_limb_t mpn_divexact_by3c(
	mp_ptr rp,
	mp_ptr sp,
	mp_size_t n,
	mp_limb_t carry
)

Parameters

rp
Type: Math.Gmp.Nativemp_ptr
The result integer.
sp
Type: Math.Gmp.Nativemp_ptr
The operand integer.
n
Type: Math.Gmp.Nativemp_size_t
The number of limbs in sp.
carry
Type: Math.Gmp.Nativemp_limb_t
The initial carry.

Return Value

Type: mp_limb_t
If 3 divides exactly, the return value is zero and the result is the quotient. If not, the return value is non-zero and the result won’t be anything useful.
Remarks

mpn_divexact_by3c takes an initial carry parameter, which can be the return value from a previous call, so a large calculation can be done piece by piece from low to high. mpn_divexact_by3 is simply a macro calling mpn_divexact_by3c with a 0 carry parameter.

These routines use a multiply-by-inverse and will be faster than mpn_divrem_1 on CPUs with fast multiplication but slow division.

The source a, result q, size n, initial carry i, and return value c satisfy c * b^n + a - i = 3 * q, where b = 2^mp_bits_per_limb. The return c is always 0, 1 or 2, and the initial carry i must also be 0, 1 or 2 (these are both borrows really). When c = 0 clearly q = (a - i) / 3. When c != 0, the remainder (a - i) mod 3 is given by 3 - c, because b ≡ 1 mod 3 (when mp_bits_per_limb is even, which is always so currently).

Examples
// Create multi-precision operands, and expected result.
mp_ptr sp = new mp_ptr(new uint[] { 0xffffffff, 0x0000ffff });
mp_ptr rp = new mp_ptr(new uint[2]);
mp_ptr result = new mp_ptr(new uint[] { 0xaaaaaaaa, 0x5555aaaa });

// Set rp = sp / 3.
mp_limb_t remainder = gmp_lib.mpn_divexact_by3c(rp, sp, sp.Size, 1);

// Assert result of operation.
Assert.IsTrue(remainder == 1);
Assert.IsTrue(rp.SequenceEqual(result));

// Release unmanaged memory.
gmp_lib.free(rp, sp, result);
See Also