flat assembler
Message board for the users of flat assembler.

Index > Windows > Disable SMT for my process?

Goto page Previous  1, 2, 3, 4, 5, 6, 7
Author
Thread Post new topic Reply to topic
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
c+N doesn't change the algorithm though. The c is just a constant overhead always there, outside of the loop. In my example the algorithm itself is changed.. to the point where most of the time, changing N doesn't change complexity.



P.S.:
Anyways, if big-O doesn't work where there is a maximum number of elements, big-O doesn't work for computers, since they have finite resources.
Post 04 Sep 2009, 15:43
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17664
Location: In your JS exploiting you and your system
revolution
Azu wrote:
P.S.:
Anyways, if big-O doesn't work where there is a maximum number of elements, big-O doesn't work for computers, since they have finite resources.
In a sense you are correct, big-O is just an approximation. But it is a very useful tool so don't be too hasty to discount it.
Post 04 Sep 2009, 15:47
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
It should be versatile enough to take limitations into account, I think.

For example, you have two algorithms, and neither of them can process over a million elements.. wouldn't it make sense not to calculate past 1 million then? One of them might theoretically scale way better if it goes to infinity, but since that can't happen, your results could be incorrect..
Post 04 Sep 2009, 15:50
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17664
Location: In your JS exploiting you and your system
revolution
Azu wrote:
It should be versatile enough to take limitations into account, I think.

For example, you have two algorithms, and neither of them can process over a million elements.. wouldn't it make sense not to calculate past 1 million then? One of them might theoretically scale way better if it goes to infinity, but since that can't happen, your results could be incorrect..
This is already a known caveat with big-O.
Post 04 Sep 2009, 15:52
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
revolution wrote:
Azu wrote:
It should be versatile enough to take limitations into account, I think.

For example, you have two algorithms, and neither of them can process over a million elements.. wouldn't it make sense not to calculate past 1 million then? One of them might theoretically scale way better if it goes to infinity, but since that can't happen, your results could be incorrect..
This is already a known caveat with big-O.
Is there a version of it that isn't like this? Like big-P or something?
Post 04 Sep 2009, 15:55
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
Azu wrote:
P.S.:
Anyways, if big-O doesn't work where there is a maximum number of elements, big-O doesn't work for computers, since they have finite resources.
Big-O tells you the mathematical relationship as N increases -- is it linear? is it exponential? That's the question it answers.

It does not tell you when X is faster that Y, depending on N. It tells you the relationship of the functions as they increase.

Bubble Sort increases quadratically, known fact. That is what Big-O tells you, not that it would run slower than quicksort for TWO elements (which is false, it's obviously faster).

Also I said before the "upper limits" are conditions imposed in the function, and conditions do not work in mathematics with a single notation.

What if you have a function that checks if N is prime (let's say MAGICALLY does so in 1 clock cycle), and if it is, then it does operation X which is O(N^2), otherwise operation Y which is O(N).

How would you rate such function's complexity? It is impossible to do it with one Big-O notation. You can apply conditions like "if N isn't prime, O(N), otherwise O(N^2)" but that uses two notations as you can see...

_________________
Previously known as The_Grey_Beast
Post 04 Sep 2009, 15:57
View user's profile Send private message Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
I used two notations though


I said if N<17 O(1) else O(ceiling(n/16))



P.S. your function does not need magic, it needs huuuuuuuuuuuge LUT.
Post 04 Sep 2009, 16:00
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17664
Location: In your JS exploiting you and your system
revolution
Azu wrote:
... big-P ...
Yeah, umm, sorry what was that you were saying, I just had to go take a big-P, but I am back now. Razz
Post 04 Sep 2009, 16:02
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
Correct but in that case, it's like you have two functions. The actual function must have the condition, not just your classification (e.g if you called a different function if N>=17, then it would qualify) Smile

_________________
Previously known as The_Grey_Beast
Post 04 Sep 2009, 16:02
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17664
Location: In your JS exploiting you and your system
revolution
Azu wrote:
P.S. your function does not need magic, it needs huuuuuuuuuuuge LUT.
And a sloooooooooooow clock so make it only take one cycle.
Post 04 Sep 2009, 16:03
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
Unless the huuuuuuuge LUT is in the cache Smile
Post 04 Sep 2009, 16:04
View user's profile Send private message Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
Borsuc wrote:
Correct but in that case, it's like you have two functions. The actual function must have the condition, not just your classification (e.g if you called a different function if N>=17, then it would qualify) Smile

Like this? Confused
Code:
cmp ecx,16
ja loopz
movdqa xmm0,dqword[esi]  
movdqa xmm1,dqword[edi]  
paddb xmm0,xmm1  
movdqa dqword[edi],xmm0
ret
loopz:
movdqa xmm0,dqword[esi]  
movdqa xmm1,dqword[edi]  
sub ecx,16
paddb xmm0,xmm1  
movdqa dqword[edi],xmm0
jns loopz
ret    



revolution wrote:
Azu wrote:
P.S. your function does not need magic, it needs huuuuuuuuuuuge LUT.
And a sloooooooooooow clock so make it only take one cycle.
i7s have slow clocks Very Happy

_________________
Post 04 Sep 2009, 16:06
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4, 5, 6, 7

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.