Здравствуйте!
Взбрендило мне для расчета целочисленного квадратного корня ("пол" sqrt(x)) написать целочисленный же алгоритм. Зачем-то я начал пытаться использовать для этого алгоритм Ньютона, притом вот какой:
public static long isqrt_newton_simple(long num)
{
long xPrev = 0, xCur = num;
while (true)
{
xPrev = xCur;
xCur = (xPrev + num / xPrev) / 2;
if (xCur == xPrev)
return xCur;
else if (xCur > xPrev)
return xPrev;
}
}
Ну, думал, облом.
Но чудесы великия!
Алгоритм дает верное значение для целой части квадратного корня, хотя бы на диапазоне 32-битного типа int.
Но я, увы, не математик, и мне становится печально, как только я подумаю о доказательстве сходимости метода к целой части квадратного корня. Есть ли у Вас какие-то идеи? Бестолковый метод или толковый? Почему?
