Sunday, April 20, 2014

Java Source Code: Arrays

Arrays is a tool class to perform operations on array. Roughly speaking, it contains the following methods:
1. sort: QuickSort for primitive type; other types(Object) are sorted by TimSort
2. copy: copyOf and copyOfRange
• they actually call System.arraycopy to do the real work
• System.arraycopy is a native method that is supposed to be faster than copying position by position
3. binarySearch: regular one as follows:
• it assumes array has been sorted before calling binarySearch
 int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}

4. equals: shallow check, just check elements in the first level
5. deepEquals: deep check, go deep inside until finding a element that is applicable to equals
6. fill: fill the whole array or a sub sequence by a value
• it's done position by position, no magic here
7. hashcode and toString: iterate over elements
• hashcode also has deep and shallow versions

Saturday, April 12, 2014

Newton's Methond - (3)

Note that there exists disparity of Newton's Method in between calculus and optimization.
Newton's Method in calculus aims to find $x^*$ such that $f(x^*) = 0$.
While in terms of optimization field, we actually would like to maximize(or minimize) $f(x)$. The problem ends up finding $x^*$ such that $f'(x^*) = 0$.

The following is an easy way to conceptually understand Newton's Method in optimization.
If we denote $f'(x)$ as $g(x)$ and then use Newton's Method to solve $x^*$ such that $g(x^*) = 0$.
Thus we will have the following update rule:
$$x^{(n+1)} = x^{(n)} - \frac{g(x^{(n)}}{g'(x^{(n)})}$$
Put $f'(x)$ back, we get
$$x^{(n+1)} = x^{(n)} - \frac{f'(x^{(n)}}{''(x^{(n)})}$$

Note that Quasi-Newton Method is another way to optimize, which won't explicitly compute the second-order derivative.

Newton's Method - (2)

The convergence of Newton's Method. As before, we also expand $f(x^*)$ at the current $x$. We get
\begin{align}
f(x^*) = 0 = f(x) + f'(x)(x^*-x) + \frac{1}{2}f''(x)(x^*-x)^2
\end{align}
Suppose this second-order approximation is good enough, which requires $x$ is not too far away from $x^*$ originally.
Then we divide (1) by $f'(x)$(assume that $f'(x) \ne 0$), we will have
\begin{align}
\frac{f(x)}{f'(x)} + x^* - x = -\frac{f''(x)}{2f'(x)}(x^* - x)^2
\end{align}
Note that the new $x'$ is going to be update as $x - \frac{f(x)}{f'(x)}$. (2) therefore becomes
\begin{align*}
x^* - x'  & = -\frac{f''(x)}{2f'(x)}(x^* - x)^2 \\
& \implies |x^* - x'| = |\frac{f''(x)}{2f'(x)}||x^* - x|^2
\end{align*}
Denote $|x^* - x'|$ as $\Delta'$ and $|x^* - x|$ as $\Delta$. We get
\begin{align}
\Delta' = |\frac{f''(x)}{2f'(x)}|\Delta ^2
\end{align}
(3) shows the rate of convergence is quadratic if
1. $f'(x) \ne 0$
2. $f''(x)$ is finite
3. $x^{(0)}$(the initial guess) should be sufficiently close to $x^*$

Friday, April 11, 2014

Newton's Method - (1)

First note that we have Newton's Method in calculus and in optimization. Generally, Newton's Method is the one in calculus, which aims to find $x^*$ such that $f(x^*)=0$.

Suppose we are now at $x = x^* + h$ and expanding $f(x)$ at point $x^*$. We will get
\begin{align}
f(x) = f(x^*+h) & = f(x^*) + f'(x^*)h
\end{align}

Since $f(x^*)=0$, (1) becomes $f(x) = f'(x^*)h$. Then $h = \frac{f(x)}{f'(x^*)}$. To update, we set the new $x'$ as $x-h=x- \frac{f(x)}{f'(x^*)}$.

Because we have to get $f'(x^*)$, which is basically impossible to do, this method doesn't work.

Then we alter to expand $f(x^*)$ at point $x$, that is
\begin{align}
f(x^*) = f(x-h) & = f(x) + f'(x)(-h) \\
&= f(x) + f'(x)(-h) + \frac{1}{2}f''(x)h^2
\end{align}

In terms of (2), we have
$$f(x^*) = 0 = f(x) + f'(x)(-h) \implies h = \frac{f(x)}{f'(x)}.$$
So, the new $x'$ will be updated as $x-h = x - \frac{f(x)}{f'(x)}.$

If we consider (3), we will get
\begin{align*}
f(x^*) = 0  & = f(x) + f'(x)(-h) + \frac{1}{2}f''(x)h^2 \\
& \implies h = \frac{f'(x) \pm \sqrt{(f'(x))^2 - 2f''(x)f(x)}}{f''(x)}
\end{align*}

Since we have multiple choices to update $x$, this method actually won't work.

Friday, April 4, 2014

Jave Souece Code: Hash Functions

Hash function for String and other classes that have multiple variables such as List is defined recursively. However, they are not completely the same.
The code for String's hash function is shown as following:
1:  public int hashCode() {
2:    int h = hash;
3:    if (h == 0 && value.length > 0) {
4:      char val[] = value;
5:      for (int i = 0; i < value.length; i++) {
6:        h = 31 * h + val[i];
7:      }
8:      hash = h;
9:    }
10:    return h;
11:  }

The computational strategy is $$s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1],$$ where $s$ is the underlying char array of the String object. $s[i]$ is the corresponding char value.
We are also able to find out that the hash value for a String object is going to be calculated and stored only once.

Then the code for List's hash function is followed as:
1:    public int hashCode() {
2:      int hashCode = 1;
3:      for (E e : this)
4:        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
5:      return hashCode;
6:    }

It is defined recursively as $$31^{n} + v_0*31^{(n-1)} + v_1*31^{(n-2)} + ... + v_{n-1},$$ where $v_0, v_1, ..v_{n-1}$ are the variables. Without having the property of immutability of String, $v_1, v_2, ...v_{n-1}$ might change during running time. Thus at each time when hash function is called, the hash value will be recalculated as above.

Let's boil down some essence from the following code.
1:  Integer [] is1 = new Integer[]{1};
2:  Integer [] is2 = new Integer[]{1};
3:  ArrayList<Integer> ls1 = new ArrayList<Integer>(Arrays.asList(is1));
4:  ArrayList<Integer> ls2 = new ArrayList<Integer>();
6:  System.out.println(is1.hashCode());
7:  System.out.println(is2.hashCode());
8:  System.out.println(Arrays.hashCode(is1));
9:  System.out.println(ls1.hashCode());
10:  System.out.println(ls2.hashCode());

The result is as
481088980
386555905
32
32
32.

The reason why two random number "481088980" and "386555905" show up is that actually the native Object's hash function has been called. "Native" represents the implementation involves with the platform. A standard way to obtain the hash value of a array is Arrays.hashCode(), which looks like
1:  public static int hashCode(Object a[]) {
2:    if (a == null)
3:      return 0;
4:    int result = 1;
5:    for (Object element : a)
6:      result = 31 * result + (element == null ? 0 : element.hashCode());
7:    return result;
8:  }


It's easy to know hash functions for List and Array actually encodes the same idea to compute hash value.
32 follows from $31^1 + 1 * 31^0 = 32$ for "is1", "ls1" and "ls2".

Thursday, April 3, 2014

Java Source Code: the Implementation of Class Integer - (1)

In a previous blog, Integer's property of immutability has been discussed extensively. Basically, immutability is implemented by some declarations involving with private and final variable and even the way of just exposing a getting interface.

In this blog, we plan to discuss more.
First, let's focus on the amazing implementation of "toString" method. The source code is shown following:
1:  public static String toString(int i) {
2:    if (i == Integer.MIN_VALUE)
3:      return "-2147483648";
4:    int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
5:    char[] buf = new char[size];
6:    getChars(i, size, buf);
7:    return new String(buf, true);
8:  }


• The reason for dealing with the special case of Integer.MIN_VALUE is that it does not have the corresponding absolute value. Note that the range of Integer(int) is from $-2^{31}$ to $2^{31}-1$.

Then we go deeper insider to take a look at getChars method. It looks like as following:
1:  static void getChars(int i, int index, char[] buf) {
2:    int q, r;
3:    int charPos = index;
4:    char sign = 0;
5:    // here is why Integer.MIN_VALUE lets getChars fail,
6:    if (i < 0) {
7:      sign = '-';
8:      i = -i;
9:    }
10:    // Generate two digits per iteration
11:    while (i >= 65536) {
12:      q = i / 100;
13:      r = i - ((q << 6) + (q << 5) + (q << 2));
14:      i = q;
15:      buf [--charPos] = DigitOnes[r];
16:      buf [--charPos] = DigitTens[r];
17:    }
18:    // Fall thru to fast mode for smaller numbers
19:    // assert(i <= 65536, i);
20:    for (;;) {
21:      q = (i * 52429) >>> (16+3);
22:      r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
23:      buf [--charPos] = digits [r];
24:      i = q;
25:      if (i == 0) break;
26:    }
27:    if (sign != 0) {
28:      buf [--charPos] = sign;
29:    }
30:  }


• The first trick used here is at line 13. We show that $100=64+32+4=2^6+2^5+2^2$. Note that if you have to multiply a moderately large number many times, this trick is highly recommended to apply.
• After line 13, it is actually the last two digits of i. Then owing to two pre-defined tables, we are able to get the corresponding digit in constant time. The underlying idea is to cope with two digits at one time. For example, the last two digits are 27.  DigitOnes[27] returns 7 and DigitTens[r] returns 2.
• 1:  final static char [] DigitTens = {
2:    '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
3:    '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
4:    '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
5:    '3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
6:    '4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
7:    '5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
8:    '6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
9:    '7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
10:    '8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
11:    '9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
12:    } ;
13:  final static char [] DigitOnes = {
14:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
15:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
16:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
17:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
18:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
19:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
20:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
21:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
22:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
23:    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
24:    } ;  
• The number 52429 looks so wired here. In fact, it comes from $\lceil \frac{2^{16+3}}{10}\rceil$. What line 21 aims to do is $q = i * 0.1$.
• But as we can see, i is probably 65537 and therefore $65537*52429=3436039373$. Overflow! However, surprisingly, $(65537*52429)>>>19=6553$. Even overflow affects nothing. However again, if we set i as 80000,  $(80000*52429)>>>19 \ne 8000$.
• I also try to do some potential improvements based on this code. I find we can continue to pull down the line before we stop the phase of deal with two digits at one time. I set is as 1024. Then the line 21 becomes
• 21:    q = (i * 3355444) >>> (25);

•  Some simple experiments have been performed and I find this modification indeed improves a little bit.

Java Source Code: How immutability works

The immutable type in java contains Integer, String, Long and so on. They are characterized as having the declaration of variable like "private final". "private" indicates that other objects have no access to the variable(actually, a get-like method is provided while no set-like method is implemented). "final" shows that once the variable is assigned, the value remains.

According to the previous blog, it has been shown that when passing parameters to a function, actually a copy of the reference is passed. It turns out that after calling some method, the reference does not change, which means the memory address it stores remains(note that it's the value of the address instead of  the value in that address).

Hence, when the reference refers to an immutable object, the content in the object has no chance to be modified.  As motioned above, the reference doesn't change either, which leads to the property of immutability.

Otherwise, if the reference refers to a common object, the content in the object might get changed. Thus, even if the reference remains after calling, the value it points to will not necessarily be kept.