An arbitrary-precision big integer along with an allocator which manages the memory.
Memory is allocated as needed to ensure operations never overflow. The range is bounded only by available memory.
pub const Managed = structpub const Managed = struct {
pub const sign_bit: usize = 1 << (@typeInfo(usize).int.bits - 1);
/// Default number of limbs to allocate on creation of a `Managed`.
pub const default_capacity = 4;
/// Allocator used by the Managed when requesting memory.
allocator: Allocator,
/// Raw digits. These are:
///
/// * Little-endian ordered
/// * limbs.len >= 1
/// * Zero is represent as Managed.len() == 1 with limbs[0] == 0.
///
/// Accessing limbs directly should be avoided.
limbs: []Limb,
/// High bit is the sign bit. If set, Managed is negative, else Managed is positive.
/// The remaining bits represent the number of limbs used by Managed.
metadata: usize,
/// Creates a new `Managed`. `default_capacity` limbs will be allocated immediately.
/// The integer value after initializing is `0`.
pub fn init(allocator: Allocator) !Managed {
return initCapacity(allocator, default_capacity);
}
pub fn toMutable(self: Managed) Mutable {
return .{
.limbs = self.limbs,
.positive = self.isPositive(),
.len = self.len(),
};
}
pub fn toConst(self: Managed) Const {
return .{
.limbs = self.limbs[0..self.len()],
.positive = self.isPositive(),
};
}
/// Creates a new `Managed` with value `value`.
///
/// This is identical to an `init`, followed by a `set`.
pub fn initSet(allocator: Allocator, value: anytype) !Managed {
var s = try Managed.init(allocator);
errdefer s.deinit();
try s.set(value);
return s;
}
/// Creates a new Managed with a specific capacity. If capacity < default_capacity then the
/// default capacity will be used instead.
/// The integer value after initializing is `0`.
pub fn initCapacity(allocator: Allocator, capacity: usize) !Managed {
return .{
.allocator = allocator,
.metadata = 1,
.limbs = block: {
const limbs = try allocator.alloc(Limb, @max(default_capacity, capacity));
limbs[0] = 0;
break :block limbs;
},
};
}
/// Returns the number of limbs currently in use.
pub fn len(self: Managed) usize {
return self.metadata & ~sign_bit;
}
/// Returns whether an Managed is positive.
pub fn isPositive(self: Managed) bool {
return self.metadata & sign_bit == 0;
}
/// Sets the sign of an Managed.
pub fn setSign(self: *Managed, positive: bool) void {
if (positive) {
self.metadata &= ~sign_bit;
} else {
self.metadata |= sign_bit;
}
}
/// Sets the length of an Managed.
///
/// If setLen is used, then the Managed must be normalized to suit.
pub fn setLen(self: *Managed, new_len: usize) void {
self.metadata &= sign_bit;
self.metadata |= new_len;
}
pub fn setMetadata(self: *Managed, positive: bool, length: usize) void {
self.metadata = if (positive) length & ~sign_bit else length | sign_bit;
}
/// Ensures an Managed has enough space allocated for capacity limbs. If the Managed does not have
/// sufficient capacity, the exact amount will be allocated. This occurs even if the requested
/// capacity is only greater than the current capacity by one limb.
pub fn ensureCapacity(self: *Managed, capacity: usize) !void {
if (capacity <= self.limbs.len) {
return;
}
self.limbs = try self.allocator.realloc(self.limbs, capacity);
}
/// Frees all associated memory.
pub fn deinit(self: *Managed) void {
self.allocator.free(self.limbs);
self.* = undefined;
}
/// Returns a `Managed` with the same value. The returned `Managed` is a deep copy and
/// can be modified separately from the original, and its resources are managed
/// separately from the original.
pub fn clone(other: Managed) !Managed {
return other.cloneWithDifferentAllocator(other.allocator);
}
pub fn cloneWithDifferentAllocator(other: Managed, allocator: Allocator) !Managed {
return .{
.allocator = allocator,
.metadata = other.metadata,
.limbs = block: {
const limbs = try allocator.alloc(Limb, other.len());
@memcpy(limbs, other.limbs[0..other.len()]);
break :block limbs;
},
};
}
/// Copies the value of the integer to an existing `Managed` so that they both have the same value.
/// Extra memory will be allocated if the receiver does not have enough capacity.
pub fn copy(self: *Managed, other: Const) !void {
if (self.limbs.ptr == other.limbs.ptr) return;
try self.ensureCapacity(other.limbs.len);
@memcpy(self.limbs[0..other.limbs.len], other.limbs[0..other.limbs.len]);
self.setMetadata(other.positive, other.limbs.len);
}
/// Efficiently swap a `Managed` with another. This swaps the limb pointers and a full copy is not
/// performed. The address of the limbs field will not be the same after this function.
pub fn swap(self: *Managed, other: *Managed) void {
mem.swap(Managed, self, other);
}
/// Debugging tool: prints the state to stderr.
pub fn dump(self: Managed) void {
for (self.limbs[0..self.len()]) |limb| {
std.debug.print("{x} ", .{limb});
}
std.debug.print("len={} capacity={} positive={}\n", .{ self.len(), self.limbs.len, self.isPositive() });
}
/// Negate the sign.
pub fn negate(self: *Managed) void {
self.metadata ^= sign_bit;
}
/// Make positive.
pub fn abs(self: *Managed) void {
self.metadata &= ~sign_bit;
}
pub fn isOdd(self: Managed) bool {
return self.limbs[0] & 1 != 0;
}
pub fn isEven(self: Managed) bool {
return !self.isOdd();
}
/// Returns the number of bits required to represent the absolute value of an integer.
pub fn bitCountAbs(self: Managed) usize {
return self.toConst().bitCountAbs();
}
/// Returns the number of bits required to represent the integer in twos-complement form.
///
/// If the integer is negative the value returned is the number of bits needed by a signed
/// integer to represent the value. If positive the value is the number of bits for an
/// unsigned integer. Any unsigned integer will fit in the signed integer with bitcount
/// one greater than the returned value.
///
/// e.g. -127 returns 8 as it will fit in an i8. 127 returns 7 since it fits in a u7.
pub fn bitCountTwosComp(self: Managed) usize {
return self.toConst().bitCountTwosComp();
}
pub fn fitsInTwosComp(self: Managed, signedness: Signedness, bit_count: usize) bool {
return self.toConst().fitsInTwosComp(signedness, bit_count);
}
/// Returns whether self can fit into an integer of the requested type.
pub fn fits(self: Managed, comptime T: type) bool {
return self.toConst().fits(T);
}
/// Returns the approximate size of the integer in the given base. Negative values accommodate for
/// the minus sign. This is used for determining the number of characters needed to print the
/// value. It is inexact and may exceed the given value by ~1-2 bytes.
pub fn sizeInBaseUpperBound(self: Managed, base: usize) usize {
return self.toConst().sizeInBaseUpperBound(base);
}
/// Sets an Managed to value. Value must be an primitive integer type.
pub fn set(self: *Managed, value: anytype) Allocator.Error!void {
try self.ensureCapacity(calcLimbLen(value));
var m = self.toMutable();
m.set(value);
self.setMetadata(m.positive, m.len);
}
pub const ConvertError = Const.ConvertError;
/// Convert `self` to `Int`.
///
/// Returns an error if self cannot be narrowed into the requested type without truncation.
pub fn toInt(self: Managed, comptime Int: type) ConvertError!Int {
return self.toConst().toInt(Int);
}
/// Convert `self` to `Float`.
pub fn toFloat(self: Managed, comptime Float: type, round: Round) struct { Float, Exactness } {
return self.toConst().toFloat(Float, round);
}
/// Set self from the string representation `value`.
///
/// `value` must contain only digits <= `base` and is case insensitive. Base prefixes are
/// not allowed (e.g. 0x43 should simply be 43). Underscores in the input string are
/// ignored and can be used as digit separators.
///
/// Returns an error if memory could not be allocated or `value` has invalid digits for the
/// requested base.
///
/// self's allocator is used for temporary storage to boost multiplication performance.
pub fn setString(self: *Managed, base: u8, value: []const u8) !void {
if (base < 2 or base > 36) return error.InvalidBase;
try self.ensureCapacity(calcSetStringLimbCount(base, value.len));
var m = self.toMutable();
try m.setString(base, value);
self.setMetadata(m.positive, m.len);
}
/// Set self to either bound of a 2s-complement integer.
/// Note: The result is still sign-magnitude, not twos complement! In order to convert the
/// result to twos complement, it is sufficient to take the absolute value.
pub fn setTwosCompIntLimit(
r: *Managed,
limit: TwosCompIntLimit,
signedness: Signedness,
bit_count: usize,
) !void {
try r.ensureCapacity(calcTwosCompLimbCount(bit_count));
var m = r.toMutable();
m.setTwosCompIntLimit(limit, signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// Converts self to a string in the requested base. Memory is allocated from the provided
/// allocator and not the one present in self.
pub fn toString(self: Managed, allocator: Allocator, base: u8, case: std.fmt.Case) ![]u8 {
if (base < 2 or base > 36) return error.InvalidBase;
return self.toConst().toStringAlloc(allocator, base, case);
}
/// To allow `std.fmt.format` to work with `Managed`.
pub fn format(self: Managed, w: *std.Io.Writer) std.Io.Writer.Error!void {
return formatNumber(self, w, .{});
}
/// If the absolute value of integer is greater than or equal to `pow(2, 64 * @sizeOf(usize) * 8)`,
/// this function will fail to print the string, printing "(BigInt)" instead of a number.
/// This is because the rendering algorithm requires reversing a string, which requires O(N) memory.
/// See `toString` and `toStringAlloc` for a way to print big integers without failure.
pub fn formatNumber(self: Managed, w: *std.Io.Writer, n: std.fmt.Number) std.Io.Writer.Error!void {
return self.toConst().formatNumber(w, n);
}
/// Returns math.Order.lt, math.Order.eq, math.Order.gt if |a| < |b|, |a| ==
/// |b| or |a| > |b| respectively.
pub fn orderAbs(a: Managed, b: Managed) math.Order {
return a.toConst().orderAbs(b.toConst());
}
/// Returns math.Order.lt, math.Order.eq, math.Order.gt if a < b, a == b or a > b
/// respectively.
pub fn order(a: Managed, b: Managed) math.Order {
return a.toConst().order(b.toConst());
}
/// Returns true if a == 0.
pub fn eqlZero(a: Managed) bool {
return a.toConst().eqlZero();
}
/// Returns true if |a| == |b|.
pub fn eqlAbs(a: Managed, b: Managed) bool {
return a.toConst().eqlAbs(b.toConst());
}
/// Returns true if a == b.
pub fn eql(a: Managed, b: Managed) bool {
return a.toConst().eql(b.toConst());
}
/// Normalize a possible sequence of leading zeros.
///
/// [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
/// [1, 2, 0, 0, 0] -> [1, 2]
/// [0, 0, 0, 0, 0] -> [0]
pub fn normalize(r: *Managed, length: usize) void {
assert(length > 0);
assert(length <= r.limbs.len);
var j = length;
while (j > 0) : (j -= 1) {
if (r.limbs[j - 1] != 0) {
break;
}
}
// Handle zero
r.setLen(if (j != 0) j else 1);
}
/// r = a + scalar
///
/// r and a may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn addScalar(r: *Managed, a: *const Managed, scalar: anytype) Allocator.Error!void {
const needed = @max(a.len(), calcLimbLen(scalar)) + 1;
const aliased = limbsAliasDistinct(r, a);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.addScalar(a.toConst(), scalar);
r.setMetadata(m.positive, m.len);
}
/// r = a + b
///
/// r, a and b may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn add(r: *Managed, a: *const Managed, b: *const Managed) Allocator.Error!void {
const needed = @max(a.len(), b.len()) + 1;
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.add(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a + b with 2s-complement wrapping semantics. Returns whether any overflow occurred.
///
/// r, a and b may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn addWrap(
r: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) Allocator.Error!bool {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
const wrapped = m.addWrap(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
return wrapped;
}
/// r = a + b with 2s-complement saturating semantics.
///
/// r, a and b may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn addSat(r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize) Allocator.Error!void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.addSat(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = a - b
///
/// r, a and b may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn sub(r: *Managed, a: *const Managed, b: *const Managed) !void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = @max(a.len(), b.len()) + 1;
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.sub(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a - b with 2s-complement wrapping semantics. Returns whether any overflow occurred.
///
/// r, a and b may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn subWrap(
r: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) Allocator.Error!bool {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
const wrapped = m.subWrap(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
return wrapped;
}
/// r = a - b with 2s-complement saturating semantics.
///
/// r, a and b may be aliases.
///
/// Returns an error if memory could not be allocated.
pub fn subSat(
r: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) Allocator.Error!void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.subSat(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// rma = a * b
///
/// rma, a and b may be aliases. However, it is more efficient if rma does not alias a or b.
///
/// Returns an error if memory could not be allocated.
///
/// rma's allocator is used for temporary storage to speed up the multiplication.
pub fn mul(rma: *Managed, a: *const Managed, b: *const Managed) !void {
var alias_count: usize = 0;
if (rma.limbs.ptr == a.limbs.ptr)
alias_count += 1;
if (rma.limbs.ptr == b.limbs.ptr)
alias_count += 1;
const needed = a.len() + b.len() + 1;
const capacity_alias = limbsAliasDistinct(rma, a) or limbsAliasDistinct(rma, b);
try rma.ensureAliasAwareCapacity(needed, capacity_alias);
var m = rma.toMutable();
if (alias_count == 0) {
m.mulNoAlias(a.toConst(), b.toConst(), rma.allocator);
} else {
const limb_count = calcMulLimbsBufferLen(a.len(), b.len(), alias_count);
const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
defer rma.allocator.free(limbs_buffer);
m.mul(a.toConst(), b.toConst(), limbs_buffer, rma.allocator);
}
rma.setMetadata(m.positive, m.len);
}
/// rma = a * b with 2s-complement wrapping semantics.
///
/// rma, a and b may be aliases. However, it is more efficient if rma does not alias a or b.
///
/// Returns an error if memory could not be allocated.
///
/// rma's allocator is used for temporary storage to speed up the multiplication.
pub fn mulWrap(
rma: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) !void {
var alias_count: usize = 0;
if (rma.limbs.ptr == a.limbs.ptr)
alias_count += 1;
if (rma.limbs.ptr == b.limbs.ptr)
alias_count += 1;
const needed = calcTwosCompLimbCount(bit_count);
const capacity_alias = limbsAliasDistinct(rma, a) or limbsAliasDistinct(rma, b);
try rma.ensureAliasAwareCapacity(needed, capacity_alias);
var m = rma.toMutable();
if (alias_count == 0) {
m.mulWrapNoAlias(a.toConst(), b.toConst(), signedness, bit_count, rma.allocator);
} else {
const limb_count = calcMulWrapLimbsBufferLen(bit_count, a.len(), b.len(), alias_count);
const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
defer rma.allocator.free(limbs_buffer);
m.mulWrap(a.toConst(), b.toConst(), signedness, bit_count, limbs_buffer, rma.allocator);
}
rma.setMetadata(m.positive, m.len);
}
pub fn ensureTwosCompCapacity(r: *Managed, bit_count: usize) !void {
try r.ensureCapacity(calcTwosCompLimbCount(bit_count));
}
/// True if two distinct `Managed` parameters share the same limbs buffer.
///
/// We specifically exclude the case where `@intFromPtr(a) == @intFromPtr(b)` (same object).
/// When both pointers refer to the same `Managed` instance, `ensureCapacity` can reallocate
/// the buffer (if needed) without creating dangling pointers for that object.
fn limbsAliasDistinct(a: *const Managed, b: *const Managed) bool {
return @intFromPtr(a) != @intFromPtr(b) and a.limbs.ptr == b.limbs.ptr;
}
/// When `aliased` is false (including when both pointers refer to the same object),
/// `ensureCapacity` may reallocate; callers who rely on distinct `Managed` instances
/// aliasing must ensure capacity before aliasing.
/// See https://github.com/ziglang/zig/issues/6167
fn ensureAliasAwareCapacity(r: *Managed, needed: usize, aliased: bool) !void {
if (aliased) {
assert(needed <= r.limbs.len);
} else {
try r.ensureCapacity(needed);
}
}
/// Use this function before doing `addScalar` if some of your parameters alias each other
pub fn ensureAddScalarCapacity(r: *Managed, a: *const Managed, scalar: anytype) !void {
try r.ensureCapacity(@max(a.len(), calcLimbLen(scalar)) + 1);
}
/// Use this function before doing `add` if some of your parameters alias each other
pub fn ensureAddCapacity(r: *Managed, a: *const Managed, b: *const Managed) !void {
try r.ensureCapacity(@max(a.len(), b.len()) + 1);
}
/// Use this function before doing `mul` if some of your parameters alias each other
pub fn ensureMulCapacity(rma: *Managed, a: *const Managed, b: *const Managed) !void {
try rma.ensureCapacity(a.len() + b.len() + 1);
}
/// q = a / b (rem r)
///
/// a / b are floored (rounded towards 0).
///
/// Returns an error if memory could not be allocated.
pub fn divFloor(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try q.ensureAliasAwareCapacity(a.len(), q_alias);
try r.ensureAliasAwareCapacity(b.len(), r_alias);
var mq = q.toMutable();
var mr = r.toMutable();
const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
defer q.allocator.free(limbs_buffer);
mq.divFloor(&mr, a.toConst(), b.toConst(), limbs_buffer);
q.setMetadata(mq.positive, mq.len);
r.setMetadata(mr.positive, mr.len);
}
/// q = a / b (rem r)
///
/// a / b are ceiled (rounded towards positive infinity).
///
/// Returns an error if memory could not be allocated.
pub fn divCeil(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try q.ensureAliasAwareCapacity(a.len(), q_alias);
try r.ensureAliasAwareCapacity(b.len(), r_alias);
var mq = q.toMutable();
var mr = r.toMutable();
const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
defer q.allocator.free(limbs_buffer);
mq.divCeil(&mr, a.toConst(), b.toConst(), limbs_buffer);
q.setMetadata(mq.positive, mq.len);
r.setMetadata(mr.positive, mr.len);
}
/// q = a / b (rem r)
///
/// a / b are truncated (rounded towards -inf).
///
/// Returns an error if memory could not be allocated.
pub fn divTrunc(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try q.ensureAliasAwareCapacity(a.len(), q_alias);
try r.ensureAliasAwareCapacity(b.len(), r_alias);
var mq = q.toMutable();
var mr = r.toMutable();
const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
defer q.allocator.free(limbs_buffer);
mq.divTrunc(&mr, a.toConst(), b.toConst(), limbs_buffer);
q.setMetadata(mq.positive, mq.len);
r.setMetadata(mr.positive, mr.len);
}
/// r = a << shift, in other words, r = a * 2^shift
/// r and a may alias.
pub fn shiftLeft(r: *Managed, a: *const Managed, shift: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = a.len() + (shift / limb_bits) + 1;
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.shiftLeft(a.toConst(), shift);
r.setMetadata(m.positive, m.len);
}
/// r = a <<| shift with 2s-complement saturating semantics.
/// r and a may alias.
pub fn shiftLeftSat(r: *Managed, a: *const Managed, shift: usize, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.shiftLeftSat(a.toConst(), shift, signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = a >> shift
/// r and a may alias.
pub fn shiftRight(r: *Managed, a: *const Managed, shift: usize) !void {
if (a.len() <= shift / limb_bits) {
// Shifting negative numbers converges to -1 instead of 0
if (a.isPositive()) {
r.metadata = 1;
r.limbs[0] = 0;
} else {
r.metadata = 1;
r.setSign(false);
r.limbs[0] = 1;
}
return;
}
const aliased = limbsAliasDistinct(r, a);
const needed = a.len() - (shift / limb_bits);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.shiftRight(a.toConst(), shift);
r.setMetadata(m.positive, m.len);
}
/// r = ~a under 2s-complement wrapping semantics.
/// r and a may alias.
pub fn bitNotWrap(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.bitNotWrap(a.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = a | b
///
/// a and b are zero-extended to the longer of a or b.
pub fn bitOr(r: *Managed, a: *const Managed, b: *const Managed) !void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = @max(a.len(), b.len());
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.bitOr(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a & b
pub fn bitAnd(r: *Managed, a: *const Managed, b: *const Managed) !void {
const cap = if (a.len() >= b.len())
if (b.isPositive()) b.len() else if (a.isPositive()) a.len() else a.len() + 1
else if (a.isPositive()) a.len() else if (b.isPositive()) b.len() else b.len() + 1;
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try r.ensureAliasAwareCapacity(cap, aliased);
var m = r.toMutable();
m.bitAnd(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a ^ b
pub fn bitXor(r: *Managed, a: *const Managed, b: *const Managed) !void {
const cap = @max(a.len(), b.len()) + @intFromBool(a.isPositive() != b.isPositive());
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try r.ensureAliasAwareCapacity(cap, aliased);
var m = r.toMutable();
m.bitXor(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// rma may alias x or y.
/// x and y may alias each other.
///
/// rma's allocator is used for temporary storage to boost multiplication performance.
pub fn gcd(rma: *Managed, x: *const Managed, y: *const Managed) !void {
const aliased = limbsAliasDistinct(rma, x) or limbsAliasDistinct(rma, y);
const needed = @min(x.len(), y.len());
try rma.ensureAliasAwareCapacity(needed, aliased);
var m = rma.toMutable();
var limbs_buffer = std.array_list.Managed(Limb).init(rma.allocator);
defer limbs_buffer.deinit();
try m.gcd(x.toConst(), y.toConst(), &limbs_buffer);
rma.setMetadata(m.positive, m.len);
}
/// r = a * a
pub fn sqr(rma: *Managed, a: *const Managed) !void {
const needed_limbs = 2 * a.len() + 1;
const capacity_alias = limbsAliasDistinct(rma, a);
const same_buffer = rma.limbs.ptr == a.limbs.ptr;
try rma.ensureAliasAwareCapacity(needed_limbs, capacity_alias);
if (same_buffer) {
const a_len = a.len();
const tmp = try rma.allocator.alloc(Limb, a_len);
defer rma.allocator.free(tmp);
@memcpy(tmp[0..a_len], a.limbs[0..a_len]);
const a_const: Const = .{ .limbs = tmp[0..a_len], .positive = a.isPositive() };
var rma_mut = rma.toMutable();
rma_mut.sqrNoAlias(a_const, rma.allocator);
rma.setMetadata(rma_mut.positive, rma_mut.len);
} else {
var rma_mut = rma.toMutable();
rma_mut.sqrNoAlias(a.toConst(), rma.allocator);
rma.setMetadata(rma_mut.positive, rma_mut.len);
}
}
pub fn pow(rma: *Managed, a: *const Managed, b: u32) !void {
const needed_limbs = calcPowLimbsBufferLen(a.bitCountAbs(), b);
const capacity_alias = limbsAliasDistinct(rma, a);
const same_buffer = rma.limbs.ptr == a.limbs.ptr;
try rma.ensureAliasAwareCapacity(needed_limbs, capacity_alias);
const limbs_buffer = try rma.allocator.alloc(Limb, needed_limbs);
defer rma.allocator.free(limbs_buffer);
if (same_buffer) {
const a_len = a.len();
const tmp = try rma.allocator.alloc(Limb, a_len);
defer rma.allocator.free(tmp);
@memcpy(tmp[0..a_len], a.limbs[0..a_len]);
const a_const: Const = .{ .limbs = tmp[0..a_len], .positive = a.isPositive() };
var rma_mut = rma.toMutable();
rma_mut.pow(a_const, b, limbs_buffer);
rma.setMetadata(rma_mut.positive, rma_mut.len);
} else {
var rma_mut = rma.toMutable();
rma_mut.pow(a.toConst(), b, limbs_buffer);
rma.setMetadata(rma_mut.positive, rma_mut.len);
}
}
/// r = ⌊√a⌋
pub fn sqrt(rma: *Managed, a: *const Managed) !void {
const bit_count = a.bitCountAbs();
const aliased = limbsAliasDistinct(rma, a);
if (bit_count == 0) {
try rma.set(0);
rma.setMetadata(a.isPositive(), rma.len());
return;
}
if (!a.isPositive()) {
return error.SqrtOfNegativeNumber;
}
const needed_limbs = calcSqrtLimbsBufferLen(bit_count);
const limbs_buffer = try rma.allocator.alloc(Limb, needed_limbs);
defer rma.allocator.free(limbs_buffer);
const needed = (a.len() - 1) / 2 + 1;
try rma.ensureAliasAwareCapacity(needed, aliased);
var m = rma.toMutable();
m.sqrt(a.toConst(), limbs_buffer);
rma.setMetadata(m.positive, m.len);
}
/// r = truncate(Int(signedness, bit_count), a)
pub fn truncate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.truncate(a.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = saturate(Int(signedness, bit_count), a)
pub fn saturate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.saturate(a.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = @popCount(a) with 2s-complement semantics.
/// r and a may be aliases.
pub fn popCount(r: *Managed, a: *const Managed, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.popCount(a.toConst(), bit_count);
r.setMetadata(m.positive, m.len);
}
}