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
revolution wrote:


03 Sep 2009, 17:45 

LocoDelAssembly


03 Sep 2009, 17:54 

Azu
Thanks for backing me up.


03 Sep 2009, 17:59 

LocoDelAssembly
Backing you up? Ok...


03 Sep 2009, 18:16 

Borsuc
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
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
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
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
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
If you don't know just say so.


03 Sep 2009, 19:10 

revolution
Azu wrote: If you don't know just say so. 

03 Sep 2009, 19:12 

Azu
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
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
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
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
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
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
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
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 YouTube, Twitter.
Website powered by rwasa.