sqrtCommon method

Implementation

F sqrtCommon(F uv, F v) {
  // Helper: repeat squaring
  F sqr(F x, int i) {
    F result = x;
    for (int j = 0; j < i; j++) {
      result = result.square();
    }
    return result;
  }

  // Helper: perfect-hash inverse lookup
  int inv(F x) {
    return this.inv[getHash(x)];
  }

  final x3 = uv * v;
  final x2 = sqr(x3, 8);
  final x1 = sqr(x2, 8);
  final x0 = sqr(x1, 8);

  // i = 0, 1
  int t = inv(x0); // t >> 16
  assert(t < 0x100);
  F alpha = x1 * g2[t];
  // i = 2
  t += inv(alpha) << 8; // t >> 8
  assert(t < 0x10000);
  alpha = x2 * g1[t & 0xFF] * g2[t >> 8];
  // i = 3
  t += inv(alpha) << 16; // t
  assert(t < 0x1000000);
  alpha = x3 * g0[t & 0xFF] * g1[(t >> 8) & 0xFF] * g2[t >> 16];
  t += inv(alpha) << 24; // t << 1
  t = ((t + 1) >> 1); // final t
  assert(t <= 0x80000000);

  return uv *
      g0[t & 0xFF] *
      g1[(t >> 8) & 0xFF] *
      g2[(t >> 16) & 0xFF] *
      g3[t >> 24];
}