lapets/isqrt

Efficient pure-Python implementation of the integer square root function.

isqrt's Issues

isqrt is slow

It is faster for scipy to compute lambertw than for this to compute isqrt.

You should bind to C and do it there. Supporting python's big int looks like the main difficulty of porting the code.

linear running time performance claim is inaccurate

A minor documentation bug: the claim in the README that

The running time is linear in the bit length of the input integer

is not quite correct. The operation count (that is, counting Python-level operations) is certainly linear, but some of those operations themselves have linear running time - the most obvious being the subtraction in the line rmdr -= cand * bit_next. Maybe the statement could be corrected to something like "The number of operations is linear in the bit length of the input integer."?