Golang: Newton’s algorithm


Task number 8 in golang tour…

Cycles and functions

To play with functions and loops, let’s implement the square root function: Given a number x, we want to find the number z for which z² is closest to x.

Computers usually calculate the square root of x using a loop. Starting with some assumed z, we can adjust z based on how close z² is to x, getting a better guess:

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

igroglaz’ note:

This is wildly incomprehensible to beginners in general. It is better to take understandable variables instead of those abstract z and x. For example, let z be guess (i.e. the number that our algorithm will offer as a “clue”), and x be num (i.e. the number for which we need to find the root). Then the formula becomes readable:

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

By repeating this adjustment, we make the guess better and better until we get an answer that is as close to the real square root as possible.

Implement this in func Sqrt. A decent initial value for z is 1, regardless of the initial data. To start, repeat the calculation 10 times and output each z. See how close you get to the answer for different values of x (1, 2, 3, …) and how quickly the guessing improves.

Tip: To declare and initialize a floating-point value, give it floating-point syntax or use a transformation:

z := 1.0
z := float64(1)

Next, change the loop condition so that it stops as soon as the value stops changing (or changes only by a very small amount). See if it is more or less than 10 iterations. Try other initial values for z, such as x or x/2. How close are the results of your function to math.Sqrt from the standard library?

(Note: if you’re interested in the details of the algorithm, z² – x above is how far z² is from where it should be (x), and dividing by 2z is the derivative of z² to scale how much we adjust z by the rate of change of z². This general approach is called Newton’s method. It works well for many functions, but especially well for the square root).

Solution

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))
}

 


This entry was posted in Go (en). Bookmark the permalink.

Leave a Reply

🇬🇧 Attention! Comments with URLs/email are not allowed.
🇷🇺 Комментарии со ссылками/email удаляются автоматически.