Integer square root

1

Is there a good integer square root function around somewhere? Is this something that would be useful for num::Integer?

*added link

2

Does having square root makes sense for Integer? What does it return? f32-64?

3

I mean the integer square root function, which would return a number of the same type as the one given.

For positive integers, this would mean, for n = isqrt(x) that n*n <= x and (n+1)*(n+1) >= x. I don't know what a sensible return value would be for negative numbers.

1 Like
4

There's always (x as f64).sqrt() as i32 (or whatever integer type you have), using std::num::Float.

5

Yes - but for i64 that would give unreliable results, right?

Also, is that guaranteed accurate for i32, or for large numbers might it occasionally give the wrong answer for large numbers, due to floating point errors? I know an i32 fits in an f64, but might the floating point errors occasionally push it the wrong direction?

6

There may be off-by-one errors for numbers larger than 253, yes. (FWIW, I don't know of any language that provides integer square roots in the standard library, I definitely encourage things like this to be put into external libraries on crates.io.)

7

What would you use it for? I was thinking maybe for laying stuff out in a square table, but for that you'd need the smallest integer larger than the square root, not the largest integer smaller than the square root...

If it's mainly for number theory, it probably belongs grouped with similar number theory functions in a library for that purpose. (and probably in Haskell)

8

And I'm going to feel like a moron if floor(sqrt(N)) + 1 > sqrt(N) is a trivial theorem that I am just too lazy to prove this morning :slight_smile:

9

(It is trivial, floor(x) + 1 > x is true for all x. :wink: In any case, floor(sqrt(N)) + 1 isn't right always: e.g. N = 4.)

10

I just checked: @huon is right, (x as f64).sqrt() as i32 is correct for all x <= 1 << 52. Well, actually I just checked

for n in range 1..(1 << 26){
    verify(n*n-1);
    verify(n*n);
    verify(n*n+1);
}

but I figure that should do it.

Thanks!

11

If your goal is to iterate 1 through sqrt(N), you can alternatively limit an existing range:

for i in (1u32..).take_while(|x| x * x <= 42) {
    println!("{}", i*i);
}
1 Like