llmulacc
Knuth 4.3.1, Algorithm M.
r = r (op) a * b r MUST NOT alias any of a or b.
The result is computed modulo r.len. When r.len >= a.len + b.len, no overflow occurs.
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 llmulacc(comptime op: AccOp, opt_allocator: ?Allocator, r: []Limb, a: []const Limb, b: []const Limb) void {
assert(r.len >= a.len);
assert(r.len >= b.len);
assert(!slicesOverlap(r, a));
assert(!slicesOverlap(r, b));
// Order greatest first.
var x = a;
var y = b;
if (a.len < b.len) {
x = b;
y = a;
}
k_mul: {
if (y.len > 48) {
if (opt_allocator) |allocator| {
llmulaccKaratsuba(op, allocator, r, x, y) catch |err| switch (err) {
error.OutOfMemory => break :k_mul, // handled below
};
return;
}
}
}
llmulaccLong(op, r, x, y);
}