Algorithm Complexity
-
I'm not positive if this is what Marc was referring to or not, but there's one near the top of the page on the right-hand side. There's a little magnifying glass and the words "Search comments" which is a link. If you click it from the Lounge, you can search the Lounge by author or subject. BDF
Thanks, Big Daddy. :) Say did you ever meet the 'real' Big Daddy[^]. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
Thanks, Big Daddy. :) Say did you ever meet the 'real' Big Daddy[^]. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
Chris Meech wrote:
meet the 'real' Big Daddy
No, sadly, I have not. But if I'm ever in Ocala, I'll be sure to stop at his museum. Thanks for the link. BDF
-
Thank you Marc. I had never noticed that before. Even odder I guess is that when you go to advanced search, the Lounge is not listed, but yet apparently it can be searched. That's a :wtf: to me. Thanks. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
Well then the solution is obvious. Just make up whatever numbers you want, and come up with a heinously complex algebraic "formula" that looks powerful, but is in fact meaningless. I'm pretty sure the Fed and the Stock Market have been getting away with this for years :)
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
-
Bassam Abdul-Baki wrote:
Actually, the search engine has improved drastically as of late.
Fun with semantics: X has improved dramatically Y's new management has drastically affected programmer performance Or, the stock market went up dramatically today vs. the stock market took a drastic turn for the worse today. Anyways, I'm not taking pot shots or trying to be holier than thou or anything like that. It's simply that I was struck by the use of the word "drastic" as a modifier to "improved" and was thinking (if you can call it that) out loud in a meandering way. Marc
-
Bassam Abdul-Baki wrote:
True, but I've seen similar statistics for using different programming languages and OS's and hardware. They just list as many different configurations as possible. Oh well, we'll modify our count slightly for the sqrt. Thanks.
except that the one "extra" function that breaks the cache is more expensive than anything else. Knowing that is what the profilers are designed to help you with. Counting up the operations often leads you to think something is better than it really is. You can't divorce yourself from the architecture, only cooperate with it. When you try and put "all the options" on the table, there are too many to count.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Bassam Abdul-Baki wrote:
Actually, the search engine has improved drastically as of late.
Fun with semantics: X has improved dramatically Y's new management has drastically affected programmer performance Or, the stock market went up dramatically today vs. the stock market took a drastic turn for the worse today. Anyways, I'm not taking pot shots or trying to be holier than thou or anything like that. It's simply that I was struck by the use of the word "drastic" as a modifier to "improved" and was thinking (if you can call it that) out loud in a meandering way. Marc
That's true. However, if you'd used the search engine before, you'd know it timed out more often than not. Thus, any improvement is a drastic improvement. Is it me or is the word meandering abused in this forum? :-D
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon Web - Blog - RSS - Math - LinkedIn - BM
-
Hi, maybe there is a way in between: Count the calls to non-trivial functions like trigonometrical ones in each algorithm and then time some iterations with only one of these calls so you can get an estimate on the weight of each of those function calls. This way you might not get a result like "A has O(n^2) and B has O(3n^2)" but "A's complexity is significantly higher than B's" or "both algorithms are about equal in complexity". Maybe put some tech talk on top of it noting that real-life complexity depends on platform used etc. :-)
-
Understanding the question is half the answer. Make sure that you understand the same thing as your boss does when you say "alghorithm complexity". Honestly, for me alghorithm complexity and code complexity are about the same thing(semantically speaking) since alghorithms are the things that are coded. Now the question is what exactly do you mean by "complexity". if you are intrested in performance, you should check http://en.wikipedia.org/wiki/Big_O_notation[^] otherwise if you should chose some metrics based on what you are looking for. Things like is 1+1+1 more complex that 1+2 or just the same. Well, good luck!
Alex C. D.
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
Look at the weights assigned to those functions (hopefully they are instristic) in an open source compilers. I cant recall specific names now, but it has something to do with Selectors and file names with a .sel extension. There should be one or more for each output arch. My guess, it should be fine tuned on the lowest level, so you should get the 'exact' number of CPU cycles it take to perform such a function. That said, good luck :)
xacc.ide
The rule of three: "The first time you notice something that might repeat, don't generalize it. The second time the situation occurs, develop in a similar fashion -- possibly even copy/paste -- but don't generalize yet. On the third time, look to generalize the approach." -
Right. You're supposed to tell them that you used the same arcane algorithm they use to calculate the time you need to finish a project.
--------------- don't P A N I C
-
Well then the solution is obvious. Just make up whatever numbers you want, and come up with a heinously complex algebraic "formula" that looks powerful, but is in fact meaningless. I'm pretty sure the Fed and the Stock Market have been getting away with this for years :)
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
Like the stock fund that got reamed a few months ago when the market did something that it's controlling formulas said was 36 standard deviations away from the most likely result.
-- If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.
-
Well, the complex functions all boil down to a power series. Power series are composed of, guess what, add subtract, multiply, divide. Computational multiply and divide are composed of, guess what, add and subtract. Subtract is, guess what, add with negation. Add is the baseline and all the rest can be derived as multiples of add.
-
Shog9 wrote:
So you'd actually halve the score of your algorithm by throwing in an extra add?
How so? It would just be XM™ + 0.5M.
Shog9 wrote:
And yeah, 4x for sine/cosine sounds really, really low.
Yeah, I argued that with him from the very beginning since they are Taylor serieseses.
"It is the mark of an educated mind to be able to entertain a thought without accepting it." - Aristotle Web - Blog - RSS - Math - LinkedIn - BM
Bassam Abdul-Baki wrote:
since they are Taylor serieseses
Do you really think sin/cos/tan are computed using Taylor series? That would take forever, as it would be difficult to get the least significant bits (almost) right (which your algorithm may not need, but a general-purpose trig function should try to accomplish). For one, there are much better formulas to get the result for smaller ranges of values, so a decent software approach would select the right formula (not a real Taylor series!), depending on input. On the other hand, modern CPUs have instructions that perform trig operations; their performance is anywhere between 10 and 300 times slower than multiply. As a first rule of thumb: if your set of formulas includes trigs, that iss the only thing you should count, forget all additions, multiplicationd, divisions, just count trigs. The next performance improvement would be to look for: 1. sin-cos pairs; some implementations can do both at the same time, at no extra cost. That does not mean your high-level language will get the second one for free though. 2. mathematical transformations that reduce the number of independent trig functions; e.g. if you already calculated sin(a) and sin(b), then sin(a+b) can be calculated from those. BTW: if your proposal would include "sin/cos costs as much as 4 multiplies" then I am afraid I would not be impressed. I strongly suggest you do some experiment to at least improve that one coefficient. :)
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips: - use PRE tags to preserve formatting when showing multi-line code snippets - before you ask a question here, search CodeProject, then Google
-
Bassam Abdul-Baki wrote:
since they are Taylor serieseses
Do you really think sin/cos/tan are computed using Taylor series? That would take forever, as it would be difficult to get the least significant bits (almost) right (which your algorithm may not need, but a general-purpose trig function should try to accomplish). For one, there are much better formulas to get the result for smaller ranges of values, so a decent software approach would select the right formula (not a real Taylor series!), depending on input. On the other hand, modern CPUs have instructions that perform trig operations; their performance is anywhere between 10 and 300 times slower than multiply. As a first rule of thumb: if your set of formulas includes trigs, that iss the only thing you should count, forget all additions, multiplicationd, divisions, just count trigs. The next performance improvement would be to look for: 1. sin-cos pairs; some implementations can do both at the same time, at no extra cost. That does not mean your high-level language will get the second one for free though. 2. mathematical transformations that reduce the number of independent trig functions; e.g. if you already calculated sin(a) and sin(b), then sin(a+b) can be calculated from those. BTW: if your proposal would include "sin/cos costs as much as 4 multiplies" then I am afraid I would not be impressed. I strongly suggest you do some experiment to at least improve that one coefficient. :)
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips: - use PRE tags to preserve formatting when showing multi-line code snippets - before you ask a question here, search CodeProject, then Google
I agree that once you know sin, cos, tan and cot should be relatively quicker. However, the only reason we assumed Taylor series is we don't know which methods it uses and we don't have the OS in which this will finally be tested/installed on, and we're not sure about which compiler. We were hoping for something quick and dirty without having to test run these algorithms since this request was added at the last minute. I agree with your suggestion that since the +-*/ are an order of magnitude less than trigs, they could, for our estimations, be ignored. Let me see if that idea will pass around here since we're very close on closing this thing. Thanks.
"Science removes the con from your conscience." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
Bassam Abdul-Baki wrote:
Is anyone aware of such a method?
I generally use a profiler. if you really want a number, test it. Call 1 MILLION calls of a given operation, time it, come up wth a numerical scale for each operand based on the time it takes to call each operation. Now you have a good number.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
Profilers help some but are not perfect. The easiest way, assuming you don't already have a profiler installed -- and sometimes even then, to tell which of two algorithms is going to be faster, is to write a program that calls both alternative and which gets the time before, between each alternative, and at the end of its run. Have the test run 1 million iterations of each case -- or maybe 10,000 if the the program is taking too long. The wall clock approach gets you a good rough estimate in all cases and in some few cases, it gives you better results. Memory caching often confuses profilers -- only a true test on real data using wall clock time will let you overcome these problems. Now, you can spend a great deal of time getting your cache architecture described to the profiler, but you'll still have to run a wall clock test to verify that your profile is configured correctly. If you haven't already done all this, maybe a wall clock test is good enough.
-
It depends how those functions are implemented. Note that they might well be single instructions on the processor (and most of them are - FCOS, FSIN, FSINCOS, FPTAN, FSQRT on x86) but the processor itself might implement them as a sequence of smaller operations. It might matter a bit more on a device that doesn't implement floating-point in hardware, for example Pocket PCs have to use software FP. That said because of the vast speed difference between CPU and even the on-board caches, you can execute many many floating point operations in the time it takes to load from memory. If you need speed, look at your access pattern before the theoretical complexity of your algorithm.
DoEvents: Generating unexpected recursion since 1991 -
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
A method for comparing different algorithms is "Algorithm Analysis". Basically it is a 5 step process: Step 1. What is the INPUT SIZE of the algorithm? E.G. An array[20] or array[n] Step 2. Identify the/a basic operation that is performed at each step of the algorithm. E.G. For i=0 to n-2 do For j=i+1 to n-1 do if A[i] == A[j] return sin(A[i]); return false; The basic operation could be a comparison, an assignment statement or addition. Step 3. Check to see if the worst case and best case are the same. Will the running time complexity be the same. Time complexities are one of the following: Big-Oh, Big-Omega, or Big-Theta Step 4: Create a mathematical summation for the number of times the algorithm's basic operation is executed. Step 5: Using standard formulas and rules of sum manipulation, either find a closed formula for the count or , at the very least, establish its order of growth. In the example above the basic operation is a comparison. In the worst case there are either no equal elements or an array with the last two elements are the only pair of equal elements. So compute for the worst case. You have two SUMS (note: lack of math notation): 1 from i=0 to n-2 and 2 from j=i+1 to n-1. The two sums are on 1. 1 is the # of times the basic operation is executed. The short is you get a result from your SUM = (n-1)n/2. In the worst case the algorithm needs to compare all n(n-1)/2 distinct pairs of its n elements. This algorithm would have a running time complexity of Big-Theta(n^2). So just give your boss a time complexity: Big-Oh, Big-Omega, or Big-Theta.
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
Hmm, not really possible. It is highly implementation dependant, and hardware dependant. For example tan can have a lot more calculations required than sqrt. But depending on how the mix of operations you could have vastly different results. Say your CPU has 2 FPU and 4 int, the algorithm that runs best on that hardware, could be vastly different than the one on a system with 4FPU and 2 int. The ability of the CPU to do more than one calculation at a time, has caused typical complexity calculations to lose a lot of their meaning. If you have the right mix you might see an order of magnitude increase in an algorithm, or you might have one extra multiply needed for the next step that requires each step of the algorithm to take 2 cycles rather than 1 for example. You could have an algorithm that is really hard to predict how the if statements will branch, this would kill a P4, with a really large instruction pipeline, branching the wrong way can cost 10 times as much as a calculation. You could get an idea of the number of multiplies, adds, branches etc needed, but how that translates to the hardware will change drastically. Even when you think what you know what the algorithm you coded was, that doesn't mean that the compiler compiled it that way, it could have inlined parts, moved operations around, etc. The only way you'd know for sure what instructions get sent to the CPU would be to code in assembly. But even then, a lot of modern CPUs will do things like branch prediction, or out of order instruction execution, so what actually ends up running on the hardware could be vastly different than you coded.