Topic for #qi-hardware is now Copyleft hardware - http://qi-hardware.com | hardware hackers join here to discuss Ben NanoNote, atben / atusb 802.15.4 wireless, and other community driven hw projects | public logging at http://en.qi-hardware.com/irclogs
<wpwrak>
quicksort moves a lot of things around. i don't need this. i can have this information in the code flow.
<mth>
what I described matches the "Partition-based general selection algorithm" section on that page
<wpwrak>
yeah. i basically want to unroll the thing.
<wpwrak>
like in the thee variables example. that one was small enough to keep in my head. i'm less optimistic about five ;-)
<mth>
the median of medians approach sounds useful
<mth>
you could do that with groups of 3 as well, if your poor little CPU doesn't have many regs
<mth>
you'd probably need special cases for sizes that are not powers of 3
<mth>
treating non-existing elements as infinity should be sufficient, I think
<mth>
ah no, then you might not get the actual median
<mth>
the groups of 5 approach should work equally well for groups of 3
<mth>
you just have to do more passes then
<wpwrak>
hmm. maybe i should draw the thing. maybe 5 is still manageable with a clear head.
<wpwrak>
since all this shold be n log n ... let's see ... 3 -> 2*3 = 6. i have 5 comparisons, close enough :)
<mth>
5! = 120, so you can do an exhaustive test on the median-of-5-elements code
<wpwrak>
naw, it can't be worse than n log n
<wpwrak>
otherwise, i could just use quick- or heapsort
<mth>
I mean, you can just test all possible inputs and if your code passes it's ok
<wpwrak>
sure. but that's excessive. even bubble sort would do better ;-)
<mth>
well, maybe duplicate elements could be tricky, so you might need a bit more test cases, but still 5^5 is manageable
<mth>
just for testing, not when actually running
<wpwrak>
5 log 5 is 11.6. so 12 is the goal :)
<mth>
eh, no-one said the constant was 1 ;)
<wpwrak>
ah yes, for testing the algorithm, i'll just do something like n^n. that runs on the pc, so cycles are dirt cheap :)
<wpwrak>
it's all a question of picking the right unit of measure ;)
<mth>
12 decacompares :)
<wpwrak>
well, 16 bit comparisons are already bad enough on an 8 bit mcu :)
<mth>
hmm, could you do something per bit?
<mth>
if you look just at the most significant bit and count the number of 0s and the number of 1s, the median will belong to the largest of those two groups
<wpwrak>
sloooaawwwwly :) but probably per byte
<wpwrak>
actually, gcc may do that for me if it's smart about its data flow analysis and applies it to machine instructions and not the abstract 16 bit operations. not sure if it's that good, though.
<mth>
I mean a different algorithm, where you'd look at one bit at a time
<wpwrak>
hmm. that sounds O(n^2)-ish
<mth>
O(N * log R), where N is array length and R is range
<wpwrak>
but yes, interesting approach if word operations are wordsize-times as expensive as bit operations
<wpwrak>
actually a bit faster
<wpwrak>
you have N for the first bit. something in [N/2, N] for the second, etc.
<wpwrak>
well, depends on how quickly you can filter our the ones you already know don't fit
<wpwrak>
should be fun to implement in an FPGA :)
<mth>
is it allowed to shuffle elements around or should they stay at their starting indices?
<wpwrak>
i think a copy is about as expensive as a compare. a swap twice that.
<wpwrak>
or maybe 1.5 times
<wpwrak>
so copying is expensive
<mth>
swap is the ideal operation for this kind of thing anyway
<wpwrak>
but code is relatively cheap -> unrolling
<wpwrak>
naw, i need to select, not to reorder
<wpwrak>
of course, i could conceptually swap, without actually doing it
<mth>
ah
<wpwrak>
e.g., if you say if (a < b) { swap(a, b); return something_else(a, b); }
<wpwrak>
then one cuold simply if (a < b) return something_else(b, a);
<wpwrak>
that's basically how you could read my 3 values example
<wpwrak>
there is no copying/swapping there
<mth>
ok, you swap variables, not array elements
<mth>
is it OK if the algorithm only works for odd-length arrays?
<wpwrak>
that's fine, yes
<wpwrak>
avoids the pesky decision whether to pick v[(n-1)/2] or v[(n+1)/2] :)
<mth>
it figures out the value of the median one bit at a time
<wpwrak>
heh, pretty cool, yes
<wpwrak>
if you have an architecture where this is efficient, it's a very neat algorithm
<wpwrak>
lower/higher don't seem to make sense, though (except for preventing you from running into the asser)
<mth>
they contain the number of elements below and above the range that matches the mask
<wpwrak>
ah, right. you need that.
<mth>
usually I would add more comments, but it's 3 am here and the natural language part of my brain is half asleep
<wpwrak>
otherwise, the choice would be the most popular bits but not the median
<mth>
somehow python is easier than English :)
<wpwrak>
oh, it's pretty much self-documenting :)
<mth>
yes, it has to pick the middle element of the entire array, not just of the examined subarray
<wpwrak>
but .. 10 bits, 5 variables, and a relatively expensive inner loop .. that's something like a factor 10 more expensive than what whould be possible with a compare and branch approach
<mth>
it's simple and not hugely inefficient, but it might not be the best solution for you
<wpwrak>
yeah, i'm afraid it'll be a pencil and paper exercise. first the tree, then balancing it ...
guanucoluis1 has quit [Remote host closed the connection]
nikescar has quit [Read error: Connection reset by peer]
nikescar has joined #qi-hardware
rejon has joined #qi-hardware
emeb has left #qi-hardware [#qi-hardware]
DocScrutinizer05 has quit [Disconnected by services]
DocScrutinizer05 has joined #qi-hardware
Ayla has quit [Quit: dodo]
ChanServ has quit [*.net *.split]
cladamw has joined #qi-hardware
emeb has joined #qi-hardware
emeb has left #qi-hardware [#qi-hardware]
rejon has quit [Ping timeout: 268 seconds]
jekhor has joined #qi-hardware
porchaso0 has joined #qi-hardware
porchao has quit [Read error: Connection reset by peer]
rejon has joined #qi-hardware
cladamw has quit [Quit: Ex-Chat]
rejon has quit [Ping timeout: 260 seconds]
rejon has joined #qi-hardware
scientes has quit [Ping timeout: 272 seconds]
jekhor has quit [Ping timeout: 246 seconds]
scientes has joined #qi-hardware
scientes has quit [Remote host closed the connection]
ChanServ has joined #qi-hardware
kristoffer has joined #qi-hardware
cladamw has joined #qi-hardware
ChanServ has quit [shutting down]
ChanServ has joined #qi-hardware
porchao has joined #qi-hardware
porchaso0 has quit [Read error: Connection reset by peer]
aisa has quit [Ping timeout: 272 seconds]
GNUtoo has joined #qi-hardware
jluis has quit [Quit: Me'n vaig]
jluis has joined #qi-hardware
kuribas has joined #qi-hardware
zear_ has joined #qi-hardware
zear has quit [Ping timeout: 260 seconds]
wej has quit [Ping timeout: 272 seconds]
wej has joined #qi-hardware
jurting_ has joined #qi-hardware
Jurting has quit [Ping timeout: 268 seconds]
cladamw has quit [Quit: Ex-Chat]
rejon has quit [Ping timeout: 255 seconds]
Hoolxi has joined #qi-hardware
kuribas has quit [Quit: ERC Version 5.3 (IRC client for Emacs)]
viric has quit [Quit: ep pleguem]
rz2k has quit [Read error: Connection reset by peer]
rz2k has joined #qi-hardware
porchaso0 has joined #qi-hardware
porchao has quit [Ping timeout: 244 seconds]
Ayla has joined #qi-hardware
<Ayla>
larsc, hi
<Ayla>
I'd like to extend your ohci-jz4740 driver to other JZ devices
<Ayla>
mind if I just rename "jz4740" to just "jz" on the filename and the code?
<larsc>
Ayla: usually that's not done, just use the driver as is for the other devices
xiangfu has joined #qi-hardware
<Ayla>
really.
<Ayla>
?
<Ayla>
so I just copy-paste the code?
<larsc>
no
<larsc>
keep it as it is and extend it where necessary
<larsc>
but don't rename everything
<Ayla>
mmmhh
Hoolxi has quit [Remote host closed the connection]