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
Tomasz Grysztar wrote:


04 Sep 2009, 09:09 

Tomasz Grysztar
Azu wrote: Okay, so like I said a few pages back, my SIMD way is O(ceiling(n/16))) forever. Definitely not O(n) like the nonSIMD one. O(celiling(n/16)) is exactly the same thing as O(n). They both are linear. I suggest you should read more about limits and asimptotic behaviors. For example O(N) is the same as O(1000N), and O(N^2+1000N) is the same as O(N^2). 

04 Sep 2009, 09:12 

Azu
But it goes in steps of 16.. if it was O(n), then it would do 16 times less if given 1 input than it would if given 16.. but it does the same either way..


04 Sep 2009, 09:13 

Tomasz Grysztar
Really, O(16N)=O(N). Please confirm with some mathematical book if you don't believe me.
I know that limits might confusing, especially when you first meet them  but if you want to understand what theoreticians mean, you need to understand their notations first. Last edited by Tomasz Grysztar on 04 Sep 2009, 09:16; edited 1 time in total 

04 Sep 2009, 09:14 

Azu
I don't mean 16*N.. if it was 16*N, it would do 16 times less work if given 1 input than it would if given 16 inputs. I mean ceiling(N/16). It has no difference between 1 input and 16. There is difference between 16 inputs and 17 though. Same difference as between 1 input and 17.. so not linear, I think..


04 Sep 2009, 09:15 

revolution
Azu wrote: But it goes in steps of 16.. Last edited by revolution on 04 Sep 2009, 09:17; edited 1 time in total 

04 Sep 2009, 09:17 

Tomasz Grysztar
Azu wrote: I don't mean 16*N.. if it was 16*N, it would do 16 times less work if given 1 input than it would if given 16 inputs. I mean ceiling(N/16). That's the same thing. Since O(16N)=O(N), then O(N)=O(N/16). Tell me, but seriously, what is your level of mathematical education? 

04 Sep 2009, 09:18 

Azu
I didn't say n/16.. I said ceiling(n/16)..
If it is n/16, then again, giving it 1 input would make it do 16 times less work than giving it 16 inputs. My algorithm will work just as much for 1 through 16 inputs (and twice as much for 17 through 32 inputs, etc). So shouldn't it have a notation that reflects this? Look; N/16 does not equal N/15 or N/1 But ceiling(N/16) and ceiling(N/15) and ceiling(N/1) all equal the same.. see? Edit: wait.. I think I used the wrong math to describe this.. let me fix it before you reply please Last edited by Azu on 04 Sep 2009, 09:24; edited 1 time in total 

04 Sep 2009, 09:19 

Tomasz Grysztar
Azu wrote: I didn't say n/16.. I said ceiling(n/16).. This behaves asimptotically the same as linear. lim celing(n)/n = 1 Azu wrote: So shouldn't it have a notation that reflects this? Last edited by Tomasz Grysztar on 04 Sep 2009, 09:27; edited 1 time in total 

04 Sep 2009, 09:23 

Azu
Okay here is the right example. Sorry about my previous post;
n=16 N/16 does not equal n=15 N/16 or n=1 N/16 But.. n=16 ceiling(N/16) and n=15 ceiling(N/16) and n=1 ceiling(N/16) all equal the same.. see? This difference isn't linear.. so why doesn't at least O(ceiling(n/16)) work? It should work no matter how big the input is, I think.. where as the O(1) only works if it is below 17, and I get now that that is invalid use of the notation, since it must be self contained. 

04 Sep 2009, 09:25 

Tomasz Grysztar
Azu wrote: Okay here is the right example. Sorry about my previous post; Of course it IS linear. Just look at it for large input sizes. 

04 Sep 2009, 09:30 

Tomasz Grysztar
To show you on example:
N=100000 Nceling(N/16)=93750 N=1000000 Nceling(N/16)=937500 N=10000000 Nceling(N/16)=9375000 and so on, till the infinity. The growth of this difference is linear. Last edited by Tomasz Grysztar on 04 Sep 2009, 09:33; edited 1 time in total 

04 Sep 2009, 09:32 

Azu
I think the one on the left is linear ( O(n) ), but not the one on the right ( O(ceil(n/16)) ).. If it is linear, then whenever there is a different n, there should be different complexity, right? Last edited by Azu on 04 Sep 2009, 09:35; edited 1 time in total 

04 Sep 2009, 09:33 

Tomasz Grysztar
Azu wrote: I think the one on the left is linear ( O(n) ), but not the one on the right ( O(ceil(n/16)) ).. Asimptotically they both are. As I said, lim ceiling(N)/N = 1 Do you know what a mathematical notation of limit is? 

04 Sep 2009, 09:34 

Azu
ceiling(N) will always equal N if N is an integer.. there is supposed to be division done on it first to make it a float..
Like this lim ceiling(N/16)/N Last edited by Azu on 04 Sep 2009, 09:37; edited 1 time in total 

04 Sep 2009, 09:36 

Tomasz Grysztar
Azu wrote: If it is linear, then whenever there is a different n, there should be different complexity, right? The O(N) notation mean asimptotically linear, not the plain linear you know from elementary school. 

04 Sep 2009, 09:36 

Azu
n = 123
lim ceiling(N/16)/N does not equal 1 It equals 0.0650406504 

04 Sep 2009, 09:37 

Tomasz Grysztar
Azu wrote: ceiling(N) will always equal N if N is an integer.. there is supposed to be division done on it first to make it a float.. lim ceiling(N)/N = 1 even if we take real N, not integer one. As for the lim ceiling(N/16)/N, it is equal to 1/16, which tells us that asimptotically ceiling(N/16) is linear in relation to N. 

04 Sep 2009, 09:40 

Tomasz Grysztar
Azu wrote: lim ceiling(N/16)/N does not equal 1 True, it does not  it equal to 1/16. Azu wrote: It equals 0.0650406504 You haven't answered my earlier question. Do you know what a limit is? Last edited by Tomasz Grysztar on 04 Sep 2009, 09:41; edited 1 time in total 

04 Sep 2009, 09:41 

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.