gmp_lib.mpn_gcdext Method (mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_ptr, mp_size_t)

GMP Native Interface for .NET

previous page next page
gmp_libmpn_gcdext Method (mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_ptr, mp_size_t)
Compute the greatest common divisor G of U and V. Compute a cofactor S such that G = US + VT.

Namespace:  Math.Gmp.Native
Assembly:  Math.Gmp.Native (in Math.Gmp.Native.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
Copy
public static mp_size_t mpn_gcdext(
	mp_ptr gp,
	mp_ptr sp,
	ref mp_size_t sn,
	mp_ptr up,
	mp_size_t un,
	mp_ptr vp,
	mp_size_t vn
)
Public Shared Function mpn_gcdext ( 
	gp As mp_ptr,
	sp As mp_ptr,
	ByRef sn As mp_size_t,
	up As mp_ptr,
	un As mp_size_t,
	vp As mp_ptr,
	vn As mp_size_t
) As mp_size_t
public:
static mp_size_t mpn_gcdext(
	mp_ptr^ gp, 
	mp_ptr^ sp, 
	mp_size_t% sn, 
	mp_ptr^ up, 
	mp_size_t un, 
	mp_ptr^ vp, 
	mp_size_t vn
)
static member mpn_gcdext : 
        gp : mp_ptr * 
        sp : mp_ptr * 
        sn : mp_size_t byref * 
        up : mp_ptr * 
        un : mp_size_t * 
        vp : mp_ptr * 
        vn : mp_size_t -> mp_size_t

Parameters

gp
Type: Math.Gmp.Nativemp_ptr
The fisrt result operand.
sp
Type: Math.Gmp.Nativemp_ptr
The second result operand.
sn
Type: Math.Gmp.Nativemp_size_t
Pointer to the number of limbs of sp.
up
Type: Math.Gmp.Nativemp_ptr
The first operand integer.
un
Type: Math.Gmp.Nativemp_size_t
The number of limbs of up.
vp
Type: Math.Gmp.Nativemp_ptr
The second operand integer.
vn
Type: Math.Gmp.Nativemp_size_t
The number of limbs of vp.

Return Value

Type: mp_size_t
The number of limbs of gp.
Remarks

Let U be defined by {up, un} and let V be defined by {vp, vn}.

The second cofactor T is not computed but can easily be obtained from (G - U * S) / V (the division will be exact). It is required that un ≥ vn > 0, and the most significant limb of {vp, vn} must be non-zero.

Store G at gp and let the return value define its limb count. Store S at sp and let | sn.Value | define its limb count. S can be negative; when this happens sn.Value will be negative. The area at gp should have room for vn limbs and the area at sp should have room for vn + 1 limbs.

Both source operands are destroyed.

Compatibility notes: GMP 4.3.0 and 4.3.1 defined S less strictly. Earlier as well as later GMP releases define S as described here. GMP releases before GMP 4.3.0 required additional space for both input and output areas. More precisely, the areas {up, un + 1} and {vp, vn + 1} were destroyed (i.e. the operands plus an extra limb past the end of each), and the areas pointed to by gp and sp should each have room for un + 1 limbs.

Examples
Copy
// Create multi-precision operands, and expected result.
mp_ptr up = new mp_ptr(new uint[] { 0x40000000, 0x00000000 });
mp_ptr vp = new mp_ptr(new uint[] { 0x00000000, 0x00000001 });
mp_ptr gp = new mp_ptr(new uint[vp.Size * (IntPtr.Size / 4)]);
mp_ptr sp = new mp_ptr(new uint[(vp.Size + 1) * (IntPtr.Size / 4)]);
mp_ptr result = new mp_ptr(new uint[] { 0x40000000, 0x00000000 });
mp_ptr cofactor = new mp_ptr(new uint[] { 0x00000001, 0x00000000, 0x00000000 });

// Set gp = gcd(up, vp).
mp_size_t sn = 0;
mp_size_t size = gmp_lib.mpn_gcdext(gp, sp, ref sn, up, up.Size, vp, vp.Size);

// Assert result.
Assert.IsTrue(size == 1);
Assert.IsTrue(gp.SequenceEqual(result));
Assert.IsTrue(sn == 1);
Assert.IsTrue(sp.SequenceEqual(cofactor));

// Release unmanaged memory.
gmp_lib.free(gp, up, vp, sp, result, cofactor);
' Create multi-precision operands, and expected result.
Dim up As New mp_ptr(New UInteger() { &H40000000, &H0})
Dim vp As New mp_ptr(New UInteger() { &H0, &H1})
Dim gp As New mp_ptr(New UInteger(vp.Size* (IntPtr.Size / 4) - 1) {})
Dim sp As New mp_ptr(New UInteger((vp.Size + 1) * (IntPtr.Size / 4) - 1) {})
Dim result As New mp_ptr(New UInteger() { &H40000000, &H0})
Dim cofactor As New mp_ptr(New UInteger() { &H1, &H0, &H0})

' Set gp = gcd(up, vp).
Dim sn As mp_size_t = 0
Dim size As mp_size_t = gmp_lib.mpn_gcdext(gp, sp, sn, up, up.Size, vp, vp.Size)

' Assert result.
Assert.IsTrue(size = 1)
Assert.IsTrue(gp.SequenceEqual(result))
Assert.IsTrue(sn = 1)
Assert.IsTrue(sp.SequenceEqual(cofactor))

' Release unmanaged memory.
gmp_lib.free(gp, up, vp, sp, result, cofactor)

No code example is currently available or this language may not be supported.

No code example is currently available or this language may not be supported.

See Also
previous page start next page