Class NDGcdLcm
Greatest-common-divisor / lowest-common-multiple element helpers for np.gcd and
np.lcm — a line-for-line port of NumPy 2.4.2's npy_gcd@c@ / npy_lcm@c@
(numpy/_core/src/npymath/npy_math_internal.h.src) driving the integer @TYPE@_gcd /
@TYPE@_lcm loops (loops.c.src). One helper per NumSharp integer dtype, mirroring the
NDDivision Fmod* layout, so the IL kernels resolve a single call per
element (DirectILKernelGenerator.EmitGcdLcmOperation). gcd/lcm have integer loops ONLY —
bool/float/complex/decimal are rejected at the np.* boundary before any kernel runs, so no
float helper exists here.
Algorithm (NumPy verbatim). The unsigned helpers are the core:
gcd(a,b) is the iterative Euclidean remainder loop while(a!=0){c=a; a=b%a; b=c;} return b;
and lcm(a,b) = gcd==0 ? 0 : a/gcd*b (divide-BEFORE-multiply, to widen the exactly-divisible
factor out first — the product can still overflow the dtype and WRAPS, matching NumPy). The signed
helpers delegate to the unsigned core on the operands' magnitudes exactly as NumPy does
(npy_gcd(a,b) = npy_gcdu(a<0?-a:a, b<0?-b:b)), then reinterpret the unsigned result back to
the signed type.
Two consequences that look like bugs but are NumPy-exact (probed against 2.4.2, so do
NOT "fix" them): the result of a signed gcd/lcm can be negative when the unsigned magnitude
wraps the signed range — e.g. gcd(int8 -128, -128) == -128 (the magnitude 128 has no positive
int8), lcm(int32.MinValue, 1) == int32.MinValue; and an overflowing lcm product wraps
silently — e.g. lcm(int16 21000, 14000) == -23536, lcm(uint32.MaxValue, MaxValue-1) == 2.
The |MIN| magnitude is obtained by the C idiom (U)(unchecked(-x)): negating the signed
minimum wraps back to itself, and its bit pattern reinterpreted as unsigned IS 2^(width-1)
(the true magnitude) — which is why every negate/cast below is unchecked.
Why the 8/16-bit helpers may compute in their own width rather than promoting to int32
(as NumPy's BYTE_gcd does via C integer promotion): for gcd, all Euclidean intermediates are
bounded by max(|a|,|b|) and so never exceed the width; for lcm, |a|/gcd is exact and
both it and |b| are < 2^width, and modular multiplication is width-invariant
((x*y) mod 2^w == ((x mod 2^w)*(y mod 2^w)) mod 2^w), so narrowing the int32-domain product
gives the identical wrapped byte/short result. C# already widens byte/ushort/char
operands to int for %/*, so the narrowing cast on store closes the equivalence.
public static class NDGcdLcm
- Inheritance
-
NDGcdLcm
- Inherited Members
Methods
GcdByte(byte, byte)
Euclidean GCD of two byte magnitudes (np.gcd uint8 loop). Returns 0 only when both inputs are 0.
public static byte GcdByte(byte a, byte b)
Parameters
Returns
- byte
The greatest common divisor, in
[0, 255].
GcdChar(char, char)
Euclidean GCD of two char code-unit magnitudes (NumSharp Char extension; treated as uint16).
public static char GcdChar(char a, char b)
Parameters
Returns
GcdInt16(short, short)
Signed GCD (np.gcd int16 loop): GcdUInt16(|a|,|b|) reinterpreted to short.
public static short GcdInt16(short a, short b)
Parameters
Returns
- short
The gcd; negative only when the magnitude wraps int16 (e.g.
gcd(-32768,-32768)).
GcdInt32(int, int)
Signed GCD (np.gcd int32 loop): GcdUInt32(|a|,|b|) reinterpreted to int.
public static int GcdInt32(int a, int b)
Parameters
Returns
- int
The gcd; negative only when the magnitude wraps int32 (e.g.
gcd(int.MinValue, int.MinValue)).
GcdInt64(long, long)
Signed GCD (np.gcd int64 loop): GcdUInt64(|a|,|b|) reinterpreted to long.
public static long GcdInt64(long a, long b)
Parameters
Returns
- long
The gcd; negative only when the magnitude wraps int64 (e.g.
gcd(long.MinValue, long.MinValue)).
GcdSByte(sbyte, sbyte)
Signed GCD (np.gcd int8 loop): GcdByte(|a|,|b|) reinterpreted to sbyte.
public static sbyte GcdSByte(sbyte a, sbyte b)
Parameters
Returns
- sbyte
The gcd; negative only for
gcd(-128,-128) == -128(magnitude 128 wraps int8).
GcdUInt16(ushort, ushort)
Euclidean GCD of two ushort magnitudes (np.gcd uint16 loop).
public static ushort GcdUInt16(ushort a, ushort b)
Parameters
Returns
- ushort
The greatest common divisor, in
[0, 65535].
GcdUInt32(uint, uint)
Euclidean GCD of two uint magnitudes (np.gcd uint32 loop).
public static uint GcdUInt32(uint a, uint b)
Parameters
Returns
- uint
The greatest common divisor.
GcdUInt64(ulong, ulong)
Euclidean GCD of two ulong magnitudes (np.gcd uint64 loop).
public static ulong GcdUInt64(ulong a, ulong b)
Parameters
Returns
- ulong
The greatest common divisor.
LcmByte(byte, byte)
Lowest common multiple of two byte magnitudes (np.lcm uint8 loop). Wraps mod 256 on overflow.
public static byte LcmByte(byte a, byte b)
Parameters
Returns
- byte
The lcm (0 if either operand is 0).
LcmChar(char, char)
Lowest common multiple of two char code-unit magnitudes (NumSharp Char extension). Wraps mod 65536.
public static char LcmChar(char a, char b)
Parameters
Returns
LcmInt16(short, short)
Signed LCM (np.lcm int16 loop): LcmUInt16(|a|,|b|) reinterpreted to short (wraps).
public static short LcmInt16(short a, short b)
Parameters
Returns
- short
The lcm; may be negative when the (wrapping) magnitude product exceeds short range.
LcmInt32(int, int)
Signed LCM (np.lcm int32 loop): LcmUInt32(|a|,|b|) reinterpreted to int (wraps).
public static int LcmInt32(int a, int b)
Parameters
Returns
- int
The lcm; may be negative when the (wrapping) magnitude product exceeds int range (e.g.
lcm(int.MinValue, 1)).
LcmInt64(long, long)
Signed LCM (np.lcm int64 loop): LcmUInt64(|a|,|b|) reinterpreted to long (wraps).
public static long LcmInt64(long a, long b)
Parameters
Returns
- long
The lcm; may be negative when the (wrapping) magnitude product exceeds long range.
LcmSByte(sbyte, sbyte)
Signed LCM (np.lcm int8 loop): LcmByte(|a|,|b|) reinterpreted to sbyte (wraps).
public static sbyte LcmSByte(sbyte a, sbyte b)
Parameters
Returns
- sbyte
The lcm; may be negative when the (wrapping) magnitude product exceeds sbyte range.
LcmUInt16(ushort, ushort)
Lowest common multiple of two ushort magnitudes (np.lcm uint16 loop). Wraps mod 65536 on overflow.
public static ushort LcmUInt16(ushort a, ushort b)
Parameters
Returns
- ushort
The lcm (0 if either operand is 0).
LcmUInt32(uint, uint)
Lowest common multiple of two uint magnitudes (np.lcm uint32 loop). Wraps mod 2^32 on overflow.
public static uint LcmUInt32(uint a, uint b)
Parameters
Returns
- uint
The lcm (0 if either operand is 0).
LcmUInt64(ulong, ulong)
Lowest common multiple of two ulong magnitudes (np.lcm uint64 loop). Wraps mod 2^64 on overflow.
public static ulong LcmUInt64(ulong a, ulong b)
Parameters
Returns
- ulong
The lcm (0 if either operand is 0).