Generalized Euclidean Algorithm

Generalized Euclidean Algorithm, or Integer Relation:

A set of real numbers x_1, x_2, ..., x_n is said to possess integer relation if there exist integers a_i such that
a_1x_1+a_2x_2+...+a_nx_n==0
with not all a_i==0.

Image Search or Color Search?

I tried several so-called "image search" engine, but found nothing that interests me.

Generally, there are two ways to search for a image or picture.

• By text


• By image

Implements of searching by text is easy and efficient. There are many search engines of this kind, among which google image search is a nice one.

However, search by text is not what people expected, and is not that user-friendly. Have you ever imagined a scene that could hardly be described? Or do you have less famous paintings whose name and author are not known?

Then you would draw your imaginations or take pictures of your favourite paintings and search for them. Of course, you can not search by text, because you do not have any idea of the text description of your targets.

But, up till now, there is no such engine that could search images worldwide effectively and efficiently. (Suggestions are appreciated ;))

Instead, according to my experience, image search engines behave in this way. They scan your uploaded image or picture, calculate color distributions with certain functions, match the colors with what are in their database, and finally send the results back to users.

So, you are expected to find those pictures with the same colors, do you?

If you search for a "white cat", you will probably find snow.

That's color search!

I think shape search is closer to the way of thinking of human being, though it could not be the same. But there are several difficulties for this not-so-perfect solution. First is how to distinguish shapes. Second, how to match shapes? How to define a regulation to match certain shapes? And this is also based on how to define shapes, especially complex shapes. Third, huge calculations. A compressed picture of ordinary size could be 100K. Finding shapes and storing them are time consuming, and could require more than 10 times of spaces. It's not just slow. It could be unsolvable because of high space complexities.

We, human beings, could easily distinguish a smile face from faces with a glance. :) However, distinguishing a smile face in black-white is hard enough for computers. :( Why? Because computers do not have eyes and brains. They only have scanners and CPUs. After defining many complicated regulations, it is possible for computers to find a smile face that meets the requirements of human beings. But implementations would be hard and bugs would be everywhere. This (;)) is a smile or not?

[]

Javascript is NOT Java at all

Although more and more people have realized that Javascript is not Java, I still want to state that:

• Javascript is now the most popular script language used in webpages all over the world.


• Javascript is now supported by most browser (I guess all browsers you have tried :P).


• Javascript is an object-oriented language, although you could not define a class with the keyword class explicitly.


• Javascript is young.


• Javascript is created by Netscape (currently Mozilla), not Sun (well, not the sun ;)).


• Javascript is NOT Java at all.

If you are interested in Javascript, please visit developer.mozilla.com. The documents might be of use.

Java IO

BufferedReader saves your memory!

In Java, input with Scanner (1.5) is very slow, and requires more memory. Scanner tries to read all data when initialized. However, Scanner is a convenient with methods like nextInt, and self defined delimiters.

BufferedReader is not as convenient but more efficient. Use StringTokenizer to extract numbers from a line if needed.

Generally speaking, Java IO is slower and requires more memory than other common languages.

Some tips on Java IO

• Scanner is suitable to read input data for the most of problems, but it is very slow. You should use it to read small input data only.



• BufferedReader provides quite fast read operations for almost all problems. But this class may be used to read single characters and lines only. To read tokens and numbers you should use StringTokenizer or StreamTokenizer.



• PrintWriter is preferred in all cases and works rather fast. But its method printf is too slow as well as calls like println(a + " " + b). You should output variables one-by-one to reach the highest performance.

Distance between Skew Lines

I assume that you are familiar with vector and cross product in three dimension.

A line is defined by two points x_1, x_2:

x==x_1+(x_2-x_1)*s

where s is a variable.

The normal vector of skew lines l_1 (x_1,x_2) and l_2 (x_3,x_4) is the cross product of vectors (x_2-x_1) and (x_4-x_3)

N==(x_2-x_1)x(x_4-x_3)

and normalize it, we get

n==(x_2-x_1)x(x_4-x_3)/|(x_2-x_1)x(x_4-x_3)|

so the distance between line l_1 and line l_2 is

d==n.(x_3-x_1)

Easy? For more informations about vector and geometry, please refer to
http://mathworld.wolfram.com/topics/Geometry.html