3 ms·
This solution -- O(log n) through repeated squaring -- is a good illustration of usefulness of many areas that "neighbor" computer science, such as linear algeb
by NotOscarWilde 13y ago
This solution -- O(log n) through repeated squaring -- is a good illustration of usefulness of many areas that "neighbor" computer science, such as linear algebra, combinatorics and graph theory.
By the way, if you want to pick up a book on cool applications of linear algebra, I recommend this one (PDF available for free):
Jiří Matoušek - Thirty-three miniatures (Mathematical and algorithmic applications of linear algebra) http://kam.mff.cuni.cz/~matousek/la-ams.html http://kam.mff.cuni.cz/~matousek/la-ams.html
- jules 13y agoI don't think this illustrates the practical usefulness of mathematics. This is not a practical problem, it's a mathematical problem. It's no surprise that maths is useful for solving it. A better case for math can be made with machine learning, image and audio processing, etc.
- NotOscarWilde 13y agoCalculating recurrences is a very common problem in CS. We have an entire toolset -- dynamic programming -- built around it. Yes, if you take the simplest recurrence and say "calculate it" it may sound artificial. But all the tools that can be used for this example -- direct formula, repeated squaring, dynamic programming -- can be used for more complicated recurrences also.