lldiv1
Knuth 4.3.1, Exercise 16.
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
fn lldiv1(quo: []Limb, rem: *Limb, a: []const Limb, b: Limb) void {
assert(a.len > 1 or a[0] >= b);
assert(quo.len >= a.len);
rem.* = 0;
for (a, 0..) |_, ri| {
const i = a.len - ri - 1;
const pdiv = ((@as(DoubleLimb, rem.*) << limb_bits) | a[i]);
if (pdiv == 0) {
quo[i] = 0;
rem.* = 0;
} else if (pdiv < b) {
quo[i] = 0;
rem.* = @as(Limb, @truncate(pdiv));
} else if (pdiv == b) {
quo[i] = 1;
rem.* = 0;
} else {
quo[i] = @as(Limb, @truncate(@divTrunc(pdiv, b)));
rem.* = @as(Limb, @truncate(pdiv - (quo[i] *% b)));
}
}
}