In this post, we attempt to unravel the mysteries of the “magic” constant found in the fast inverse sqrt method in an intuitive fashion.
This is inspired by an article of similar name called Calculating Fibonacci Numbers, Quickly and Exactly. Consider the a modified fibonacci sequence given by the recurrence . We shall look at various algebraic and analytic properties of this sequence, find two algorithms that computes in time, and finally look at a motivating example where we need to compute this sequence quickly and exactly.
We consider the problem of efficiently computing the infinity norm of the inverse of a lower bidiagonal matrix L in linear time.
Let’s consider the Interval Scheduling Problem, in which we have a set of n requests ; the request corresponds to an interval of time starting at and finishing at , or request spans interval . Suppose that a subset of the requests is compatible if no two of them overlap in time; find the largest compatible subset of any set of requests in a reasonable number of steps.