Archive

Archive for the ‘math’ Category

The square root function using Newton’s method

February 3, 2014 1 comment

Newton’s method approximates Sqrt(x) by picking a starting point z (e.g. 1.0) and then repeating:
newton

Let’s see an implementation in Go. We repeat until the value only changes a very small delta. The number of steps is also displayed.

package main

import (
    "fmt"
    "math"
)

func Sqrt(x float64) float64 {
    prev, z := 1.0, 1.0
    const delta = 0.000000000001
    steps := 0
    for {
        z -= (z*z-x) / (2*z)
        if math.Abs(prev-z) < delta {
            break
        }
        prev = z
        steps++
    }
    fmt.Println("# steps:", steps)
    return z
}

func main() {
    n := float64(7)
    fmt.Println(Sqrt(n))
    fmt.Println(math.Sqrt(n))
}

Hmm, it seems WordPress.com doesn’t support Go syntax highlighting :(

Output for Sqrt(7):

# steps: 6
2.6457513110645907
2.6457513110645907

Idea from here: http://tour.golang.org/#25

Categories: golang, math Tags: , ,

Miller-Rabin primality test

A very efficient way for testing if a large number is a prime or not is the Miller-Rabin primality test.

Python code is here.

Wikipedia entry is here.

Categories: math Tags: ,

Prime factors of a number

June 25, 2012 Leave a comment

Guess what. There is a Unix command for this too… It is called “factor”.

Usage:

factor 36

Output:

36: 2 2 3 3

What is a prime factor?

Categories: math Tags:

Generate primes

June 25, 2012 Leave a comment

Today I learnt that there is a Unix command for generating primes called “primes”…

Installation:

sudo apt-get install bsdgames

Usage:

primes 1 100

Upper limit: 4,294,967,295. More info: “man primes”.

Categories: math Tags:

The Batman Equation

April 30, 2012 Leave a comment

Click on the image for more info. Thanks Jeszy for the link.

Categories: math Tags: ,

Calculating the average incrementally

April 25, 2012 Leave a comment

This entry is based on Sándor Norbert’s post on Incremental average calculation.

Problem
I have a large list with very large numbers and I want to calculate their average. However, I’m afraid there would be an overflow while summing up the elements.

Solution
The traditional average computation first calculates the sum of the elements and then this sum is divided by the number of elements. However, the average can be calculated incrementally too, i.e. you take the 1st element and you calculate its average, then take the 2nd element and update the average, and so on. When you process the last element, you have the average of the whole list. Let’s see it mathematically.

Recall the traditional average:


Now let’s see the incremental formula:


That is:


Thus, the average up to i elements:


The algorithm in Python:

def inc_avg(li):
    """Calculate the average incrementally.
    Input: a list.
    Output: average of the list."""
    left = 0
    right = len(li)-1

    avg = li[left]
    left += 1

    while left <= right:
        curr = left + 1
        avg += (li[left] - avg) / float(curr)
        left += 1

    return avg

Experimental results
TODO: compare the runtime of plain average with this incremental solution.

Categories: math, python Tags: ,
Follow

Get every new post delivered to your Inbox.

Join 61 other followers