Integer sqrt in stdlib

Crystal Contrib
41

If you want a fluent interface, you can always do something like:

module Fluent
  macro extended
    {% for method in Math.methods.map(&.name).sort.uniq %}
      def {{method.id}}(*args)
        Math.{{method.id}}(self, *args)
      end
    {% end %}
  end
end
 
struct Float64
  extend Fluent
end
 
puts 0.5253.acos.cos #=> 0.5253

and then

struct Int32
  extend Fluent
end
 
puts 16.isqrt.gcd(8) #=> 4
1 Like
42

The discussion whethere it belongs in Math module or number types doesnā€™t belong here. If you want to change that, that should be discussed in general and apply to all Math methods that already exist.

For now, the method should be in the same namespace as the existing sqrt, that is Math.isqrt. Althoughā€¦ maybe we could also consider a more descriptive name :man_shrugging:

1 Like
43

Hey @asterite Iā€™ve been trying to figure out the Crystal codebase enough to understand how to create a PR and all the places the pieces need to go. Itā€™s been very frustrating, because the more I try the less I seem to understand.

It may be better for someone who knows their way around the codebase and github to do it (correctly), in a shorter time than I can figure it out myself. I can supply test cases though.

Also @tsundsted, I tried your fluent code and it works nice, but itā€™s way over my head, and seems like wizards work. Thereā€™s allot of deep stuff going on there, on many levels, I would love for you to explain in more detail. However, it seems to effectively create the means to have UFCS code capabilities.

Is this something each user would have to put in their code or can this be implemented at the language level to provide it universally out of the box?

Can I urge you to write a Crystal blog article explaining it. Iā€™m sure Iā€™m not the only one who would want its features, and putting an article on the Crystal site makes it permanently accessible for everyone, especially those new to the language.

44

Sure, donā€™t worry. If someone has time they will create the PR for Math.isqrt.

1 Like
45

I substituted the bit_length method in the just released 0.34, and it works like a charm. :grin:

2 Likes
46

Did Integer sqrt get added to stdlib?
If so its not in https://crystal-lang.org/api/0.35.1/Math.html

If not, can it be added before 1.0 (to match Ruby compatibility, et al).

47

There hasnā€™t been any progress on this: https://github.com/crystal-lang/crystal/issues/8920

That said, this can be a shard or just live in your project.

48

Part of the earlier discussion was about creating a proper bit_length method, which has been done and added to the stlib.

The other was what the formal name should be.
But per this earlier code to implement it, it would be in the Math module:

module Math
  def isqrt(n: Int)         # Newton's method for Integer squareroot
    raise ArgumentError.new "Input must be non-negative integer" if n < 0
    return n if n < 2
    b = n.bit_length 
    one = typeof(n).new(1)  # value 1 of type self
    x = one << ((b - 1) >> 1) | n >> ((b >> 1) + 1)
    while (t = n // x) < x
      x = (x + t) >> 1 
    end
    x                       # ouput same Integer type as input
  end
end

Per the discussion for adding this, Math.sqrt produces floating point errors after a certain size, which is why I got Ruby to include an accurate Integer sqrt version.

For the same mathematical reasons, and for compatibility with Ruby, I think this method needs to be added to Crystal, under whatever name you give it.

1 Like