There are two ways to do this. The first is, of course, to go through some sort of formal analysis of the algorithm, until you notice something like "hey, I'm evaluating lots of polynomials, shouldn't I think about how I could evaluate them quickly?" And then you'd remember that polynomials can be written in a form like

where the left-hand side requires three multiplications (generally, n multiplications for a polynomial of degree n) and three (generally, n) additions to be evaluated; the right-hand side requirese six (generally, n(n+1)/2 = n + (n-1) + ... + 1) multiplications and three (generally, n) additions. (This is, of course, assuming that you've forgotten what x

^{2}is when you get to evaluating x

^{3}. You wouldn't... but a computer probably would!) Generally,

But sometimes it's easier to just step through the algorithm step by step and realize what you find yourself doing over and over again. For example, in evaluating a polynomial a

_{n}x

^{n}+ a

_{n-1}x

^{n-1}+ ... + a

_{1}x + a

_{0}, you'd realize that when you compute x

^{n}you start by computing x

^{n-1}and then you multiply it by x; if you did that by hand over and over again you'd eventually want to find a way to speed things up. Wouldn't it be easier if you had already stored the value of x

^{n-1}? So you'd first compute the list [1, x, x^2, ... , x^n] by just noticing that each term is x times the previous one, and then you'd multiply those by their respective coefficients a

_{i}and add those sums up. This takes 2n multiplications and n additions; it's not quite as good as the form I've given above, but the point is that just storing your intermediate results instead of recalculating them over and over again saves a lot of time. And if you don't realize this from formally analyzing the algorithm, you can realize it by just stepping through the algorithm until you get to the point where you start cursing and thinking "didn't I already do this? Why the *^%)!*!# am I doing it again?"

(By the way, this was inspired by my trying to compute the numbers of factorizations of various integers; it turns out that you want a lot of numbers of the form "the number of factorizations of n into factors at most k" and if you're not careful you can end up computing the same numbers over and over again. So I got careful.)

## 5 comments:

Ye have heard it said in the past, that there are three rules of optimisation.

1. Don't.

2. (advanced) Don't yet.

3. (really advanced) Don't until you've analysed and/or instrumented your code to find out where the real bottlenecks are.

But very truly, I say unto you: There are some problems for which you need to optimise early, and for which the performance bottlenecks are known in advance Therefore:

4. (really, really advanced) If you must optimise prematurely, do it on the back of an envelope, rather than in code.

You may also consider using your compiler's profiling capabilities to find (possibly unexpected) bottlenecks in your code.

Memoization is a technique that can help sometimes, too.

I was going to note, too, that this

ismemoization.Free information about penis enlargement products, how it works, price of products, top products, and review of penis products. Visit http://www.buypenisenlargement.com

vimax pills - good blog friends! Post your article which is also useful for readers and to share information or experiences you have. I will visit your blog again. penis enlargement pills - http://www.male-sexual.com

Post a Comment