http://forums.leaflabs.com/topic.php?id=209 A place to share, learn, and grow... en-US Fri, 22 Jan 2016 00:19:16 +0000 http://bbpress.org/?v=1.0.2 q http://forums.leaflabs.com/search.php http://forums.leaflabs.com/topic.php?id=209&page=4#post-2431 Thu, 11 Nov 2010 20:03:16 +0000 gbulmer 2431@http://forums.leaflabs.com/ <p>mbolivar - &lt;&gt;If you have an implementation you'd like included in libmaple, I'm sure we'd be grateful. &lt;/&gt;</p> <p>I found the book we used for Shell sort. It was dark red, and not green, which slowed me down a lot :-)</p> <p>It was "Handbook of Algorithms and Data Structures in Pascal and C" by G H Gonnet, ISBN 0-201-14218-X Copyright 1984. My copy has a note before the preface to say the code is available on 9 track tape, 1600bpi, for US$95. So not a good candidate for Maplelib.</p> <p>Th=at book has been superceeded by the <a href="http://www.amazon.com/Handbook-Algorithms-Data-Structures-Pascal/dp/0201416077">1991 edition</a></p> <p>For the 1991 book there is a web site <a href="http://www.dcc.uchile.cl/~rbaeza/handbook/hbook.html" rel="nofollow">http://www.dcc.uchile.cl/~rbaeza/handbook/hbook.html</a><br /> with the source code.<br /> So the Shell sort is at <a href="http://www.dcc.uchile.cl/~rbaeza/handbook/algs/4/414.sort.c.html" rel="nofollow">http://www.dcc.uchile.cl/~rbaeza/handbook/algs/4/414.sort.c.html</a><br /> I think we futzed with the step values, maybe from Knuth.</p> <p>Anyway, I have't found the license on that code, but it may be a suitable starting place for maplelib. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1638 Tue, 05 Oct 2010 13:16:16 +0000 poslathian 1638@http://forums.leaflabs.com/ <p>yup you want that other paren ;) </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1636 Tue, 05 Oct 2010 13:06:50 +0000 StephenFromNYC 1636@http://forums.leaflabs.com/ <p>Hello,</p> <p>I like both perry's software version and postlathian's hardware method. Both are useful, depending on the application (eg. physical access to the button).</p> <p>Perry, I think you are missing a close parenthesis after "available()".</p> <p>Is this the correct code?</p> <p><code><br /> setup() {<br /> while(!SerialUSB.available())<br /> ;<br /> SerialUSB.println("Hello!");<br /> }<br /> </code></p> <p>Thanks!</p> <p>Stephen from NYC </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1634 Tue, 05 Oct 2010 12:58:30 +0000 poslathian 1634@http://forums.leaflabs.com/ <p>I often do:</p> <p>setup() {<br /> pinMode(38,INPUT); // BUT button<br /> while(!digitalRead(38));</p> <p> // tap button to start (starts on DOWN)<br /> } </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1630 Tue, 05 Oct 2010 12:13:42 +0000 perry 1630@http://forums.leaflabs.com/ <p>here's what i do to make sure i din;t miss anything coming out of the serialusb:</p> <pre><code>setup() { while(!SerialUSB.available() ; SerialUSB.println(&quot;Hello!&quot;); }</code></pre> <p>this will make the maple wait until a key is pressed in the serial monitor and then start spewing stuff out. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1629 Tue, 05 Oct 2010 11:58:25 +0000 poslathian 1629@http://forums.leaflabs.com/ <p>about auto-reset:<br /> Hmm. We could add auto-reset on terminal open as selectable feature. I agree with you that it has its uses. Right now, *most* (and in the IDE this is enforced) terminals will only send data when DTR is high. Thus, by forcing DTR low and then sending data, you are doing something beyond the normal bounds of operation. We poll these bytes for 1EAF, if found we reset. This code is strictly part of the libmaple SerialUSB driver, so any nonstandard USB stack would not have this included. Since well behaving terminals should set DTR when writing, this magic number check is not really a performance hit nor easy to do by accident. DTR toggling does nothing by itself (no reset). getDTR(),getRTS() are already in libmaple!</p> <p>SerialUSB fix:<br /> Nope, not a DTR based fix. this is a hardware fix. Im leave it to everyone to guess what the change is going to be, but we arnt ready to announce hardware changes in Rev6 just yet. How will this affect current users? Not at all, the new hardware will be a separate board in the drop down menu. However, if you wish to use the new scheme, we *might* (if requested) offer very low cost adapter boards (0 profit) that will add the new hardware to old maples via the JTAG port, perhaps ugly - but it will make everything behave equivalently. The change should not affect the library at all, so all sketches etc remain unchanged. We have tried many many permutations of driving the USB to maintain correct operation across the various operating systems, and we think this is a low cost high value fix that makes neat new features possible to boot. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1626 Tue, 05 Oct 2010 11:37:59 +0000 gbulmer 1626@http://forums.leaflabs.com/ <blockquote><p>1) Auto-reset on terminal open:<br /> One thought for reset control is to directly use DTR/RTS to control the reset, so that opening a terminal program will engage the autoreset. I think this is clearly the wrong thing. </p></blockquote> <p>I agree with you for general terminal program.<br /> The issue was/is when reoppening the IDE's serial monitor on the Arduino, it auto-resets.<br /> That is a very nice behaviour for new users, who can try their programs out very easily without losing any of their print output.<br /> If that is implemented, I would like it to be an option that I can switch off.</p> <blockquote><p>Surely you want to decouple opening a terminal window from program flow unless you program this in explicitly (via getDTR(), getRTS()). </p></blockquote> <p>A completly agree. That's what I want, and I think is the most general purpose. One can press the rest button if one needs a Reset. I don't want opening a connection to the Maple to reset it. We had a horrible job to defeat that on older Arduino's when my chum Mark wrote a ICSP using the Arduino.</p> <blockquote><p>So, currently, the auto-reset works via pulling down DTR and then sending along some magic numbers (0x1EAF). </p></blockquote> <p>That sounds okay. I think I could (at a push) defeat that on a Mac, if I really needed to (using DTrace). BUt I assume it's an option with some of the terminal emulators.</p> <p>Does puling down DTR stop the user program, or is it still running?<br /> Is the reset only done when the magic number comes along too?<br /> If the user program is a different kind of USB device, I assume none of this happens?</p> <blockquote><p>2) SerialUSB voodoo:<br /> Ugh, such voodoo. I dont want to get anyones hopes of of full fixes in 0.0.7, its a very hard problem (but have cleaned up a lot of related bugs in 0.0.7). However, we had the pleasure of talking it over a lot recently - and with a lot of users and developers of other products at maker faire - and have finally settled on a long term fix. Its a hardware fix, and a feature add, and were psyched. </p></blockquote> <p>Is it more than using DTR for out-of-band signaling? What other issues am I missing?</p> <p>So will this be practical for us to implement on existing boards?<br /> When will the change get rolled into Maple boards? </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1606 Tue, 05 Oct 2010 08:52:45 +0000 poslathian 1606@http://forums.leaflabs.com/ <p>In no particular order, here are some quick comments to the topics covered on this thread:</p> <p>1) Auto-reset on terminal open:<br /> One thought for reset control is to directly use DTR/RTS to control the reset, so that opening a terminal program will engage the autoreset. I think this is clearly the wrong thing. Surely you want to decouple opening a terminal window from program flow unless you program this in explicitly (via getDTR(), getRTS()). So, currently, the auto-reset works via pulling down DTR and then sending along some magic numbers (0x1EAF). </p> <p>2) SerialUSB voodoo:<br /> Ugh, such voodoo. I dont want to get anyones hopes of of full fixes in 0.0.7, its a very hard problem (but have cleaned up a lot of related bugs in 0.0.7). However, we had the pleasure of talking it over a lot recently - and with a lot of users and developers of other products at maker faire - and have finally settled on a long term fix. Its a hardware fix, and a feature add, and were psyched. In the meantime if SerialUSB is really killing you, (and I hate to do this) please use the UART's with an FTDI for now - but with confidence that this problem will not plague this platform forever ;)</p> <p>3) The RAM/Flash contention. This IS a bootloader issue, the best we can do is a push changes into the bootloader git and if users want to use the serial-bootloader to upgrade then go for it! The issue is a throwback from before a permanent-bootloader mode didnt exist. What would happen is that botched code would get into flash, and everytime you restarted it would jump to bad flash code and crash. Meanwhile, bad ram code can be cleared with a power cycle, so everything was designed to heavily favor ram whenever there was a contention. Of course, with permanent bootloader this problem goes away, so we can do the "right thing" now. </p> <p>I have nothing to say about sorting algs ;) (although incidentally, I wrote a really bad merge sort the other day for my THX note synth) </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1601 Tue, 05 Oct 2010 02:18:49 +0000 snigelen 1601@http://forums.leaflabs.com/ <p>Interesting discussion you have. Just a small comment on this</p> <blockquote><p> <code>inc &lt;- round(inc / 2.2)</code></p> <p>The last line in particular is a definite deal-breaker on embedded hardware.</p> </blockquote> <p>With integer arithmetic you can do the same thing as (I think)<br /> <code>inc &lt;- (10*inc+5)/22</code> </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1594 Mon, 04 Oct 2010 18:15:40 +0000 gbulmer 1594@http://forums.leaflabs.com/ <blockquote><p>oh, and just a clarification on what i meant when i said</p> <blockquote><p>GCC does attempt to do tail call elimination, but that won't help here, since quicksort is not tail-recursive -- the presence of two recursive calls (on the left and right subarrays after the partition step) dooms us to needing the stack.</p></blockquote> <p>by "won't help", i meant that the stack size is asymptotically still logarithmic in the input length, since the first recursive call can't be eliminated. optimizing out the recursive call which _is_ in tail position will of course pare down the constant factors.</p></blockquote> <p>Agreed; in the worst case, flattening the tail call to an iterative solution makes no difference to the stack size. </p> <p>I am on thin ice here but, my vague recollection was that quicksort could choose which partition to recurse on, and which to iterate on. In many cases, the partitions are uneven, so recursing on the smaller partition, is a good strategy to reduce stack space requirements. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1591 Mon, 04 Oct 2010 17:23:13 +0000 gbulmer 1591@http://forums.leaflabs.com/ <blockquote><p>If you have an implementation you'd like included in libmaple, I'm sure we'd be grateful. </p></blockquote> <p>That was several jobs ago ...<br /> The battery backed "non-volatile" memory on my old IBM AT clone, gave up years ago, losing all the hard disk parameters, and rendering it useless :-(<br /> The 5 1/4" floppy 'backups" are just as useless (that was my only machine with a 5 1/4" disk drive).</p> <p>But, I think I might have the book that I copied from, somewhere :-)<br /> (I remember it had a dark-ish green cover)</p> <p>Paper, the only information back-up civilisation needs ;-) </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1573 Mon, 04 Oct 2010 09:29:39 +0000 mbolivar 1573@http://forums.leaflabs.com/ <p>gbulmer: one last thing.</p> <blockquote><p> I think you'll find Shell sort is slightly better than insertion sort <a href="http://en.wikipedia.org/wiki/Shell_sort" rel="nofollow">http://en.wikipedia.org/wiki/Shell_sort</a> under most conditions. In experiments we did (in the 80's) on sorting 3D polygons within a rendering engine, it often beat quicksort. (I've tended to use it, and always been pleased with its performance. It seemed overkill for this problem.) </p></blockquote> <p>This is fascinating. If you have an implementation you'd like included in libmaple, I'm sure we'd be grateful. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1572 Mon, 04 Oct 2010 09:11:24 +0000 mbolivar 1572@http://forums.leaflabs.com/ <p>oh, and just a clarification on what i meant when i said</p> <blockquote><p> GCC does attempt to do tail call elimination, but that won't help here, since quicksort is not tail-recursive -- the presence of two recursive calls (on the left and right subarrays after the partition step) dooms us to needing the stack. </p></blockquote> <p>by "won't help", i meant that the stack size is asymptotically still logarithmic in the input length, since the first recursive call can't be eliminated. optimizing out the recursive call which _is_ in tail position will of course pare down the constant factors. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1571 Mon, 04 Oct 2010 09:06:21 +0000 mbolivar 1571@http://forums.leaflabs.com/ <p>[a previous post deleted as it was a copy of yours]</p> <p>gbulmer:</p> <blockquote><p> I had a look, and it does the TCO by hand:</p> <p>if ((r = pd - pc) &gt; es) {<br /> /* Iterate rather than recurse to save stack space */<br /> a = pn - r;<br /> n = r / es;<br /> goto loop;<br /> } </p></blockquote> <p>I'm looking at it too; it's a cool implementation.</p> <p>As I'm sure you've seen, it switches to insertion sort at the leaves (n &lt; 7) and when the array appears to be almost sorted (swap_cnt == 0).</p> <p>From what I've just read about shell sort, it is equivalent to insertion sort when the array is small, so there's no difference at the leaves. And of course insertion sort performs well on almost-sorted data, so the motivation for its use there is clear, but I found it curious that they wouldn't use shell sort in that case, given that the array could still potentially be large and that shell sort is considered better (unless there is some property I'm missing). </p> <p>Here's some speculation as to why insertion might have been chosen, though:</p> <p>The Wikipedia shell sort has this to say about implementation:<br /> <a href="http://en.wikipedia.org/wiki/Shell_sort#Shell_sort_algorithm_in_pseudocode" rel="nofollow">http://en.wikipedia.org/wiki/Shell_sort#Shell_sort_algorithm_in_pseudocode</a></p> <pre> inc &lt;- round(n/2) while inc &gt; 0 do: for i = inc .. n − 1 do: temp &lt;- a[i] j &lt;- i while j &gt;= inc and a[j − inc] &gt; temp do: a[j] &lt;- a[j − inc] j &lt;- j − inc a[j] &lt;- temp inc &lt;- round(inc / 2.2) </pre> <p>The last line in particular is a definite deal-breaker on embedded hardware. </p> http://forums.leaflabs.com/topic.php?id=209&page=3#post-1569 Mon, 04 Oct 2010 08:54:37 +0000 mbolivar 1569@http://forums.leaflabs.com/ <p>so as i'm sure you've seen, newlib qsort switches to insertion sort at the leaves (n &lt; 7) and (i think) when the the array appears to be almost sorted (as determined by swap_cnt); however, in reading about shell sort, it seems that it's equivalent to insertion at small inputs, so no difference there.</p> <p>there is a hand-coded TCO on lines 213-221, which i'll include inline since it's short:</p> <blockquote><p> if ((r = pb - pa) &gt; es)<br /> qsort(a, r / es, es, cmp);<br /> if ((r = pd - pc) &gt; es) {<br /> /* Iterate rather than recurse to save stack space */<br /> a = pn - r;<br /> n = r / es;<br /> goto loop;<br /> } </p></blockquote> <p>so the second recursive call (which is of course in tail position) is manually optimized, as you suspected. </p>