QRat update

[Dom DiSc]

On Wednesday, 16 August 2023 at 14:09:41 UTC, H. S. Teoh wrote:
> Unfortunately I couldn't implement .sqrt for BigInt 
> coefficients yet, because currently there isn't an efficient 
> BigInt square root function. (I'd implement one myself, but 
> then I wouldn't be sure whether it would perform well.)

```d
/// biggest integer with r^2 <= n
T sqrt(T)(T n) if(isUnsigned!T)
{
    if(n<2) return n; // trivial cases: sqrt(1) = 1 and sqrt(0) = 0

    uint pos = (bitlen(n)-1)>>1; // root has half the bitlen
    T r, s, t;
    r.bit[pos] = true;
    s.bit[pos<<1] = true; // s and t are used for extra fast 
squaring
                          // of a number with only one additional 
bit set
    while(pos--)
    {
       s.bit[pos<<1] = true;
       t = r; t <<= pos+1; t += s;
       if(t > n)
       {
          s.bit[pos<<1] = false;
          continue;
       }
       r.bit[pos] = true;
       if(!pos) return r;

       s = t; t -= n;
       if(!t) return r;

       if(pos > ((bitlen(t)-1)>>1))
          pos = (bitlen(t)-1)>>1;
    }
    return r;
}
```

This will work also with Bigint and will be reasonable fast.