Язык Go. Алгоритм Ньютона

Задание нумер 8 в Го Туре…

Циклы и функции

Чтобы поиграть с функциями и циклами, давайте реализуем функцию квадратного корня: задав число x, мы хотим найти число z, для которого z² наиболее близок к x.

Компьютеры обычно вычисляют квадратный корень из x с помощью цикла. Начиная с некоторого предполагаемого z, мы можем скорректировать z, основываясь на том, насколько близко z² к x, получая лучшее предположение:

z -= (z * z - x) / (2 * z)

Примечание Игроглаза:

вообще это дико непонятно новичкам. Лучше вместо этих абстрактных z и x брать понятные переменные. Например, пусть z будет guess (т.е. число, которое наш алгоритм будет предлагать в качестве «отгадки»), а x будет num (т.е. число, для которого нужно найти корень). Тогда формула становится читаемой:

guess -= (guess * guess - num) / (2 * guess)

Повторяя эту корректировку, мы делаем предположение все лучше и лучше, пока не получим ответ, максимально приближенный к реальному квадратному корню.

Реализуйте это в func Sqrt. Приличное начальное значение для z равно 1, независимо от исходных данных. Для начала повторите вычисления 10 раз и выведите каждое z. Посмотрите, насколько близко вы подошли к ответу для различных значений x (1, 2, 3, …) и как быстро улучшается угадывание.

Подсказка: Чтобы объявить и инициализировать значение с плавающей точкой, задайте ему синтаксис с плавающей точкой или используйте преобразование:

z := 1.0
z := float64(1)

Далее измените условие цикла так, чтобы он останавливался, как только значение перестанет меняться (или изменится только на очень маленькую величину). Проверьте, будет ли это больше или меньше 10 итераций. Попробуйте другие начальные значения для z, например, x или x/2. Насколько близки результаты вашей функции к math.Sqrt из стандартной библиотеки?

(Примечание: если вас интересуют детали алгоритма, то z² — x выше — это то, насколько далеко z² находится от того места, где он должен быть (x), а деление на 2z — это производная z², чтобы масштабировать то, насколько сильно мы корректируем z по скорости изменения z². Этот общий подход называется методом Ньютона. Он хорошо работает для многих функций, но особенно хорошо для квадратного корня).

Решение:

package main

import (
	"fmt"
	"math"
)

func Sqrt(num float64) float64 {
	guess := 1.0
	i := 0
	for {
		i++
		guess -= (guess*guess - num) / (2 * guess)
		fmt.Println("Attemps #", i, " ", guess)
		if guess == math.Sqrt(num) {
			break
		}
	}
	return guess
}

func main() {
	fmt.Println("Our func (Newton alg): ", Sqrt(424242))
	fmt.Println("Golang math.Sqrt func: ", math.Sqrt(424242))
}