flat assembler
Message board for the users of flat assembler.
![]() Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next |
Author |
|
Azu
But that is how I mean..
|
|||
![]() |
|
Azu
In my example the parameter is how many additions you are doing..
|
|||
![]() |
|
Borsuc
Then it is O(N)
![]() O(1) means that it is O(1), no matter the parameter (number of additions in this case), which is false, because it isn't constant. Bubble Sort is O(N^2), guess why. _________________ Previously known as The_Grey_Beast |
|||
![]() |
|
Azu
Because that algorithm must run N*N times!
If I have a SIMD instruction that can do up to 16 additions at once, then it is running 1 time, as long as 16 or less additions need done, where as non-SIMD way would need ran 16 times to do 16 additions, or 2 times to do 2 additions, or whatever..... |
|||
![]() |
|
revolution
Azu wrote: In my example the parameter is how many additions you are doing.. |
|||
![]() |
|
Borsuc
@Azu: More correct would be to say that, because as you increase N, the amount of "steps" (let's keep it at abstract mathematical level) required increases by N^2. Or in other words, doubling N will quadruple the number of steps required.
Azu, it is about the number of "steps" needed. Doing them in parallel doesn't change anything, there's still 2 steps whether you do both at the same time, or whether you do them twice as fast. _________________ Previously known as The_Grey_Beast |
|||
![]() |
|
Azu
No no no
The SIMD instruction will do the same amount of work whether you utilize the max amount of inputs it can work on at once or just give it 1 It's just that the excess will be wasted If it can do up to 16 at once and you give it say 3, it will be the same as if you give it 16.. it will take same amount of time, use same amount of resources, same complexity and everything. Different input but the complexity is constant. |
|||
![]() |
|
Borsuc
O(N) is theoretical mathematical representation -- there is no such thing as "waste" in math!
![]() But that's irrelevant anyway. O(N) is asymptotical analyzation. This means as N tends to infinity you take the limit (and derivative). It's the mathematical term for how it "tends". You know, with limits (lim x->oo, stuff like that), which is x^2 for N^2, and 1 for O(1), not even using x! (no parameter change after all) Asymptotes |
|||
![]() |
|
Azu
What I mean is, SIMD instructions do the same amount of work whether you are making full use of how much they can do or not. It doesn't vary based on how much work you need done. It can either handle however many operations you need or not. Hence O(1) whenever one of them is enough.
|
|||
![]() |
|
Borsuc
Yes you are correct, but that has nothing to do with Big-O notation. See my post above why
![]() _________________ Previously known as The_Grey_Beast |
|||
![]() |
|
Azu
Okay.. so what notation should I use instead?
I just want to express how many times an algorithm needs ran based on how much stuff it works on. Like this; loopy: mov al,byte[edi] add al,byte[esi] sub ecx,1 mov byte[edi],al lea edi,[edi+1] lea esi,[esi+1] je loopy Needs ran ecx times where as this; movdqa xmm0,dqword[esi] movdqa xmm1,dqword[edi] paddb xmm0,xmm1 movdqa dqword[edi],xmm0 Needs ran 1 time.. What is the correct notation that I should use to compare these? |
|||
![]() |
|
revolution
AFAIK there is no notation for such a thing. Mathematicians are generally not interested in linear speed-ups so I doubt they have developed any special notation for it (if someone knows otherwise I would be happy to learn). Only computer programmers seem interested in linear speed-ups, so perhaps the measure of runtime, or clock counts, or instruction count, or byte count, or something, is the best you can get.
|
|||
![]() |
|
Azu
Linear speadups? I'm talking about how many times you have to run the algorithm when you increase the number of inputs to it. That has absolutely nothing to do with runtime, clock counts, or instruction count. Look at my last example (before you ask, it's in the post right above yours).
|
|||
![]() |
|
revolution
Azu wrote: Linear speadups? I'm talking about how many times you have to run the algorithm when you increase the number of inputs to it. That has absolutely nothing to do with runtime, clock counts, or instruction count. Look at my last example (before you ask, it's in the post right above yours). |
|||
![]() |
|
Azu
No.. the required operations is constant as long as less than 17 inputs. Actually, it won't even work for >16 inputs, since I didn't put in any logic to handle that... so it's going to be constant no matter how many, lol. Where as the number of times the non-SIMD one will run is exactly how many inputs.
What is the notation for this? I think that, like I said, it should be "O(n)" for the non-SIMD one, and O(1) for the SIMD one if less than 17 inputs. Or x=16;how many it can do at once O(ceil(n/x)) to handle cases all the way up to infinitely, like I said a few pages back. (okay actually I changed it a little just now to make it more compact, but same result) You all keep saying that I am using the wrong notation so please tell me what is the right one to use for this. |
|||
![]() |
|
revolution
Okay, so you have 16 operations per loop. That means:
0=1 loops 1-16=1 loop 17-32=2 loops 33-48=3 loops etc. That is how linear works. |
|||
![]() |
|
Azu
For 0 through 16 it is 1 "loop" (not really a loop when it is just ran once though), like I said. Hence the "when N<17" qualifier I added to all my posts.
Last edited by Azu on 04 Sep 2009, 07:48; edited 1 time in total |
|||
![]() |
|
revolution
Azu wrote: You all keep saying that I am using the wrong notation so please tell me what is the right one to use for this. |
|||
![]() |
|
Azu
revolution wrote:
Code: ;func 1 loopy: loop loopy ;func 2 loopy: sub ecx,1 je loopy |
|||
![]() |
|
Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next < Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.