Function divFloor [src]

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.

Prototype

pub fn divFloor( q: *Mutable, r: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, ) void

Parameters

q: *Mutabler: *Mutablea: Constb: Constlimbs_buffer: []Limb

Source

  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;
    }
}  