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 Next 
Author 

Azu 03 Sep 2009, 17:45
revolution wrote:


03 Sep 2009, 17:45 

LocoDelAssembly 03 Sep 2009, 17:54


03 Sep 2009, 17:54 

Azu 03 Sep 2009, 17:59
Thanks for backing me up.


03 Sep 2009, 17:59 

LocoDelAssembly 03 Sep 2009, 18:16
Backing you up? Ok...


03 Sep 2009, 18:16 

Borsuc 03 Sep 2009, 18:16
Quote: As we’ll see, the asymptotic run time of an algorithm gives a simple, and machine independent, characterization of it’s complexity. _________________ Previously known as The_Grey_Beast 

03 Sep 2009, 18:16 

Azu 03 Sep 2009, 18:28
When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1).
Loops, for example, are O(N), where as jump tables are O(1). I'm really not sure what the ambiguity is. 

03 Sep 2009, 18:28 

revolution 03 Sep 2009, 18:36
Azu wrote: When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1). 

03 Sep 2009, 18:36 

Azu 03 Sep 2009, 18:42
revolution wrote:
If bigO notation isn't right for what I described then please just tell me what is, because that's always how I've seen it used. 

03 Sep 2009, 18:42 

revolution 03 Sep 2009, 19:08
Alexander Pope (1688  1744) wrote: A little learning is a dangerous thing; drink deep, or taste not the Pierian spring: there shallow draughts intoxicate the brain, and drinking largely sobers us again. 

03 Sep 2009, 19:08 

Azu 03 Sep 2009, 19:10
If you don't know just say so.


03 Sep 2009, 19:10 

revolution 03 Sep 2009, 19:12
Azu wrote: If you don't know just say so. 

03 Sep 2009, 19:12 

Azu 03 Sep 2009, 19:13
About what you replied to..
Azu wrote: If bigO notation isn't right for what I described then please just tell me what is 

03 Sep 2009, 19:13 

revolution 03 Sep 2009, 19:16
SIMD gives linear speed up, like I mentioned earlier. If that is not what you are asking then please explain more what you want to know and I will answer if I can.


03 Sep 2009, 19:16 

Azu 03 Sep 2009, 19:19
These
Azu wrote: Here's an example; Azu wrote: When an algorithm needs ran n times (where n is how many elements you feed to it) to get the result, it is O(N) complexity. If it only needs ran once for however many elements it processes, it is O(1). You said bigO notation is not like that, so I am asking; what is the right notation to use for it? 

03 Sep 2009, 19:19 

revolution 03 Sep 2009, 19:30
You need to understand that bigO has a hidden factor 'c' that is not stated in any mathematical document. This factor 'c' is the linear factor and is not important to arithmetic complexity measurements hence it is ignored. This factor 'c' is where the CPU clocks rates and SIMD will have an effect.
So you would kind of get c×O(something)  although you will never see that in any literature. The part in the brackets cannot ever be changed just by using wider instructions or different instructions or faster clock rates any any other linear speed up. 

03 Sep 2009, 19:30 

Azu 03 Sep 2009, 19:33
The hidden "c" is how long the algo takes to run and n is how many times it needs ran.. so didn't I use bigO correctly then?
If you can do between 1 and 16 of something at once via SIMD, then isn't it O(1) as long as there is under 17? Where as with normal instructions that work on 1 byte at a time it would be O(n).. what is wrong with this? I don't understand how I am misusing it. 

03 Sep 2009, 19:33 

revolution 03 Sep 2009, 19:38
Azu wrote: The hidden "c" is how long the algo takes to run and n is how many times it needs ran.. so didn't I use bigO correctly then? 

03 Sep 2009, 19:38 

Azu 03 Sep 2009, 19:42
If you can do up to 4 at once.. then wouldn't it be O(1) as long as you are doing less than 5 adds? Where as if you did them one at a time using nonSIMD then it should be O(N)..
Here's a way to put it without needing the "as long as you are doing less than X"; n=How many x=How many of them you can do at once O(1+floor(n/x)) Shouldn't this be correct always? Last edited by Azu on 03 Sep 2009, 19:45; edited 2 times in total 

03 Sep 2009, 19:42 

revolution 03 Sep 2009, 19:44
Your understanding of N is not correct. N is a measure of the input size, not a loop count or any other CPU specific thing.


03 Sep 2009, 19:44 

Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.