C#. Длинная арифметика. Урок 12. Вычисление квадратного корня по формуле Герона

Длинная арифметика   24 сентября 2013  Автор статьи:  

Очень часто возникает задача найти целочисленное значение квадратного корня. В этой статье мы научимся это делать на основе формулы Герона. Данная формула позволяет строить ряд, который очень быстро сходиться к ответу.
Xn+1 = (Xn + (a / Xn) / 2
где Xn — n-ый член ряда, a — число из которого мы хотим извлечь квадратный корень.
Так как данная формула является итерационной, то мы должны понять, когда мы будем останавливаться и говорить, что этот член ряда и есть наш ответ. Логично ввести два ограничения:

  • Если следующий член ряда равен предыдущему, то мы нашли ответ и выполнять какие — то еще действия не имеет смысла.
  • Если мы выполнили уже достаточное количество шагов(например тысячу) и нам хватит точности с которой был определен результат.

Можно было бы обобщить первое условия, ввести эпсилон, т.е. погрешность вычислений и если следующий член отличался бы от предыдущего на числа меньшее чем эпсилон, то выдавать ответ, иначе продолжать вычисления.
Так как мы строим ряд, то мы должны знать, а чему будет равен первый его элемент. Можно, конечно, воспользоваться формулами приближенного вычисления корня, но достаточно просто взять его за 1 и позволить формуле самой вычислить за нас корень.
Еще раз хочу заметить, что ряд сходиться достаточно быстро, притом всегда можно установить ограничение на количество итераций или ввести эпсилон, поэтому для поиска корня до 100 знаков в числе данный метод работает достаточно шустро.
Так как в данном цикле уроков мы пишем свой класс для длинной арифметики, то продолжим его дописав два метода:

public static BigInteger SqrtByGeron(BigInteger a)
{
return GeronFunction(a, new BigInteger("1"), 1, 1000);
}

private static BigInteger GeronFunction(BigInteger a, BigInteger b, int shag, int n)
{
int r = 0;
BigInteger ans = (b.Add(a.Div(b))).Divide(2, out r);
if (shag >= n || ans.Substract(b).CompareTo(BigInteger.One)==0)
{
return ans;
}
return GeronFunction(a, ans, shag + 1, n);
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++