Mathematics in Programming

1. 牛顿迭代法和TAYLOR 级数可以解决大部分方程求解问题,函数近似问题。

Example: sqrt()函数

public static double sqrt ( double c )
{
  if (c < 0) return Double.NaN;
  double err = 1e-15;
  double t = c;
  while (Math.abs(t - c/t) > err * t)
    t = (c/t + t) / 2.0;
  return t;
}

//QUAKE3中用的计算参数x的平方根的倒数函数,该函数的相对误差约为0.177585%

float InvSqrt (float x)
{
  float xhalf = 0.5f*x;
  int i = *(int*)&x;
  i = 0x5f3759df - (i >> 1); // 计算第一个近似根
  x = *(float*)&i;
  x = x*(1.5f - xhalf*x*x); // 牛顿迭代法
  return x;
}

2. 随机数相关问题

//Random int value drawn from discrete distribution (i with probability a[i])

public static int discrete(double[] a)
{ // Entries in a[] must sum to 1.
 double r = StdRandom.random();
 double sum = 0.0;
 for (int i = 0; i < a.length; i++)
 {
 sum = sum + a[i];
 if (sum >= r) return i;
 }
 return -1;
}

//randomly shuffle the elements in an array of  double values

public static void shuffle(double[] a)
{
 int N = a.length;
 for (int i = 0; i < N; i++)
 { // Exchange a[i] with random element in a[i..N-1]
   int r = i + StdRandom.uniform(N-i);
   double temp = a[i];
   a[i] = a[r];
   a[r] = temp;
 }
}

 


		
Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s