gcd
rma may alias x or y.
x and y may alias each other.
Asserts that rma has enough limbs to store the result. Upper bound is
@min(x.limbs.len, y.limbs.len).
limbs_buffer is used for temporary storage during the operation. When this function returns,
it will have the same length as it had when the function was called.
Function parameters
Parameters
Used to indicate either limit of a 2s-complement integer.
Types
- TwosCompIntLimit
- Used to indicate either limit of a 2s-complement integer.
- Mutable
- A arbitrary-precision big integer, with a fixed set of mutable limbs.
- Const
- A arbitrary-precision big integer, with a fixed set of immutable limbs.
- Managed
- An arbitrary-precision big integer along with an allocator which manages the memory.
Returns the number of limbs needed to store `scalar`, which must be a
Functions
- calcLimbLen
- Returns the number of limbs needed to store `scalar`, which must be a
- calcSetStringLimbCount
- Assumes `string_len` doesn't account for minus signs if the number is negative.
- calcNonZeroTwosCompLimbCount
- Compute the number of limbs required to store a 2s-complement number of `bit_count` bits.
- calcTwosCompLimbCount
- Compute the number of limbs required to store a 2s-complement number of `bit_count` bits.
- addMulLimbWithCarry
- a + b * c + *carry, sets carry to the overflow bits
- llcmp
- Returns -1, 0, 1 if |a| < |b|, |a| == |b| or |a| > |b| respectively for limbs.
Source
Implementation
pub fn gcd(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void {
const prev_len = limbs_buffer.items.len;
defer limbs_buffer.shrinkRetainingCapacity(prev_len);
const x_copy = if (rma.limbs.ptr == x.limbs.ptr) blk: {
const start = limbs_buffer.items.len;
try limbs_buffer.appendSlice(x.limbs);
break :blk x.toMutable(limbs_buffer.items[start..]).toConst();
} else x;
const y_copy = if (rma.limbs.ptr == y.limbs.ptr) blk: {
const start = limbs_buffer.items.len;
try limbs_buffer.appendSlice(y.limbs);
break :blk y.toMutable(limbs_buffer.items[start..]).toConst();
} else y;
return gcdLehmer(rma, x_copy, y_copy, limbs_buffer);
}