The builtin u64.isqrt seems to be available in nightly only, and additionally I guess the author didn't want to use any external crates as part of their self-imposed challenge. Though I think there may be an off-by-one result with f64.sqrt I don't think this functionally breaks their u64 code because they loop to root_n + 1.

https://doc.rust-lang.org/std/primitive.u64.html#method.isqrt

[–] blazebra@programming.dev 1 points 6 months ago (4 children)

Algorithm is so plain and simple, it doesn’t require nightly or Rust specifically to implement.

[–] farcaster@lemmy.world 0 points 6 months ago* (last edited 6 months ago) (3 children)

Well, yeah, but you asked why they didn't use integer sqrt. It's something many programming languages just don't have. Or if they do, it's internally implemented as a sqrt(f64) anyway, like C++ does.

Most CPUs AFAIK don't have integer sqrt instructions so you either do it manually in some kind of loop, or you use floating point...

[–] blazebra@programming.dev 1 points 6 months ago (1 children)

Integer sqrt is usually not a library function and it’s very easy to implement, just a few lines of code. Algorithm is well defined on Wikipedia you read a lot. And yes, it doesn’t use FPU at all and it’s quite fast even on i8086.

[–] farcaster@lemmy.world 1 points 6 months ago (1 children)

I doubt doing it in software like that outperforms sqrtss/sqrtsd. Modern CPUs can do the conversions and the floating point sqrt in approximately 20-30 cycles total. That's comparable to one integer division. But I wouldn't mind being proven wrong.

[–] blazebra@programming.dev 2 points 6 months ago

Integer sqrt can be used for integers with any length, not only for integers fit into f64

load more comments (1 replies)