HSC 2016 MX2 Marathon (archive) (2 Viewers)

KingOfActing · Jan 15, 2016

Re: HSC 2016 4U Marathon

Oh, the other idea I had but didn't bother to try and see if it was more viable (probably is) was to find a polynomial that very accurately approximated the square root function on some small range (Something like 1-4?) and then recursively force the input into that range.

A simple outline:

Code:

sqrt(input x)
{
    if(x < 0) throw error;
    if(x == 0) return 0;
    if(x < 1) return sqrt(4*x)/2;
    if(x > 4) return sqrt(x/4)*2;
    return minMaxPolynomial(x);
}

Where minMax was the accurate polynomial (or any other accurate, fast function) to approximate the square root of a number in the range 1 <= x <= 4.

Paradoxica · Jan 15, 2016

Re: HSC 2016 4U Marathon

KingOfActing said:
Oh, the other idea I had but didn't bother to try and see if it was more viable (probably is) was to find a polynomial that very accurately approximated the square root function on some small range (Something like 1-4?) and then recursively force the input into that range.

A simple outline:

Code:

sqrt(input x) { if(x < 0) throw error; if(x == 0) return 0; if(x < 1) return sqrt(4*x)/2; if(x > 4) return sqrt(x/4)*2; return minMaxPolynomial(x); }

Where minMax was the accurate polynomial (or any other accurate, fast function) to approximate the square root of a number in the range 1 <= x <= 4.

A good fact to note is that on average, the number of digits of accuracy doubles with each iteration for square roots using Newton-Raphson Method.

seanieg89 · Jan 15, 2016

Re: HSC 2016 4U Marathon

KingOfActing said:
$The first method that comes to mind is Newton's Method for approximating the roots of an function. In this case, our function is $ f(x) = x^2 - a $ where $a$ is the number we want to calculate the root of. Newton's method is as follows. Start with some guess $x_0$ and then define the following relation: $ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$, which in our case becomes: $ x_{n+1} = x_n - \frac{x_n^2-a}{2x_n} = \frac{x_n^2+a}{2x_n}$. To prove that this will converge towards our desired value, take the limit as n approaches infinity: Let $x = \lim_{n \to \infty}x_n$, then $ x = \frac{x^2+a}{2x} \Longleftrightarrow x = \pm\sqrt{a} \\$Assuming we make an appropriate first guess, the function will always remain positive, hence converging towards the principal square root.$

$The operations to complete one step of the recursion would be, assuming $a$ is stored in memory slot 0 and the previous $x_n$ is stored in memory slot 1: $\\\\$Copy slot 1 to 2, copy slot 1 to 3, multiply slot 1 and 2, store in slot 1, add from slot 0 and 1, store in slot 1, divide slot 1 by the number 2, store in slot 1, divide slot 1 by slot 3, store in slot 1$\\\\$This would take 10 time units, but can be arbitrarily repetead to achieve any precision required.$

$Precision checking, however, will also take up a few time units in every round. In order to ensure at least 20 digits of precision, we must make sure $ x_{n+1} $ and $x_{n}$ agree up to 20 digits. This can be done by copying the previous guess, and at the end of the recursion checking whether $ \frac{|x_{n+1}-x_n|}{x_{n+1}} \leq 10^{-20} $ (note that absolute value can be replaced by checking which of the two is greater, and subtracting the smaller from the greater). Unfortunately, adding this step to every recursion adds 8 time units/recursion. It is left to the friend to decide how often they would like to check in the recursion, if at all.$

$There are a few more hurdles that need to be dealt with. The original number must be greater than 0 before beginning the recursion. An additional check for the number equalling 0 should result in a display of 0. Finally, the original guess must be made to be appropriate. A possible guess could be $\frac{a}{2}$. This is only detrimental in the case $a < \sqrt2$ and so can be probablistically argued to be a good option. Ultimately, any positive guess will eventually converge to 20 significant figures. If access to the number in its mantissa-exponent form is available, a very good starting guess would be keep the mantissa the same, and halve the exponent.$

After typing all that I now realise that it said n-th root not square root, but the idea would be the same, still using the Newtonian method just with the function $x^n - a$ . As for an upper bound on time units, I'm way too tired but a very weak one would be 20*time units/recursion. I also treated the numbers as having to be stored somewhere before any operations being done to them (You can't just multiply a number by itself, for example. You have to store that number in two different slots (register addresses), multiply them, then store the result somewhere in some slot.

I don't know if any of what I wrote makes any sense but I am too tired to read over it again. Yolo.

Good first idea! Newton's is indeed amazing for this purpose. However, your analysis of accuracy is a bit flawed. The n+1-th approximation being very close to the n-th approximation doesn't in itself imply that we are close to the limiting value. Picture a sequence that bunches up for a long time before having a big "jump" and converging to something else entirely.

This is not going to be the case here, but using this kind of method to "check precision" definitely requires additional justification.

You should also specify an easy way of choosing a starting value that will guarantee convergence.

(As paradoxica notes above, the degree of accuracy will roughly double with each iteration of newton's, which is why it is great. The starting value does not matter as much when you have such rapid convergence. An inequality that captures this rapid convergence is they main thing I am looking for in an answer.)

Paradoxica · Jan 15, 2016

Re: HSC 2016 4U Marathon

seanieg89 said:
Good first idea! Newton's is indeed amazing for this purpose. However, your analysis of accuracy is a bit flawed. The n+1-th approximation being very close to the n-th approximation doesn't in itself imply that we are close to the limiting value. Picture a sequence that bunches up for a long time before having a big "jump" and converging to something else entirely.

This is not going to be the case here, but using this kind of method to "check precision" definitely requires additional justification.

You should also specify an easy way of choosing a starting value that will guarantee convergence.

(As paradoxica notes above, the degree of accuracy will roughly double with each iteration of newton's, which is why it is great. The starting value does not matter as much when you have such rapid convergence. An inequality that captures this rapid convergence is they main thing I am looking for in an answer.)

Refer to Cambridge Year 12 3U for a question which captures the inequality, by forcing you to deduce that the 20th approximation of the square root of three is accurate to over 1 million decimal places, starting from the greatest integer less than the square root of 3

seanieg89 · Jan 15, 2016

Re: HSC 2016 4U Marathon

Paradoxica said:
Refer to Cambridge Year 12 3U for a question which captures the inequality, by forcing you to deduce that the 20th approximation of the square root of three is accurate to over 1 million decimal places, starting from the greatest integer less than the square root of 3

Am well aware of how to estimate the error in Newton's myself lol, am posing this as a question to HS students.

Don't have a copy of that book on me so I cannot speak for how rigorous the method in that question is. Even if it does things properly though, I highly recommend students try this problem without being walked through it by a textbook question.

KingOfActing · Jan 20, 2016

Re: HSC 2016 4U Marathon

For anyone interested, this is the sort of minimax polynomial I was talking about. I made this one through Remez' algorithm for the range 1 < x < 4.
$$For $1<x<4,\, \sqrt{x} = -0.00246248x^4+0.334792x^3-0.189161x^2+0.785939x+0.471376 +\varepsilon$ Where $\epsilon$ is the error term $ |\varepsilon| \leq 8.29773\times10^{-4}$ This can be easily extended to any degree, and makes deriving the error term quite simple.

For those who don't know, Remez' algorithm is this:

$Let the degree of your interpolating polynomial be $N$, denote the interpolating polynomial $P(x)$ and the function you wish to interpolate $f(x)$. Then pick $N+2$ points $x_1, x_2, ..., x_{N+2}$ in the range you wish to interpolate, and set up the following system of equations:$\\P(x_1)-f(x_1)=\varepsilon\\P(x_2)-f(x_2)=-\varepsilon\\...\\P(x_{N+2})-f(x_{N+2}) = \pm\varepsilon\\$i.e. alternate the sign of the maximal error term $\epsilon$. Solve this system of equations for the coeffecients of $P$ and for $\varepsilon$, and you are done.$

InteGrand · Jan 23, 2016

Re: HSC 2016 4U Marathon

Paradoxica said:
$$\noindent By considering the vectors, $e^{\frac{\pi}{180}}, e^{\frac{2\pi}{180}}, e^{\frac{3\pi}{180}}, \cdots ,e^{\frac{42\pi}{180}}, e^{\frac{43\pi}{180}}, e^{\frac{44\pi}{180}}\\$ evaluate $\dfrac{\displaystyle \sum_{n=1}^{44}\cos n^{\circ}}{\displaystyle \sum_{n=1}^{44}\sin n^{\circ} }$

Should there be i's in the exponents (i.e. complex exponentials)? Otherwise there's not much point thinking of them as vectors, is there? (Haven't thought much about the Q.)

Paradoxica · Jan 23, 2016

Re: HSC 2016 4U Marathon

InteGrand said:
$\noindent Let $R$ be a real number and $n$ be a positive integer.$

$\noindent (i) Suppose $R<0$, so $-R>0$. For any integer $k$, let $\omega_k := \sqrt [n]{-R}\,\mathrm{c\textit{i}s}\left(\frac{(2k+1)\pi}{n} \right)$, so that $\omega_k$ is an $n^{\text{th}}$ root of $R$. Show that $\omega_k$ and $\omega_{(n-1)-k}$ are complex conjugates.$

$\noindent (ii) Suppose $R>0$. For any integer $k$, let $\omega_k := \sqrt [n]{R}\,\mathrm{c\textit{i}s}\left(\frac{2k\pi}{n} \right)$, so that $\omega_k$ is an $n^{\text{th}}$ root of $R$. Show that $\omega_k$ and $\omega_{n-k}$ are complex conjugates.$

$$\noindent (i) By direct substitution, $\omega_k \times \omega_{(n-1)-k} = \sqrt [n]{-R}\,\mathrm{c\textit{i}s} \left(\frac{(2k+1)\pi}{n}\right) \times \sqrt [n]{-R}\,\mathrm{c\textit{i}s}\left(\frac{(2n-2k-1))\pi}{n}\right) \\ \omega_k \times \omega_{(n-1)-k} = \sqrt [n]{R^2}\,{c\textit{i}s} \left(\frac{(2n - (2k+1)+2k+1)\pi}{n}\right)=\sqrt [n]{R^2}\,{c\textit{i}s} \left(\frac{2n \pi}{n}\right)\\ \omega_k \times \omega_{(n-1)-k} =\sqrt [n]{R^2}\,{c\textit{i}s} (2\pi)=\sqrt [n]{R^2} \in \mathbb{R} \\$Since the product is a real number, the square of the modulus, they are complex conjugates.$ \\ $\noindent (ii) In a manner similar, but less complicated, to above, the same can be shown.$

$$\noindent By considering the vectors, $e^{\frac{i\pi}{180}}, e^{\frac{2i\pi}{180}}, e^{\frac{3i\pi}{180}}, \cdots ,e^{\frac{42i\pi}{180}}, e^{\frac{43i\pi}{180}}, e^{\frac{44i\pi}{180}}\\$ evaluate $\dfrac{\displaystyle \sum_{n=1}^{44}\cos n^{\circ}}{\displaystyle \sum_{n=1}^{44}\sin n^{\circ} }$

InteGrand · Jan 23, 2016

Re: HSC 2016 4U Marathon

Paradoxica said:
$$\noindent (i) By direct substitution, $\omega_k \times \omega_{(n-1)-k} = \sqrt [n]{-R}\,\mathrm{c\textit{i}s} \left(\frac{(2k+1)\pi}{n}\right) \times \sqrt [n]{-R}\,\mathrm{c\textit{i}s}\left(\frac{(2n-2k-1))\pi}{n}\right) \\ \omega_k \times \omega_{(n-1)-k} = \sqrt [n]{R^2}\,{c\textit{i}s} \left(\frac{(2n - (2k+1)+2k+1)\pi}{n}\right)=\sqrt [n]{R^2}\,{c\textit{i}s} \left(\frac{2n \pi}{n}\right)\\ \omega_k \times \omega_{(n-1)-k} =\sqrt [n]{R^2}\,{c\textit{i}s} (2\pi)=\sqrt [n]{R^2} \in \mathbb{R} \\$Since the product is a real number, they are complex conjugates.$ \\ $\noindent (ii) In a manner similar, but less complicated, to above the same can be shown.$

Well technically speaking, it's not just the fact that the product is a real number that is significant, but rather that this product is equal to the modulus-squared (of the ω), but correct method, well done

.

DatAtarLyfe · Jan 23, 2016

Re: HSC 2016 4U Marathon

InteGrand said:
Well technically speaking, it's not just the fact that the product is a real number that is significant, but rather that this product is equal to the modulus-squared (of the ω), but correct method, well done .

that was a deceivingly simple question, completely overlooked the basic concept

Paradoxica · Jan 23, 2016

Re: HSC 2016 4U Marathon

$\noindent By considering $\log(x^n -1)$ or otherwise, find $ \\ \frac{31}{2-\alpha}+\frac{31}{2-\beta}+\frac{31}{2-\gamma}+\frac{31}{2-\delta}\\$ where $\alpha,\beta,\gamma,\delta$ are complex fifth roots of unity.$ \\ $Hence, evaluate, in closed form, $ \sum_{r=1}^{n-1} \frac{2^n-1}{2-e^{\frac{2ir\pi}{n}}}$

KingOfActing · Jan 23, 2016

Re: HSC 2016 4U Marathon

Paradoxica said:
$$\noindent By considering the vectors, $e^{\frac{i\pi}{180}}, e^{\frac{2i\pi}{180}}, e^{\frac{3i\pi}{180}}, \cdots ,e^{\frac{42i\pi}{180}}, e^{\frac{43i\pi}{180}}, e^{\frac{44i\pi}{180}}\\$ evaluate $\dfrac{\displaystyle \sum_{n=1}^{44}\cos n^{\circ}}{\displaystyle \sum_{n=1}^{44}\sin n^{\circ} }$

I'm not quite sure where to get from where I was at but this is what I did: $\text{It is first noted that } \sum_{m = 1}^{n}\cos{mx} = \Re\left(\sum_{m = 1}^{n}e^{imx}\right) \text{ and similarly } \sum_{m = 1}^{n}\sin{mx} = \Im\left(\sum_{m = 1}^{n}e^{imx}\right)\text{. Recognise the exponential sum as a geometric sequence as } e^{imx} = (e^{ix})^m \\\text{Hence,}\\\sum_{m = 1}^{n}\cos{mx} = \Re\left(\sum_{m = 1}^{n}e^{imx}\right) = \Re \left( \frac{e^{ix}(e^{inx}-1)}{e^{ix}-1} \right) = \frac{\cos(nx)-\cos((n+1)x)+ \cos{x}-1}{2-2\cos{x}}\\\sum_{m = 1}^{n}\sin{mx} = \Im\left(\sum_{m = 1}^{n}e^{imx}\right) = \Im \left( \frac{e^{ix}(e^{inx}-1)}{e^{ix}-1} \right) = \frac{\sin(nx)-\sin((n+1)x)+ \sin{x}}{2-2\cos{x}}\\\text{Hence,}$ $\frac{\sum_{n=1}^{44}\cos n^{\circ}}{\sum_{n=1}^{44}\sin n^{\circ}} =\frac{\sum_{n=1}^{44}\cos(\frac{n\pi}{180})}{\sum_{n=1}^{44}\sin(\frac{n\pi}{180})} = \frac{\cos(\frac{44\pi}{180})-\cos(\frac{45\pi}{180})+ \cos{\frac{\pi}{180}}-1}{\sin(\frac{44\pi}{180})-\sin(\frac{45\pi}{180})+ \sin{\frac{\pi}{180}}} = \frac{\cos(\frac{44\pi}{180})-\cos(\frac{45\pi}{180})+ \cos{\frac{\pi}{180}}-1}{\sin(\frac{44\pi}{180})-\sin(\frac{45\pi}{180})+ \sin{\frac{\pi}{180}}} = \frac{\cos(\frac{44\pi}{180})+\cos(\frac{\pi}{180})-\frac{1}{\sqrt2}-1}{\sin(\frac{44\pi}{180})+\sin(\frac{\pi}{180})-\frac{1}{\sqrt2}} = \frac{2\cos(\frac{43\pi}{360})\cos(\frac{45\pi}{360})-\frac{1}{\sqrt2}-1}{2\sin(\frac{45\pi}{360})\cos(\frac{43\pi}{360})-\frac{1}{\sqrt2}} = \frac{\sqrt{2+\sqrt2}\cos(\frac{43\pi}{360})-\frac{1}{\sqrt2}-1}{\sqrt{2-\sqrt2}\cos(\frac{43\pi}{360})-\frac{1}{\sqrt2}} = \frac{\sqrt{4+2\sqrt2}\cos(\frac{43\pi}{360})-1-\sqrt2}{\sqrt{4-2\sqrt2}\cos(\frac{43\pi}{360})-1}$

Looking at the result on wolframalpha, I am fairly certain it just $1 + \sqrt2$ , but I'm not sure how to simplify the expression I've got. I tried to rationalise the denominator but that just made the numerator really messy and didn't seem to lead anywhere.

hedgehog_7 · Jan 23, 2016

Re: HSC 2016 4U Marathon

The ellipse e has equation x^2/100 + y^2/75 = 1

Find the equation of the circle that is tangential to the ellipse at P (5,7.5) and Q (5,7.5)

Drsoccerball · Jan 23, 2016

Re: HSC 2016 4U Marathon

hedgehog_7 said:
The ellipse e has equation x^2/100 + y^2/75 = 1

Find the equation of the circle that is tangential to the ellipse at P (5,7.5) and Q (5,7.5)

Firstly you should not use 'e' as a way of describing an Ellipse it can be confused with the eccentricity.
Also P and Q are the same point ?

Drsoccerball · Jan 23, 2016

Re: HSC 2016 4U Marathon

Paradoxica said:
$$\noindent By considering the vectors, $e^{\frac{i\pi}{180}}, e^{\frac{2i\pi}{180}}, e^{\frac{3i\pi}{180}}, \cdots ,e^{\frac{42i\pi}{180}}, e^{\frac{43i\pi}{180}}, e^{\frac{44i\pi}{180}}\\$ evaluate $\dfrac{\displaystyle \sum_{n=1}^{44}\cos n^{\circ}}{\displaystyle \sum_{n=1}^{44}\sin n^{\circ} }$

Wasn't this out of syllabus ?

KingOfActing · Jan 23, 2016

Re: HSC 2016 4U Marathon

Drsoccerball said:
Wasn't this out of syllabus ?

Euler's formula is out now, yeah. Just replace everywhere you see e^ix with cis(x) and it's still valid, through De Moivre's formula.

hedgehog_7 · Jan 23, 2016

Re: HSC 2016 4U Marathon

The ellipse a has equation x^2/100 + y^2/75 = 1

Find the equation of the circle that is tangential to the ellipse at P (5,-7.5) and Q (5,7.5)

Paradoxica · Jan 23, 2016

Re: HSC 2016 4U Marathon

KingOfActing said:
Looking at the result on wolframalpha, I am fairly certain it just $1 + \sqrt2$ , but I'm not sure how to simplify the expression I've got. I tried to rationalise the denominator but that just made the numerator really messy and didn't seem to lead anywhere.

What did I say? Consider the VECTORS

KingOfActing · Jan 23, 2016

Re: HSC 2016 4U Marathon

hedgehog_7 said:
The ellipse a has equation x^2/100 + y^2/75 = 1

Find the equation of the circle that is tangential to the ellipse at P (5,-7.5) and Q (5,7.5)

Let the equation of the circle be (x-a)^2 + (y-b)^2 = r^2

Differentiating the circle equation implicitly gives dy/dx = (a-x)/(y-b)
Differentiating the ellipse equation implicitly gives dy/dx = -3x/4y

These derivative must be equal at the points given, giving two equations:
2a-b = 2.5
2a + b = 2.5
Hence a = 5/4, b = 0

Substituting into the equation of the circle along with one of the points it passes through allows us to solve for the radius:
(5-5/4)^2 + (7.5)^2 = r^2
1125/16= r^2

Hence the equation of the circle is (x-5/4)^2+ y^2 = 1125/16

Sorry for lack of LaTeX, I'm on my phone and I got lazy

KingOfActing · Jan 23, 2016

Re: HSC 2016 4U Marathon

Paradoxica said:
What did I say? Consider the VECTORS

Oopsies

HSC 2016 MX2 Marathon (archive) (2 Viewers)

lukewarm mess

-insert title here-

Well-Known Member

-insert title here-

Well-Known Member

lukewarm mess

Well-Known Member

-insert title here-

Well-Known Member

Booty Connoisseur

-insert title here-

lukewarm mess

Member

Well-Known Member

Well-Known Member

lukewarm mess

Member

-insert title here-

lukewarm mess

lukewarm mess

Users Who Are Viewing This Thread (Users: 0, Guests: 2)