Wolfram Research

Function Repository Resource:

HalfGCD

Source Notebook

Compute the half-gcd of a pair of integers

Contributed by: Daniel Lichtblau

ResourceFunction["HalfGCD"][i1,i2]

returns the half-gcd matrix and list for integers i1 and i2.

Details

The half-gcd is also called the HGCD.
The half-gcd of a pair of positive integers (i1,i2) with i1>i2 is a matrix of integers m and a vector of integers v=(v1,v2) satisfying (i) m.(i1,i2)=v (ii) det(m)=±1 (iii) v1> v2.
The pair (v1,v2) lies in the "middle" of the Euclidean remainder sequence for (i1,i2), insofar as they straddle the half-size in bits of the larger integer i1.
ResourceFunction["HalfGCD"] is suitably modified to handle negative values or values in reverse order of magnitude.
ResourceFunction["HalfGCD"] is implemented using an efficient divide-and-conquer method.
ResourceFunction["HalfGCD"] uses the same internal Mathematica kernel code used for the efficient implementations of the GCD and ExtendedGCD functions.
ResourceFunction["HalfGCD"] also works on Gaussian integer inputs.

Examples

Basic Examples (2) 

Compute the half-gcd of 68 and 44:

In[1]:=
{m, v} = ResourceFunction["HalfGCD"][68, 44]
Out[1]=

Check that the half-gcd criteria are satisfied:

In[2]:=
{m . {68, 44} == v, Abs[Det[m]] == 1, v[[1]] >= Sqrt[68] > v[[2]]}
Out[2]=

Scope (3) 

HalfGCD handles negative inputs:

In[3]:=
ResourceFunction["HalfGCD"][68, -44]
Out[3]=

Inputs need not be ordered by magnitude:

In[4]:=
ResourceFunction["HalfGCD"][44, 68]
Out[4]=

HalfGCD handles Gaussian integer inputs:

In[5]:=
{mat, vec} = ResourceFunction["HalfGCD"][44 + 57 I, 68 - 81 I]
Out[5]=

Check the result:

In[6]:=
mat . {44 + 57 I, 68 - 81 I} == vec
Out[6]=

Properties and Relations (4) 

The half-gcd can be iterated to compute the usual GCD (a step of the Euclidean algorithm is interleaved in order to guarantee a reduction when the numbers are too far apart for HalfGCD to give a nontrivial reduction):

In[7]:=
FixedPoint[Module[{hg = ResourceFunction["HalfGCD"] @@ #[[2]], q, r},
   If[hg[[2, 1]] == 0,
    {q, r} = QuotientRemainder @@ hg[[2]];
    hg[[1]] = {{0, 1}, {1, -q}} . hg[[1]];
    hg[[2]] = {hg[[2, 2]], r};
    ];
   {hg[[1]] . #[[1]], hg[[2]]}] &, {IdentityMatrix[2], {3898641600, 2200354800}}]
Out[7]=

Check that 8400 is the correct GCD:

In[8]:=
GCD @@ {3898641600, 2200354800}
Out[8]=

Check that the corresponding row of the conversion matrix gives the multipliers for the extended GCD:

In[9]:=
ExtendedGCD @@ {3898641600, 2200354800}
Out[9]=

The half-gcd is often identical (up to row signs) to the result of a certain lattice reduction:

In[10]:=
{n1, n2} = {168, 144};
LatticeReduce[Join[IdentityMatrix[2], Transpose[{{n1, n2}}], 2]]
Out[11]=
In[12]:=
ResourceFunction["HalfGCD"][n1, n2]
Out[12]=

The asymptotic speed of the half-gcd implementation is quasilinear (linear times logarithmic factors) in the size of the inputs, so doubling the sizes only slightly more than doubles the timings:

In[13]:=
Table[bits = 2^n;
 {n1, n2} = RandomInteger[2^bits, 2];
 First[Timing[ResourceFunction["HalfGCD"][n1, n2];]], {n, 20, 25}]
Out[13]=

For large inputs (i1,i2), the fact that m.(i1,i2) gives a relatively small second element means that m2.(i1,i2) can be considered approximately zero, relative to the size of inputs. This in turn implies that |m2,2/m2,1| is a good approximation to |i1/i2|. One can use this to create rational approximations of irrational values.

Find the half-gcd of the nearest integer to 1010π with the prefactor 1010:

In[14]:=
{mat, vec} = ResourceFunction["HalfGCD"][Round[10^10*Pi], 10^10]
Out[14]=

Check the quotient of the second row in the multiplier matrix:

In[15]:=
quot = Abs[mat[[2, 2]]/mat[[2, 1]]];
digits = 13;
{quot, N[quot, digits], N[Pi, digits]}
Out[17]=

This quotient will often appear in the list of continued fraction approximations to π:

In[18]:=
Convergents@ContinuedFraction[Pi, 8]
Out[18]=

Possible Issues (1) 

When the second input divides the first and is less than the square root of the first, the GCD can be computed in one step, but HalfGCD will not take that step due to criterion (iii) noted in Details & Options:

In[19]:=
ResourceFunction["HalfGCD"][36, 4]
Out[19]=

Neat Examples (3) 

Thue's Lemma guarantees that for a given modulus p>1, an integer n has a rational equivalent modulo p with numerator and denominator no larger than . It can be found using the half-gcd. A common use case is in reconstructing rational solutions to linear equations from solutions computed over the integers modulo a power of a prime.

Code to reconstruct a rational equivalent mod p for a given n:

In[20]:=
rationalRecover[n_, p_] := (#[[2, 2]]/#[[1, 2, 2]]) &[
  ResourceFunction["HalfGCD"][p, n]]

Find the rational equivalent to 123456789 modulo the cube of the 100th prime:

In[21]:=
p100cube = Prime[100]^3;
bigint = 123456789;
rat = rationalRecover[bigint, p100cube]
Out[21]=

Show that it is equivalent:

In[22]:=
{num, den} = NumeratorDenominator[rat];
Mod[den*bigint - num, p100cube]
Out[22]=

Resource History

Source Metadata

Related Resources

License Information