Archive - Jun 2008

Date
  • All
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

Fastest integer multiplication algorithm not on wikipedia

Posted June 27th, 2008 by Mgccl
in

Update: It is, just not featured on multiplication algorithm page.
I just found it out today.
Someone should read it and understand it and wikipeida it. [That person is certainly, not me]

Faster Integer Mulitplication

ACT Score 31, Epic Fail

Posted June 25th, 2008 by Mgccl
in

Done ACT.

I believe I can get a 32 or 33 next time.

35 on math... I has one question wrong on math????
That will be a dark spot that never goes away... it scar me for life...

A candidate problem for 2008 Beijing middle school exam

Posted June 25th, 2008 by Mgccl
in

High school in China includes year 10 to 12. Students who want to get into a good high school have to take the middle school exam and score amazing on it. Each province or sometimes, cities, have their own exam.

This is one of the candidate problem for Beijing this year. It is suppose to be one of those questions that fail 99% of the student body in order to allow only elite to remain.
I saw it here[Chinese].
I tried the question and I was shocked how I suck at geometry. So I used a trigonometry solution, and in the end, using calculus.

Question: Find \angle 7.

My solution:
\angle 1 = \tan^{-1}(\frac{b}{2a+b})
\angle 2 = \tan^{-1}(\frac{a}{a+b})
\angle 3 = \tan^{-1}(\frac{2a+b}{a+b})
\angle 4 = \tan^{-1}(\frac{a+b}{2a+b})
\angle 5 = \angle 4 - \angle 1
\angle 6 = \angle 3 - \angle 2
\angle 7 = \angle 5 + \angle 6
\angle 7 = \tan^{-1}(\frac{a+b}{2a+b}) - \tan^{-1}(\frac{b}{2a+b}) + \tan^{-1}(\frac{2a+b}{a+b}) - \tan^{-1}(\frac{a}{a+b})

Great, we have the expression! Solving it is the problem
\angle 7 = \left(\tan^{-1}(\frac{a+b}{2a+b}) + \tan^{-1}(\frac{2a+b}{a+b})\right)- \left(\tan^{-1}(\frac{b}{2a+b}) \tan^{-1}(\frac{a}{a+b})\right)
The formula
\tan^{-1}(\frac{1}{x}) = \frac{\pi}{2} - \tan^{-1}(x)
helps.
\angle 7 = \frac{\pi}{2}-\left(\tan^{-1}(\frac{b}{2a+b}) + \tan^{-1}(\frac{a}{a+b})\right)
How can I do the rest? There are two options, both run some huge calculations.
One is to use the tangent addition formula which I forgot and have to derive from sine and cosine addition formulas... but that will be too long for tests like this in China. I didn't Wikipedia it, it's cheating.
So I use calculus!
f(b) = \tan^{-1}(\frac{b}{2a+b}) + \tan^{-1}(\frac{a}{a+b})
f(0) = \frac{\pi}{4}
f'(x) = 0(huge amount of calculation omitted, I believe it's around the same if I use the tangent addition formula if I remembered it.
\angle 7 = \frac{\pi}{2} - \frac{\pi}{4}
\angle 7 = \frac{\pi}{4}

There is a elegant geometry solution[Chinese]. This problem cost me few hours, most of the time spending on search for a geometric solution. I finally give up at around 3:30 AM and go with the brutal force "Find all angles and bash the numbers out of arctans."
I would totally fail the real test. I'm questioning myself do I have math talent at all...
Have to improve my geometry skills.

A circle solution to World's Hardest Easy Geometry Problem

Posted June 19th, 2008 by Mgccl
in

The World's Hardest Easy Geometry Problem ruined my sleep.


Find the measure of x without elementary geometry about triangles.

I tried that problem a few months ago for a few hours and failed, so I cheated and looked up the answer.
But today I dreamed about that problem. In my dream, I saw myself using circle to solve that problem.
I woke up, it's 3 am, great time to work on a geometry problem.

So I did. I succeed!
It is cheating to use circles. Only basic properties about triangles, angles and lines are allowed.
Please don't read this if you want to have your own fun with the problem first.
I also have a link for a triangle only solution.

Note: My graph is different because I changed the name of point E to D, and D to E.
Here is where da solutions at.

First looking show that CE=BE, so it's nice to consider using symmetry to solve the problem.
Construct EI \perp CB
Draw a circle pass through E,D,F
Reflect all points through EI
The graph looks like this:

It's easy to see there are some equations
\begin{eqnarray} \angle C &=& \frac{\stackrel{\frown}{EF}+\stackrel{\frown}{GF}-\stackrel{\frown}{HD}}{2}\\ \angle ADB &=& \frac{\stackrel{\frown}{FG}}{2}\\ \end{eqnarray}
All the angles listed above can be found directly because the other two angles in the triangle are already known.
After finding all the size of those angles and multiply 2 to each side, it reduce to a few simple linear equation, all we have to do is to solve it.
It's a easy linear system can be computed by hand.
Set
\begin{eqnarray} a=\stackrel{\frown}{FE}\\ b=\stackrel{\frown}{HD}\\ c=\stackrel{\frown}{FG}\\ \end{eqnarray}

\begin{eqnarray} 40^\circ &=& a+c-b\\ 60^\circ &=& c\\ \end{eqnarray}
We end up with this
20^\circ = b-a
c=b because the graph is symmetric.
a = 40^\circ
Thus x = 20

Q.E.D.[Quite Exhausting Demonstration]

I need to start to train my subconscious so I can do math when I'm asleep.

Visualize multiplication

Posted June 18th, 2008 by Mgccl
in

I have always searched for a visualization of multiplication.
Not the
"there are 3 apples and there are 3 set of them and we get 9 apples"
but a visualization on a number line. Like the visualization of addition.
addition can be visualized like this according to Wikipedia.


A number-line visualization of the algebraic addition 2 + 4 = 6. A translation by 2 followed by a translation by 4 is the same as a translation by 6.

There are visualization that take 2 numbers and create an area, but it doesn't map that area onto a number line.

Just yesterday I finally saw what I needed, the visualization of multiplication though visual sieve by Yuri Matiyasevich and Boris Stechkin.

Read more about it here.

12next ›last »
Honey Pot that kill bots