divFloor
q = a / b (rem r)
a / b are floored (rounded towards 0). q may alias with a or b.
Asserts there is enough memory to store q and r.
The upper bound for r limb count is b.limbs.len.
The upper bound for q limb count is given by a.limbs.
limbs_buffer is used for temporary storage. The amount required is given by calcDivLimbsBufferLen.
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 divFloor(
q: *Mutable,
r: *Mutable,
a: Const,
b: Const,
limbs_buffer: []Limb,
) void {
const sep = a.limbs.len + 2;
var x = a.toMutable(limbs_buffer[0..sep]);
var y = b.toMutable(limbs_buffer[sep..]);
div(q, r, &x, &y);
// Note, `div` performs truncating division, which satisfies
// @divTrunc(a, b) * b + @rem(a, b) = a
// so r = a - @divTrunc(a, b) * b
// Note, @rem(a, -b) = @rem(-b, a) = -@rem(a, b) = -@rem(-a, -b)
// For divTrunc, we want to perform
// @divFloor(a, b) * b + @mod(a, b) = a
// Note:
// @divFloor(-a, b)
// = @divFloor(a, -b)
// = -@divCeil(a, b)
// = -@divFloor(a + b - 1, b)
// = -@divTrunc(a + b - 1, b)
// Note (1):
// @divTrunc(a + b - 1, b) * b + @rem(a + b - 1, b) = a + b - 1
// = @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) = a + b - 1
// = @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) - b + 1 = a
if (a.positive and b.positive) {
// Positive-positive case, don't need to do anything.
} else if (a.positive and !b.positive) {
// a/-b -> q is negative, and so we need to fix flooring.
// Subtract one to make the division flooring.
// @divFloor(a, -b) * -b + @mod(a, -b) = a
// If b divides a exactly, we have @divFloor(a, -b) * -b = a
// Else, we have @divFloor(a, -b) * -b > a, so @mod(a, -b) becomes negative
// We have:
// @divFloor(a, -b) * -b + @mod(a, -b) = a
// = -@divTrunc(a + b - 1, b) * -b + @mod(a, -b) = a
// = @divTrunc(a + b - 1, b) * b + @mod(a, -b) = a
// Substitute a for (1):
// @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) - b + 1 = @divTrunc(a + b - 1, b) * b + @mod(a, -b)
// Yields:
// @mod(a, -b) = @rem(a - 1, b) - b + 1
// Note that `r` holds @rem(a, b) at this point.
//
// If @rem(a, b) is not 0:
// @rem(a - 1, b) = @rem(a, b) - 1
// => @mod(a, -b) = @rem(a, b) - 1 - b + 1 = @rem(a, b) - b
// Else:
// @rem(a - 1, b) = @rem(a + b - 1, b) = @rem(b - 1, b) = b - 1
// => @mod(a, -b) = b - 1 - b + 1 = 0
if (!r.eqlZero()) {
q.addScalar(q.toConst(), -1);
r.positive = true;
r.sub(r.toConst(), y.toConst().abs());
}
} else if (!a.positive and b.positive) {
// -a/b -> q is negative, and so we need to fix flooring.
// Subtract one to make the division flooring.
// @divFloor(-a, b) * b + @mod(-a, b) = a
// If b divides a exactly, we have @divFloor(-a, b) * b = -a
// Else, we have @divFloor(-a, b) * b < -a, so @mod(-a, b) becomes positive
// We have:
// @divFloor(-a, b) * b + @mod(-a, b) = -a
// = -@divTrunc(a + b - 1, b) * b + @mod(-a, b) = -a
// = @divTrunc(a + b - 1, b) * b - @mod(-a, b) = a
// Substitute a for (1):
// @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) - b + 1 = @divTrunc(a + b - 1, b) * b - @mod(-a, b)
// Yields:
// @rem(a - 1, b) - b + 1 = -@mod(-a, b)
// => -@mod(-a, b) = @rem(a - 1, b) - b + 1
// => @mod(-a, b) = -(@rem(a - 1, b) - b + 1) = -@rem(a - 1, b) + b - 1
//
// If @rem(a, b) is not 0:
// @rem(a - 1, b) = @rem(a, b) - 1
// => @mod(-a, b) = -(@rem(a, b) - 1) + b - 1 = -@rem(a, b) + 1 + b - 1 = -@rem(a, b) + b
// Else :
// @rem(a - 1, b) = b - 1
// => @mod(-a, b) = -(b - 1) + b - 1 = 0
if (!r.eqlZero()) {
q.addScalar(q.toConst(), -1);
r.positive = false;
r.add(r.toConst(), y.toConst().abs());
}
} else if (!a.positive and !b.positive) {
// a/b -> q is positive, don't need to do anything to fix flooring.
// @divFloor(-a, -b) * -b + @mod(-a, -b) = -a
// If b divides a exactly, we have @divFloor(-a, -b) * -b = -a
// Else, we have @divFloor(-a, -b) * -b > -a, so @mod(-a, -b) becomes negative
// We have:
// @divFloor(-a, -b) * -b + @mod(-a, -b) = -a
// = @divTrunc(a, b) * -b + @mod(-a, -b) = -a
// = @divTrunc(a, b) * b - @mod(-a, -b) = a
// We also have:
// @divTrunc(a, b) * b + @rem(a, b) = a
// Substitute a:
// @divTrunc(a, b) * b + @rem(a, b) = @divTrunc(a, b) * b - @mod(-a, -b)
// => @rem(a, b) = -@mod(-a, -b)
// => @mod(-a, -b) = -@rem(a, b)
r.positive = false;
}
}