How hard can generating 1024-bit primes really be? (glitchcomet.com)

submitted 6 months ago by farcaster@lemmy.world to c/rust@programming.dev

11 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

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

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

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

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.