Maths

[Harry]

Got any questions about maths? You have a huge community of experts on this forum, so why not ask them here. No coursework help though!

[Crackerjack_404]

Recently I came across a very interesting fact about the time complexity of Euclidean algorithm about how the number of steps in the algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.

So if the algorithm took N steps, the smallest number b satisfies
b >= F_(n+1) >= φ^(n-1)
Where F_n in the nth Fibonacci number and φ is the golden ratio. I find it fascinating that the golden ratio somehow shows up here in the worst-case complexity of the algorithm finding the gcd of two numbers.

Does anyone have any good explanations or reading suggestions that explain how and why φ shows up here?

[AndGiggles]

@Crackerjack_404

You may have solved this by yourself already, but there is a decent covering of this in CLRS (Introduction to Algorithms) in the chapter on Number-theoretic algorithms. I can’t quite tell if you are asking about the derivation of the run-time or the relationship between the Fibonacci numbers and the golden ratio. If the former, then CLRS should give a good presentation. For the latter – I seem to recall you saying you know some linear algebra – try writing the recurrences which define the Fibonacci sequence as a matrix equation. Now try diagonalising the matrix. How does this help you?

[Crackerjack_404]

@AndGiggles
Thanks! I was actually curious both about the runtime derivation and then Fibonacci/golden ratio link. I’ll check the CLRS chapter for the former. I’ve got Fibonacci sequence as a matrix equation, and computing the eigenvalues then diagonalising does the golden ratio! Quite satisfying to get the closed form expression for Fibonacci!

[Crackerjack_404]

Something fun I came across today and thought I’d share, for anyone who’s familiar with differentiation and matrix multiplication, turns out you can differentiate polynomials using a matrix!

Say you’ve got a cubic:

f(x) = a + bx + cx^2 + dx^3

Then you can represent the coefficients of x as a column vector
` [ a ]
[ b ]
[ c ]
[ d ]
`

And if them multiply that by the matrix:
` [ 0 1 0 0 ]
[ 0 0 2 0 ]
[ 0 0 0 3 ]
[ 0 0 0 0 ]
`

You get

` [ b ]
[ 2c ]
[ 3d ]
[ 0 ]

`

Which are exactly the coefficients of the derivative!

f^'(x) = b + 2cx + 3dx^2

This is definitely the right way to think about this! Harry

[upsidedown]

I love this and have taken the enormous liberty of stealing it for the forthcoming Sunday Puzzle, hope you don’t mind!! If you do, then please email me to complain and I will reinstate it as your post. You will get credit I promise! Harry

[Geo_addict]

Here are two geometry problems I have written; the first is definitely easier than the second!

1) Let ABC be an acute triangle. Let M be the midpoint of BC. Let D be the second intersection of AM with the circumcircle of ABC and let X be the reflection of D over M. Let E and F be the second intersections respectively of BX and CX with the circumcircle of ABC. Prove that AE*AF = AX^2.

2) Let ABC be a triangle with incenter I and incircle \omega. Let P, Q, R be the intersections of \omega with AI, BI, CI. Let l_A, l_B, l_C be the tangents to \omega through P, Q, R. Let X be the intersection of l_B and l_C, and define Y and Z similarly. Prove that AX, BY, CZ are concurrent.

I haven’t checked these and I usually ask for solutions up front, but since we are rather busy with Challenge 10 I thought I would throw them out there to see if the author gets any bites. Harry

[Geo_addict]

Update to above: In problem 1, AX^2 should be (AX’)^2. Apologies for the mistake.

AI, BI, CI refer to SEGMENTS and the l in l_A, l_B, l_C is an ‘ell’ not an ‘eye’.

[Author]

Posts