Algorithm Complexity
-
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
-
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
-
Dang. What do you know. I found it: http://www.codeproject.com/lounge.asp?msg=2248592&ForumID=1159&searchkw=algorithm&sd=13%20Jul%202007&ed=11%20Oct%202007&stype=1&Page=2#xx2248592xx[^] I actually never realized there was a "search forum" link (I was expecting a textbox with a search button). Typed in "algorithm" and found it on the second page: Genetic Programming 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
Bassam Abdul-Baki wrote:
The Lounge is, the SoapBox isn't worth it.
Yeah. Search "global warming" on google and it points you to the CP soapbox. All that hot air, you know. :) Marc
-
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?
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
-
Dang. What do you know. I found it: http://www.codeproject.com/lounge.asp?msg=2248592&ForumID=1159&searchkw=algorithm&sd=13%20Jul%202007&ed=11%20Oct%202007&stype=1&Page=2#xx2248592xx[^] I actually never realized there was a "search forum" link (I was expecting a textbox with a search button). Typed in "algorithm" and found it on the second page: Genetic Programming Marc
-
Bassam Abdul-Baki wrote:
The Lounge is, the SoapBox isn't worth it.
Yeah. Search "global warming" on google and it points you to the CP soapbox. All that hot air, you know. :) Marc
Marc Clifton wrote:
Yeah. Search "global warming" on google and it points you to the CP soapbox.
Which in turn is used by both sides of the outside world and back in turn by the soapbox people. It's like a dog chasing its own tail. Pointless, but a whole lot of fun for some. :)
"You can lead a horse to Vista, but it won't get in stall." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
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:
except the multiplication is our normalized number and the plus and minus were roughly half that computation.
Actually +-* are all pretty close on modern cpus. :) but I did run some quick numbers to see, the results were interesting. :)
_________________________ 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:
except the multiplication is our normalized number and the plus and minus were roughly half that computation.
Actually +-* are all pretty close on modern cpus. :) but I did run some quick numbers to see, the results were interesting. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Dang. What do you know. I found it: http://www.codeproject.com/lounge.asp?msg=2248592&ForumID=1159&searchkw=algorithm&sd=13%20Jul%202007&ed=11%20Oct%202007&stype=1&Page=2#xx2248592xx[^] I actually never realized there was a "search forum" link (I was expecting a textbox with a search button). Typed in "algorithm" and found it on the second page: Genetic Programming Marc
Hate to display my ignorance, but just where is this
Marc Clifton wrote:
"search forum" link
you refer too.
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
well, the results were surprising, so I am going back to check why... if htey are right it may make somethings easier for me. a+b 0.62 sec a-b 0.62 sec a*b 0.62 sec a/b 2.00 sec sin(b) 33.98sec cos(b) 35.59sec (those should be the same, which means maybe a cpu caching issue?) tan(b) 37.59sec atan2(a,b) 27.85sec atan(a/b) 38.43 (I knew it was better to do atan2 instead of division, but I didn't expect that) sqrt(b) 2.01 sec (that is the one that blew me away)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
well, the results were surprising, so I am going back to check why... if htey are right it may make somethings easier for me. a+b 0.62 sec a-b 0.62 sec a*b 0.62 sec a/b 2.00 sec sin(b) 33.98sec cos(b) 35.59sec (those should be the same, which means maybe a cpu caching issue?) tan(b) 37.59sec atan2(a,b) 27.85sec atan(a/b) 38.43 (I knew it was better to do atan2 instead of division, but I didn't expect that) sqrt(b) 2.01 sec (that is the one that blew me away)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
There are plenty of optimized sqrt methods, I'm not sure which one's the least computation required. I would expect cos to be slightly less than sin since it starts with 1 (constant), but without knowing what they're doing, they could be slightly different. The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
"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
-
There are plenty of optimized sqrt methods, I'm not sure which one's the least computation required. I would expect cos to be slightly less than sin since it starts with 1 (constant), but without knowing what they're doing, they could be slightly different. The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
"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
Bassam Abdul-Baki wrote:
I'm surprised nobody has put all of those and the different processors in a table?
because they change per processor, and SSE series, etc. Add in cached loops and dropped caches, etc. and you have a mish-mash that most vendors just say "profile it" and see.
_________________________ 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:
I'm surprised nobody has put all of those and the different processors in a table?
because they change per processor, and SSE series, etc. Add in cached loops and dropped caches, etc. and you have a mish-mash that most vendors just say "profile it" and see.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
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.
"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
-
There are plenty of optimized sqrt methods, I'm not sure which one's the least computation required. I would expect cos to be slightly less than sin since it starts with 1 (constant), but without knowing what they're doing, they could be slightly different. The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
"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
Bassam Abdul-Baki wrote:
The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
Because it's pretty much useless for comparing algorithms. An algorithm complexity is different than an algorithm running time; I can show some O(n!) algorithms that run fast for some mid to large size dataset, but once you pass a certain size the running time just jumps and prove the complexity of said algorithm.
Maximilien Lincourt Your Head A Splode - Strong Bad
-
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
You might have had better luck if you had posted this in the Algorithms/Math board!