Skip to content

Instantly share code, notes, and snippets.

@ShinNoNoir
Last active August 29, 2015 13:57
Show Gist options
  • Select an option

  • Save ShinNoNoir/9460537 to your computer and use it in GitHub Desktop.

Select an option

Save ShinNoNoir/9460537 to your computer and use it in GitHub Desktop.
Very simplistic (and most likely faulty) benchmark test
import Prelude hiding (sqrt)
import Data.List (foldl')
-- NR:
next n x = (x + n/x) / 2
within eps (a:b:rest)
| abs (a-b) <= eps = b
| otherwise = within eps (b:rest)
sqrt a0 eps n = within eps (iterate (next n) a0)
sqrt' eps x = sqrt (x/2) eps x
-- Strict sum (default -O2 flag didn't turn `sum` into strict version)
sum' = foldl' (+) 0
-- Program data:
eps = 0.00001
test = [1..10000000]
main = print $ sum' . map (sqrt' eps) $ test
-- Compile:
-- ghc --make -O2 NewtonRaphson.hs -o /.NewtonRaphson.exe
-- Run:
{-
$ time ./NewtonRaphson.exe
2.1081852648716927e10
real 0m5.219s
user 0m0.000s
sys 0m0.015s
-}
#include <stdio.h>
#include <math.h>
#define EPS 0.00001
#define START 1
#define END 10000000
double nrsqrt(double n, double a0) {
double prev_x;
double x = a0;
do {
prev_x = x;
x = (prev_x + n/prev_x) / 2.0;
} while (fabs(x - prev_x) > EPS);
return x;
}
int main() {
double n;
double sum = 0;
for (n=START; n <= END; n++) {
sum += nrsqrt(n, n/2.0);
}
printf("%f\n", sum);
return 0;
}
/*
Compile:
$ gcc -O2 nr.c -o nr.exe
Run:
$ time ./nr.exe
21081852648.720150
real 0m1.201s
user 0m0.000s
sys 0m0.000s
*/
/*
$ time ./NR.exe
21081852648,717
real 0m2.887s
user 0m0.015s
sys 0m0.000s
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace NewtonRaphson
{
class NR
{
public static void Main()
{
var res = Enumerable.Range(1, 10000000).Select(x => NRSqrt(EPS, x)).Sum();
Console.WriteLine(res);
}
static double EPS = 0.00001;
static double NRSqrt(double a0, double eps, double n)
{
Func<double, double> NRStep = x => (x + n / x) / 2;
return Within(eps, Iterate(NRStep, a0));
}
static double NRSqrt(double eps, double n)
{
return NRSqrt(n / 2.0, eps, n);
}
static IEnumerable<T> Iterate<T>(Func<T, T> f, T x)
{
while (true)
{
yield return x;
x = f(x);
}
}
static double Within(double eps, IEnumerable<double> xs)
{
// Note: You can also get the items pairwise using
// xs.Zip(xs.Skip(1), (a,b) => ...)
// but this will evaluate xs twice!
var it = xs.GetEnumerator();
double a, b;
b = it.Current;
do
{
it.MoveNext();
a = b;
b = it.Current;
} while (Math.Abs(a - b) > eps);
return b;
}
}
}
# Port of the imperative C version
EPS = 0.00001
START = 1
END = 10000000
def sqrt(n, a0):
x = a0
while True:
prev_x, x = x, (x + n/x) / 2.0
if abs(x - prev_x) <= EPS:
return x
if __name__ == '__main__':
print sum(sqrt(x, x/2.0) for x in range(START,END+1))
"""
$ time python ./nr.py
21081852648.7
real 0m38.575s
user 0m0.000s
sys 0m0.031s
$ time pypy ./nr.py
21081852648.7
real 0m2.872s
user 0m0.015s
sys 0m0.000s
"""
// Port of C version:
/*
$ time ./NRImp.exe
21081852648,717
real 0m1.556s
user 0m0.000s
sys 0m0.031s
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace NewtonRaphson
{
class NR
{
static double EPS = 0.00001;
static double START = 1;
static double END = 10000000;
public static void Main()
{
double sum = 0;
for (double n = START; n <= END; n++)
{
sum += NRSqrt(n, n / 2.0);
}
Console.WriteLine(sum);
}
static double NRSqrt(double n, double a0)
{
double prev_x;
double x = a0;
do
{
prev_x = x;
x = (x + n / x) / 2.0;
} while (Math.Abs(x - prev_x) > EPS);
return x;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment