llsquareBasecase
r MUST NOT alias x.
Function parameters
Parameters
- r:[]Limb
- x:[]const Limb
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 llsquareBasecase(r: []Limb, x: []const Limb) void {
const x_norm = x;
assert(r.len >= 2 * x_norm.len + 1);
assert(!slicesOverlap(r, x));
// Compute the square of a N-limb bigint with only (N^2 + N)/2
// multiplications by exploiting the symmetry of the coefficients around the
// diagonal:
//
// a b c *
// a b c =
// -------------------
// ca cb cc +
// ba bb bc +
// aa ab ac
//
// Note that:
// - Each mixed-product term appears twice for each column,
// - Squares are always in the 2k (0 <= k < N) column
for (x_norm, 0..) |v, i| {
// Accumulate all the x[i]*x[j] (with x!=j) products
const overflow = llmulLimb(.add, r[2 * i + 1 ..], x_norm[i + 1 ..], v);
assert(!overflow);
}
// Each product appears twice, multiply by 2
_ = llshl(r, r[0 .. 2 * x_norm.len], 1);
for (x_norm, 0..) |v, i| {
// Compute and add the squares
const overflow = llmulLimb(.add, r[2 * i ..], x[i..][0..1], v);
assert(!overflow);
}
}