Algorithm Complexity
-
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
-
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
If you want to know the number of cycles you could check the chip documentation to determine how many micro cycles a given op will use. With the relatively simple complexity of those algorithms I doubt even big analysis will help. I believe all of those functions use look up tables and identities.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Are there any decisons or loops or just formulas?
Co-Author ASP.NET AJAX in Action
-
Interesting, if you do find an article for sheet with the 'weights' of each operator/function I'd be interested to know. Surely someone, somewhere must of done this kind of thing.
WPF - Imagineers Wanted Follow your nose using DoubleAnimationUsingPath
-
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)
-
If you want to know the number of cycles you could check the chip documentation to determine how many micro cycles a given op will use. With the relatively simple complexity of those algorithms I doubt even big analysis will help. I believe all of those functions use look up tables and identities.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
You need to compute the number of operations that each algorithm is doing depending on the size of the inputs. (edit) usually, all binary operations are constant in time. for example : 1+1 is O(1) loops are linear in complexity : j = 0; for ( i = 0; i < n; i++ ) { j++;} is O(n) and so on and so forth.
Maximilien Lincourt Your Head A Splode - Strong Bad
-
Can you give an example or two?
Co-Author ASP.NET AJAX in Action
-
Bassam Abdul-Baki wrote:
but they wanted something algebraic and not computed.
you compute an algebraic weight to be attached to any given function based on its performance time. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Can you give an example or two?
Co-Author ASP.NET AJAX in Action
-
Bassam Abdul-Baki wrote:
but they wanted something algebraic and not computed.
you compute an algebraic weight to be attached to any given function based on its performance time. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
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
If all you want is a quick "cocktail napkin" comparison, then just count operations by hand, using some large, consistent weight (say, 100) for the trig methods. If the results are close, then you can decide on other factors (clarity, accuracy, ease of optimization, etc.)
every night, i kneel at the foot of my bed and thank the Great Overseeing Politicians for protecting my freedoms by reducing their number, as if they were deer in a state park. -- Chris Losinger, Online Poker Players?
-
time each function individually, assign the fastest operation as "1", assign a number to each other operation based on the timing difference between the shortest operation and it. :) + might be 1 - might be 1 * might be 2.5 / might be 5 sin() might be 10 cos() might be 10 sqrt() might be 20 base each number based on calculated differences, you still have a relative complexity based on CPU time. :) of course ignoring cache flushes, but that is a bit more difficult to catch. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
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
I haven't read through all the responses you got, but there was a fellow a week ago or so here that posted some results of a genetic algorithm being used to create numeric algorithms. It was very interesting. Marc
-
If all you want is a quick "cocktail napkin" comparison, then just count operations by hand, using some large, consistent weight (say, 100) for the trig methods. If the results are close, then you can decide on other factors (clarity, accuracy, ease of optimization, etc.)
every night, i kneel at the foot of my bed and thank the Great Overseeing Politicians for protecting my freedoms by reducing their number, as if they were deer in a state park. -- Chris Losinger, Online Poker Players?
That's what we're doing. However, all operands are based on a multiple of multiplication. The lead architect wishes to use (+/-) = 0.5(*) and (sin/cos)=4(*). I disagreed with that since all trig functions are Taylor series expansions that depending on how many digits, could take much higher to calculate. So we're trying to come up with a happy medium for this and we've settle on three significant digits and/or three Taylor sums whichever is easier.
"You can lead a horse to Vista, but it won't get in stall." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
I haven't read through all the responses you got, but there was a fellow a week ago or so here that posted some results of a genetic algorithm being used to create numeric algorithms. It was very interesting. Marc
-
time each function individually, assign the fastest operation as "1", assign a number to each other operation based on the timing difference between the shortest operation and it. :) + might be 1 - might be 1 * might be 2.5 / might be 5 sin() might be 10 cos() might be 10 sqrt() might be 20 base each number based on calculated differences, you still have a relative complexity based on CPU time. :) of course ignoring cache flushes, but that is a bit more difficult to catch. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
That's almost what we want, except the multiplication is our normalized number and the plus and minus were roughly half that computation. :)
"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
Bassam Abdul-Baki wrote:
Any link?
Nope. Sorry. And I have no clue as to whether the CP forum is searchable. But IIRC, it was about 2-3 weeks ago. Marc
-
That's what we're doing. However, all operands are based on a multiple of multiplication. The lead architect wishes to use (+/-) = 0.5(*) and (sin/cos)=4(*). I disagreed with that since all trig functions are Taylor series expansions that depending on how many digits, could take much higher to calculate. So we're trying to come up with a happy medium for this and we've settle on three significant digits and/or three Taylor sums whichever is easier.
"You can lead a horse to Vista, but it won't get in stall." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
Bassam Abdul-Baki wrote:
However, all operands are based on a multiple of multiplication. The lead architect wishes to use (+/-) = 0.5(*) and (sin/cos)=4(*).
What? So you'd actually halve the score of your algorithm by throwing in an extra add? :~ And yeah, 4x for sine/cosine sounds really, really low. [Edit: I think i read that wrong; you're using multiplication as your baseline, not multiplying weights. Still seems odd... ]
Last modified: 5mins after originally posted -- where's my head at...
every night, i kneel at the foot of my bed and thank the Great Overseeing Politicians for protecting my freedoms by reducing their number, as if they were deer in a state park. -- Chris Losinger, Online Poker Players?
-
Bassam Abdul-Baki wrote:
Any link?
Nope. Sorry. And I have no clue as to whether the CP forum is searchable. But IIRC, it was about 2-3 weeks ago. Marc
Marc Clifton wrote:
And I have no clue as to whether the CP forum is searchable.
The Lounge is, the SoapBox isn't worth it. :-D
"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM