• Bazebara
    link
    22 months ago

    Nice article, I enjoyed it. Why float sqrt has been used? Integer sqrt is way faster and easily supports integers of any lengths

    • @[email protected]OP
      link
      fedilink
      1
      edit-2
      2 months ago

      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

      • Bazebara
        link
        12 months ago

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

        • @[email protected]OP
          link
          fedilink
          0
          edit-2
          2 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…

          • Bazebara
            link
            12 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.

            • @[email protected]OP
              link
              fedilink
              12 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.

              • Bazebara
                link
                22 months ago

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