Самый быстрый способ получить целую часть sqrt (n)?

Question

Как мы знаем, если n не является идеальным квадратом, то sqrt(n) не будет целым числом.Поскольку мне нужна только целая часть, я чувствую, что вызов sqrt(n) не будет таким быстрым, так как для вычисления дробной части требуется время.

Итак, мой вопрос:

Можем ли мы получить только целую часть sqrt (n) без вычисления фактического значения sqrt(n)?Алгоритм должен быть быстрее, чем sqrt(n) (определено в <math.h> или <cmath>)?

Если возможно, вы также можете написать код в блоке asm.

Answer 1

Если вам нужна производительность при вычислении квадратного корня, я думаю, вы будете вычислять многие из них. Тогда почему бы не кэшировать ответ? Я не знаю диапазон для N в вашем случае, и если вы будете много раз вычислять квадратный корень одного и того же целого числа, но если да, то вы можете кэшировать результат каждый раз, когда вызывается ваш метод (в массиве будет самый эффективный, если не слишком большой).