Implementing Gauss–Legendre algorithm using arbitrary-length rationals
It sounds like you are using arbitrary-precision arithmetic, i.e., you represent each rational number as a ratio $a/b$ where $a,b$ are stored as arbitrary size integers (bignums).  If that's the case, that's probably the source of your problem.

Don't do that.  That's highly inefficient, because you'll end up with very large integers $a,b$, that may be far larger than needed for the desired precision level; and it'll be imprecise, because of the ⌊√a⌋/⌊√b⌋ problem you mention.

Instead, use fixed-precision arithmetic: each number is represented directly as a number (not a ratio) using a fixed-precision representation.  That will be much more efficient and more accurate.  It won't have the problem of ⌊√a⌋/⌊√b⌋, since you're not limited to a ratio of integers.  You might need to find a library that implements fixed-precision arithmetic, or to implement that part yourself, and you'll probably need to estimate the appropriate precision level based on the number of iterations and the amount of precision achievable with that given precision level.