Re: [Ql-Users] Tyche
Tony Firshman wrote: Dilwyn Jones wrote, on 6/Apr/11 13:23 | Apr6: Norman Dunbar wrote: Afternoon all, On 06/04/11 10:52, Dilwyn Jones wrote: Gerard Phelan had the idea of asking a search engine how to pronounce it (now why didn't I think of that?). That's what I did too! http://www.forvo.com/word/tyche/ Interesting in that the word is Greek and is pronounced Tee-chee. Tyche is/was the goddess of [good] fortune. Also: Hmm, as Jonathan Oakley was apparently involved with the Tyche development, this makes sense, as many of the later QView projects were named after gods and godesses (Minerva, Hermes, etc etc) Minerva maybe but Lau and I dreamed up Hermes. It was not a Qview project. Tony Ah... but Tony... do you not remember scrabbling around looking for the Greek god of serial ports? ... On the Tyche front... I (and Johnathan) pronounce it exactly as the two words tie and key. The OED entry for the prefix tycho- (from Tyche) supports this: t - eye - k - oh t - as in tan eye - as in buy k - as in card, park oh - as in goat The Greek spelling of Tyche is tau-upsilon-chi-eta. The upsilon does its usual metamorphosis from a u sound to a y, as in psycho, The chi just gets left with a harder k sound. Much the same applies to the other Greek mortal, later goddess: Psyche (psi, upsilon, chi, iota). The Merriam-Webster will pronounce that one. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder athttp://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Announcement about the future of Ser-USB
Rich Mellor wrote: On 12/04/2011 22:04, Adrian Ives wrote: CUT 2) Yes, input; but the USBWiz can't do split baud rates and it isn't easy to do split rates on a standard QL without additional hardware and/or software. The input limitation is two stops at 9600. The USBWiz only sends one so it doesn't work. Therefore 4800 is the top speed. Hermes (as well as SuperHermes) cures this to some extent, allowing different baud rates for ser1 / ser2 input (as well as being different to the output baud rate). Hermes also supports just one stop bit at 9600 baud. The handshaking on serial input is also improved with Hermes, which would probably overcome the loss of characters you reported on standard QL hardware. Minerva provides the ability to have different output baud rates on ser1 and ser2 also. Just to explain... The original 8049 code used a buffer for serial data, with pointers to the next byte available, the next free space, AND a count of bytes in the buffer. It updated these three independently, which is insane, and could end up with them getting out of step with one another. There would be a byte, or bytes, in the buffer, but the counter said they were not there. No driver code in the 68K could EVER correct for this. At the time, various people (myself included) were getting into the Bulletin Board thing - and serial ports that were unusable after 4800 baud just weren't acceptable. Enter Hermes - a rewrite of the 8049 code from scratch. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder athttp://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Help wanted
Lee Privett wrote: Can anyone tell me what character 181 is in the Sinclair QL character font is? It is not printed in the QL User manual, not the ones I have anyway I cannot find the character in the standard window fonts, symbol or wingdings I cannot find it in the world list of currency symbols either It looks like a backward S with emphasis on the start and tail, and a squiggly bit under the bottom curve IIRC there were two mistakes in the QL font. The backward S with an under-dot was one of them. The other was the O with upper and lower diæreses. I don't recall what they were intended to be, but I do remember Jonathan Oakley saying (I think) that the person doing the font just did them based on a hand-written layout, and just made the characters look like that. In Minerva, I stole the former character, and made it a little digraph of the letters Q and V - for QView. The latter I just left alone. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder athttp://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Announcement about the future of Ser-USB
Adrian Ives wrote: ... - If QDOS decides that it's time to flush a slave block then - that's it - you WILL flush that slave block! It doesn't matter what your driver is doing, or whether it needs that block in memory. You WILL flush it - and just for good measure you are prohibited from returning an error code to QDOS to say that it failed! This is pretty much a show stopper. The current driver uses a double cache system that transfers the block into a holding area to be written when current I/O is finished, but if there is a large volume of data going through the driver it's hard to interleave the flush request correctly. - As a further bonus, if QDOS has decided that you WILL flush a large number of slave blocks, the driver will exhaust all of the available memory trying to double buffer the requests. - I could disable slave block handling altogether, but then every single request would generate serial I/O, slowing the driver down to an unacceptable level of performance. ... I believe you are misusing slave blocks. They are not intended to be used for general I/O buffering. If you want that, allocate memory from the common heap. Ideally, slave blocks are used just to mirror data present on a mass storage device, and being asked to release it is completely simple. The driver doesn't even get told about that. The microdrive code does use them for data to be written, and causes anything that makes any sort of memory allocation request - if the allocation needs space - to hang until the microdrive completes flushing the slave blocks (or fails!). As a flush of slave blocks can be triggered for any sort of memory request - from the common heap, expanding (a) SuperBasic, or RESPR - you have to work within that. The microdrive driver does just that. When it finds that it cannot flush a dirty slave block, it treats it as a microdrive bad or changed medium error. That's after seven times around the tape, which I think equates to roughly a minute before the triggering memory request might get serviced. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder athttp://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Announcement about the future of Ser-USB
Adrian Ives wrote: - As a further bonus, if QDOS has decided that you WILL flush a large number of slave blocks, the driver will exhaust all of the available memory trying to double buffer the requests. How can the driver exhaust all of the available memory. when it is not permitted to allocate memory while flushing slave blocks? ... My other comment, The driver doesn't even get told about that. was about the fact that the driver does not get called for slave blocks whose data is accessible. They are silently returned to the pool. * Workhorse for releasing slave blocks, most of this was in io_slave reglist reg d0-d1/d3/a0-a4 sb_slave movem.l reglist,-(sp) move.w #sv_fsdef2(-256)!$f0,d1 mask for drive id and part offset assert 0,bt_stat and.b (a1),d1 pick out drive bits from status asr.w #2,d1 shift id to make pointer to table move.l sv_fsdef63(a6,d1.w),a2 get physical definition block move.l fs_drivr(a2),a4 driver linkage address lea -sv_lio(a4),a3 base of driver definition block move.l ch_slave(a4),a4 get entry point of slave jsr (a4) movem.l (sp)+,reglist sb_allop moveq #bt.actn,d2 set up action (read or write) mask and.b (a1),d2 is action pending bne.s sb_slaveyes - go ensure slaving sf (a1)take this block ea_top add.l d3,a1 move pointer to next one ea_bot subq.l #bt_end,d0 bge.s sb_allopany more blocks? bra.s ok_rts -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder athttp://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] A small machine code program...
Tony Firshman wrote: Marcel Kilgus wrote, on 26/Nov/10 17:02 | Nov26: Marcel Kilgus wrote: 1for i=1to 100 2a$=:if i mod 3=0:a$=FIZZ 3if i mod 5=0:a$=a$BUZZ 4print i,a$:next i (91 bytes including 4 LF) Damn, missed something: 1for i=1to 100 2a$=:if i mod 3=0:a$=FIZZ 3if i mod 5=0:a$=a$BUZZ 4print i,a$:next (89 bytes including 4 LF) 1i=i+1 2a$=:if i mod 3=0:a$=FIZZ 3if i mod 5=0:a$=a$BUZZ 4print i,a$:goto 1 82 bytes incl LF and CTRL SPACE after 100. This meets all Rich's requirements: -- The rules are simple - write out the values 1 to 100 on screen If the value is divisible by 3 write 'FIZZ' after the number If the value is divisible by 5 write 'BUZZ' after the number If the value is divisible by 3 and 5 write 'FIZZBUZZ' after the number -- Nothing about having to stop at 100 (8-)# Tony 1PRINT CHR$(RND(TO 255)):GO TO 1 (It might take a little while...) -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder athttp://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Message formatting
Marcel Kilgus wrote: Tony Firshman wrote: Usnet use inline so why not here? My 2 cents: I'm fully with Tony on this one but also think that it's a battle against windmills and thus cannot be won. Marcel ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm No. People eventually learn that top-posting is wrong (and contrary to everything, as it destroys all chance of following what has happened in a thread). They learn, when they notice that no one replies to their contributions. The practice is required netiquette, on NNTP newsgroups, as the early parts of a thread are no longer available. Joining a thread is made simple, when one can just read the thread, in correct, logical sequence, from top to bottom of the latest post. It is no different on a mailing list, where it makes it impossible for a newcomer to understand what a thread is about, it it has been mangled by out-of-sequence postings. I just ignore top-posted contributions, and never reply to them. Google: top-posting netiquette (PS. Hi all.) -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder at http://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Email address change
Tony Firshman wrote: I see. I am *very* glad I have disabled these fake smilies (8-)# - I guess then mine has to be written: (8- )# to avoid a fake one Neither of those show as a graphic smiley. I'm using Seamonkey. I don't have any extra smiley packages. BTW, I discovered the other day that Smiley central is an indirect source of malware. They have a clear statement of policy that they do not do any advert/tracking/malware themselves. However, there's a little sub-clause where they disown any responsibility for what the sites they link to might send you. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder at http://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Email address change
Dilwyn... why can't you use your *dilwynjones.co.uk* domain for email, seeing as that's already registered to you? If Fasthosts are being a pain, just transfer the domain to someone sensible. Laurence Reeves wrote: Dilwyn... why can't you use your *dilwynjones.co.uk* domain for email, seeing as that's already registered to you? If Fasthosts are being a pain, just transfer the domain to someone sensible. Dilwyn Jones wrote: Eh? I never had that one! I'm definitely not the only dilwynjones in Wales, it's quite a common name here. My silly mistake. I wasn't really thinking, when I looked up the domain name dilwynjones.co.uk, that it might not be registered to another Dilwyn Jones, viz: Dilwyn Jones Honeypots 8 Highclere Sunninghill Ascot Berkshire SL5 0AA GB Registered a year ago, for two years, with ukreg.com, but there's no website. It may be just used for email. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder at http://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Email address change
Tony Firshman wrote: Dilwyn Jones wrote: Laurence Reeves wrote: Dilwyn... why can't you use your *dilwynjones.co.uk* domain for email, seeing as that's already registered to you? If Fasthosts are being a pain, just transfer the domain to someone sensible. Eh? I never had that one! I'm definitely not the only dilwynjones in Wales, it's quite a common name here. He he - your mailer completely screwed up your reply. Not only did it not add the quote character '' to Lau's email, but it did not strip out Lau's sig (he had the correct '-- ' before his sig). This meant I had to edit Lau's text and manually copy your reply. What a hassle! You ought to configure your mailer for this mailing list! Anyway, dilwynjones.org.uk *is* free for around £3 a year from 123. Tony Not Dilwyn's fault at all. For some reason, something in the list handling chose to turn some plain newlines (\n) into equals signs with two newlines (=\n\n). That occurred to the post I sent (which I keep local copies of) when it appeared on the list. In particular, the signature introducer (a single line with precisely two hyphens and one space: -- ) was turned into a line with two hyphens, a space and an equals sign (-- =), which means nothing special. I've no idea what caused it. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder at http://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [Ql-Users] Email address change
Tony Firshman wrote: Dilwyn Jones wrote: I will be closing my Tesco.net email account soon, so please update your email address book. Please ensure that all emails to me are sent to: dilwyn AT uk6 DOT net with immediate effect. This is a Freeola email address, the company which has been hosting my website for some time now. The message form on my website will of course continue to work (famous last words!) You ought to buy a domain name and re-direct from that. You will then have the *one* email address for ever... jones though is taken (8-)# dilwynjones.org.uk is available I couldn't resist saying... *dilwynjones.org.uk* for the huge cost of... £2.99 a year. Of course, you get the website redirect at the same time, then you forget all this chopping and changing. Dilwyn... why can't you use your *dilwynjones.co.uk* domain for email, seeing as that's already registered to you? If Fasthosts are being a pain, just transfer the domain to someone sensible. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder at http://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] LBYTES
Dilwyn Jones wrote: With SBYTES you can do something like SBYTES ram1_test,address,0 which creates a not very useful zero length file. But if you try to LBYTES it back with LBYTES ram1_test,address you get the error message 'end of file' Seems more like a statement of fact than an error msg. Yes, quite right, I hadn't quite thought of it that way :-) Absolutely not right. They is utterly no reason for an LBYTES of a zero length file to report an error. You wouldn't think it appropriate if it reported an error when asked to do a file of 5,373 bytes? Why should 0 bytes be treated as some magically special case? It's a bug. -- Lau AS! d-(!) a++ c p++ t+ f-- e++ h+ r--(+) n++(*) i++ P- m++ ASC Decoder at http://www32.brinkster.com/ascdecode/ ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] QL Wiki
George Gwilt wrote: On 7 Apr 2007, at 16:04, Laurence Reeves wrote: (And Tony, I always pronounce it Wi-ki-pe-di-op-hi-li-ac. I invented the word. I can define the correct way to pronounce it! So there!) Er - rather hermpty dermptyish. Naturally! I also spell a thing with fins, gills and scales, that swims around in water... a ghoti. -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] QL Wiki
Tony Firshman wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Laurence Reeves wrote: George Gwilt wrote: On 7 Apr 2007, at 16:04, Laurence Reeves wrote: (And Tony, I always pronounce it Wi-ki-pe-di-op-hi-li-ac. I invented the word. I can define the correct way to pronounce it! So there!) Er - rather hermpty dermptyish. Naturally! I also spell a thing with fins, gills and scales, that swims around in water... a ghoti. .. courtesy of George Bernard Shaw I think. Apparently, probably not. As in, it seems to have been coined by a spelling reform enthusiast, but then supported by GBS. Anyway, I just decided I really facied some of those... you know... what are they... longish square cut things... you need a ghoughpteighbteau to make them from ah! chips! That's it. -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] QL Wiki
Rich Mellor wrote: On Sat, 07 Apr 2007 09:50:18 +0100, Tony Firshman [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 http://en.wikipedia.org/w/index.php?title=Sinclair_QL Does http://www.rwapadventures.com/ql_wiki/ offer any better features? Is there any sense it producing two? Unless Rich's one offers unique facilities, it seems to me to make more sense to us and update the wikipedia one. My thoughts were that it is easier to maintain one amongst the QL community - the main wiki one is just too broad and if you are not careful, you end up seeing Windows topics with the same names as QL ones - try looking up QDOS. I have also noticed that some of my additions to the main wiki get deleted - no idea why, obviously someone who disagrees However, what does everyone else think? Sorry Rich, but I'm with Tony on this. I missed noting where your Wiki was at the start of this, and hadn't got around to asking. I'm sure I could have worked it out. I was quite bemused as to what justification there might be for it. I'd ask questions like where is it hosted, is it archived, backed up, etc. I could understand having some more secure Wiki facilities for Quanta, say, but that's about it. If you've had problems on Wikipedia with people deleting your stuff, have you followed it up? Your changes would still be present in archival form, I believe. That's how they recover when silly people attack. (Signed: A Wikipediophiliac/Wikipedaholic) (Hey, I like the first one... exactly two letters per syllable.) -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] QL Wiki
Rich Mellor wrote: Ah I have found it - it has not been removed - someone has instead created a Sinclair QDOS entry - it is not easy to find though, as QDOS only takes you to the PC o/s page - the link is at the very top of this page. I'm sorry, but I cannot agree with it is not easy to find. I cannot IMAGINE it being easier! I think all in all, one QL wiki resource is what is needed - I tried looking for a few things, and yes, its fine that Pawn takes you to a page about Magnetic Scrolls, but with Prawn taking you to a page about the shellfish, how do you tie that into the Sinclair QL adventure of the same name? NO! That's just not true. Pawn takes you to a disambiguation page. You chose a route from that to get to the Magnetic Scrolls game. What's Prawn supposed to do? Wikipedia is very good, but it is the problem that it is a very general encyclopedia, it is sometimes hard to find the page relating to a topic which has the same name as another better known topic. I have never found it hard. If the information is there, disambiguations get you there. Once in a specialist area, direct links within those pages take you to the directly related stuff, with links back to disambiguations where relevant. It works. It works, if you put the information there. (And Tony, I always pronounce it Wi-ki-pe-di-op-hi-li-ac. I invented the word. I can define the correct way to pronounce it! So there!) -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] USBwiz USB to serial device
Marcel Kilgus wrote: Tony Firshman wrote: I will get one of these and play: http://www.ghielectronics.com/details.php?id=5sid=6 I've read the manual. Actually this is a pretty neat device and easy to program. The problem is the serial link. While it could be easily used to attach USB keyboards and mice to the QL, it's probably too slow for anything else (flash memory access, printing). I mean, we're talking the speed of a Microdrive here, even floppy discs are blazingly fast in comparison. Do I notice a comment on microdrives as /slow/? What is it... 7 seconds to transfer 100K - which equals somewhat better than 100 bits/sec. A floppy, once you allow for interleave, comes nowhere near that? I.e. when transferring the /whole/ of a microdrive, versus the /whole/ of a floppy. the floppy may just outperform the md. However, while transferring a single file, the md files are /usually/ contiguous (and for program load, this doesn't even matter), so the transfer rate is still high. but the floppy sectors will come up with every 3rd or worse and the performance will dive. Speeds come in many flavours. The access time, instantaneous date rate and sustained data rate, for example. For md, the access time is indeed crap (average 3.5 seconds!), but both the others are the same, and quite good. For a floppy drive, access time is not brilliant (300ms?), but the sustained rate is worse than 1/3rd of the instantaneous rate (to some extent dependent on formatting - and I'm assuming the standard interleave and skew, which are there for a good, if historic, reason :- ). Horses for courses, as ever. -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
Tony Firshman wrote: Incidentally Pipex puts the page in a frame. No they didn't. 11 did that. I've never worked out exactly why they do that. The *real* url is http://www.auni40.dsl.pipex.com/sime.html No Tony... the *real* URL is as I gave it. When I again move the files, as I have with my whole website twice already, they will still be accessible by my domain. That how you Universally Locate the Resource. ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
[EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: SNIP OK. So the random order - quicksort marginally outperforms heapsort. For the already sorted case, quicksort is rather better than heapsort, but its margin goes down as the count goes up. However, with the data all the same... ooopppsss my quicksort has fallen headlong into the O(n*n) trap. That has always been a 'failing' of the quicksort, when the data are in sorted order, it takes 'forever' to finish. I was taught that at college and was reminded of it when I wrote PrinterMaster 2 - I used a quicksort internally and if it was run twice, the first one was quick (the data were random) and the second took ages (the data were sorted already). In the end, I ripped the guts of the quicksort out and replaced it with some other sort, probably a bubble sort as I think the size of the array being sorted was limited to 200 entries or something. Then again, maybe I used something else instead. In reply to Per's comments earlier, as Norman in effect says, quicksort is *not* a good all-rounder. It is fast, but in order to be happy with that speed, you must accept a stack that grows to O(ln(n)) (O(n) with buggy code!) and the /guarantee/ that some data will take O(n*n) to sort. BTW. Quicksort does not, in principle, mind data that is initially sorted. Its /simplest/ implementation, which uses the first item as the median, has that problem. Ditto for using the last item. Just using the middle item gets around that, but in reality just hides the root problem: the worst case is always O(n*n). You are quite right to point out that bubblesort is maligned for all the wrong reasons. Even with 200 items, where the n/ln(n) means you should expect the sorting to take of the order of a 38 longer, if that means 38 microseconds, instead of one microsecond... In fact, in a genuinely real time application, given the choice of using one or the other, you would have choose bubblesort. When quicksort /does/ hit an O(n*n) case, it takes /vastly/ longer than bubblesort. ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
Dilwyn Jones wrote: The second one is much faster than the first. They both use O(n) stack space. The both have O(n*n) worst cases. They both use the first element as the mean, so will have O(n*n) when the data is initially sorted. I'd not use either. Timing checks I did on it some time ago show that Quicksort is good on mixed random data, Not is good, but it is very frequently good. which is usually where other sort routines slow down. Nope. True for some. Where the data is in pretty good sorted order already, other sort routines can be faster. Yes, for some others. Quicksort is a reasonable choice as a general purpose sort routine where the data distributions and array sizes aren't really known in advance. No. It is /not/. Mark Knight sent QL Today a listing some years ago of a sort called pigeon sort, which could be faster than Quicksort but it was much longer than these listings and I couldn't understand it at the time. It's the one that you use in post offices. Pigeonholes. Highly appropriate in /very/ specialised circumstances.. Improvement suggestions for the above listings welcome. I'm thinking about it... first I'm trying to build QLAY to run on Ubuntu, just for fun. Or maybe I'll re-implement SuperBasic - as Mono-based. In the short term, here's my C code for heapsort, hand edited to SB, and utterly untested! DEFine PROCedure pushroot REPeat down w=2*free+2:REMark save pointer and get right descendant IF w=count IF wcount:EXIT down ELSE w=w-1:REMark single leaf ELSE IF data(w-1)data(w): w=w-1:REMark larger leaf IF data(w)=nxt:EXIT down:REMark got max-heap property data(free)=data(w):REMark promote child and keep looking free=w END REPeat down data(free)=nxt END DEFine DEFine PROCedure heapsort(data, count) LOCal v,w,free,nxt:v=count/2 REPeat build IF v=0:EXIT build v=v-1 nxt=data(v):free=v:pushroot END REpeat build REPeat extract IF count=0:EXIT extract count=count-1 nxt=data(count):data(count)=data[0]:free=0:pushroot END REPeat extract END DEFine ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
Having cured the many bugs in my simple implementations, I now have a slightly more conventional set of results: The raw figures are at http://www.bergbland.info/2secs.txt and here. A spreadsheet... get http://www.bergbland.info/2secs.ods. The first section is the test code running with calls to a dummy routine that actually doesn't even try to sort the data, so the final column shows the time taken to shuffle the data. The figures there have already been incorporated in the later sections. As before, every test was run for two seconds and the result is the average time per execution of the particular sort routine. The figures in parentheses are the result of dividing the time by n*ln(n). Lines of code: quicksort:85(unreadable), heapsort:26(fairly obscure), mergesort:25(readable). My mergesort performs pretty badly. Not too surprising, as it's the shortest piece of code. :-) nosort: 1000 691ns(0ns) 678ns(0ns) 96620ns(13ns) 2000 682ns(0ns) 705ns(0ns) 192us(12ns) 3000 718ns(0ns) 717ns(0ns) 291us(12ns) 4000 720ns(0ns) 718ns(0ns) 389us(11ns) 5000 718ns(0ns) 719ns(0ns) 483us(11ns) 6000 717ns(0ns) 719ns(0ns) 581us(11ns) 7000 723ns(0ns) 720ns(0ns) 682us(11ns) 8000 721ns(0ns) 718ns(0ns) 785us(10ns) 9000 718ns(0ns) 719ns(0ns) 877us(10ns) quicksort: 1000 44699ns(6ns) 44881ns(6ns) 45895ns(6ns) 2000 89409ns(5ns) 88934ns(5ns) 94820ns(6ns) 3000 136us(5ns) 136us(5ns) 146us(6ns) 4000 181us(5ns) 180us(5ns) 198us(5ns) 5000 225us(5ns) 226us(5ns) 245us(5ns) 6000 271us(5ns) 270us(5ns) 295us(5ns) 7000 316us(5ns) 314us(5ns) 340us(5ns) 8000 362us(5ns) 361us(5ns) 387us(5ns) 9000 406us(4ns) 404us(4ns) 447us(5ns) heapsort: 1000 88687ns(12ns) 89078ns(12ns) 90234ns(13ns) 2000 176us(11ns) 179us(11ns) 194us(12ns) 3000 271us(11ns) 270us(11ns) 284us(11ns) 4000 359us(10ns) 360us(10ns) 373us(11ns) 5000 448us(10ns) 450us(10ns) 471us(11ns) 6000 538us(10ns) 544us(10ns) 595us(11ns) 7000 644us(10ns) 645us(10ns) 670us(10ns) 8000 724us(10ns) 719us(10ns) 759us(10ns) 9000 814us(9ns) 817us(9ns) 893us(10ns) mergesort: 1000 271us(39ns) 270us(39ns) 274us(39ns) 2000 741us(48ns) 740us(48ns) 743us(48ns) 3000 1004us(41ns) 1008us(41ns) 1014us(42ns) 4000 1216us(36ns) 1229us(37ns) 1270us(38ns) 5000 1669us(39ns) 1672us(39ns) 1717us(40ns) 6000 2220us(42ns) 2217us(42ns) 2257us(43ns) 7000 2711us(43ns) 2707us(43ns) 2786us(44ns) 8000 3232us(44ns) 3227us(44ns) 3308us(46ns) 9000 3567us(43ns) 3593us(43ns) 3652us(44ns) ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
P Witte wrote: Laurence Reeves writes: P Witte wrote: Quicksort is so much faster than any stable sort I know of, even when cheating, that its worth it ;o) Yeah, yeah. I, of course, agree totally. I cheat /all/ the time. Cheats I dont easily agree with are those that employ particular quirks of particular hardware or software that end up being a nightmare to debug or transfer years after the only programmer who ever understood it OD'ed on Jolt.. Ah! I see. Like all my Minerva code... I ramble about tmings To be frank, I dont understand my own implementation of quicksort in QUICKSORT anymore. 's funny... I don't understand most of my clever code. Here are some timings (QPC2 - 1.2GHz PC) etc NB. Filling with RND(0 TO d%) is a little skewed. Why should the range of values be the same as the population? I'd stick with RND(-32768 TO 32767), which /nearly/ avoids duplicates, or fill once with any set all differing (fiddly for strings), then O(n) shuffle each time. I did a shellsort implementation, but it didnt do for me. In fact I wrote SuperBasic versions of most of the algorithms in Knuth's TAOCP. Only three of them made it to assembler. This one beats them all hands down. Very true. My waffle about mergesort was a little tongue-in-cheek, as it is actually almost always considerably slower than quicksort. However, have a look at http://www.aims.ac.za/~mackay/sorting/sorting.html, especially the graph near the middle of the doc. I want one of those! NB. The simeq that appears in various places in the above page is, I feel, supposed to be asymptotically equal to which is #x2243;. It should maybe be sime;, but as the page doesn't even have a DOCTYPE, and is full of other html bugs, this didn't work in my SeaMonkey. -- Re your PS: the cases where quicksort goes all nasty, O(n*n), are non-trivial. In fact, quicksort is quite unusual, in that it sorts both initially correctly ordered data and /reverse/ order data in O(n*ln(n)). That's provided you go for the /third/ most trivial choice of median - the value at the middle of the list. The first and second most trivial choices - i.e. the first or last value - do give O(n*n). ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
P Witte wrote: Quicksort is so much faster than any stable sort I know of, even when cheating, that its worth it ;o) Yeah, yeah. I, of course, agree totally. I cheat /all/ the time. I did get a bit carried away... and perused the current net thinking on sort algorithms, and it would seem that the ancient mergesort has a lot going for it. You add O(n) extra memory to extend the key and make quicksort effectively stable. This adds cost to key comparisons. With mergesort, a similar O(n) extra memory /may/ be needed. However, and this is a /big/ however, the worst case (admittedly low probability) time for quicksort is O(n*n), whereas mergesort stays at O(n*ln(n))... indeed, its worst case is only twice as slow as its best case. I said above that extra memory /may/ be needed, because it depends on how the data is held. There is /no/ extra memory (barring O(ln(n))) if the data starts off as a linked list. The algorithm is also highly effective if the data is stored on disc, etc, rather than in memory. Algorithm for mergesort: If more than one element, split (arbitrarily) into two equal (or differ by one) chunks, recursively mergesort each, merge the two sorted chunks. 3767376 split 376 7376 split 3 76 7376 split 3 7 6 7376 merge 3 67 7376 merge 367 7376 split 367 73 76 split 367 7 3 76 merge 367 37 76 split 367 37 7 6 merge 367 37 67 merge 367 3677 merge 3366777 And now... my fertile mind... what if the split into two chunks actually was the odd and even indices within the array? Curiously, this could be done as a SuperBasic slice. The merge operation becomes /horrible/, and I haven't thought it through at all (except that the worst case looks to be O(n*n)!), but the whole thing becomes (close to) in-place. PS. I always feel shellsort is magic. PPS. http://en.wikipedia.org/wiki/Patience_sorting looks rather interesting. ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Quicksort
P Witte wrote: IIRC the resulting sort is stable allowing for an unambiguous fast binary search (also included) of the array(s) using the same criteria as for the sort. (That was at least my programming goal. I'll have to check this, though.) Sorry? I don't think I follow your banter. A stable sort is one where records with equal keys remain in the same order after the sort as they were before it. I'm certain that quicksort cannot do that. ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Bug?
Malcolm Lear wrote: Hi Is this normal behavior for a 68K processor. I'm doing a word comparison between a memory location and a data register. It seems that data in the most significant word of the register is effecting the result. In the example below the test ends up at notequal. Unfortunately I've not got access to a real CPU to try this on (only QPC). Malcolm start move.l #$,d0 lea test,a4 cmp.w(a4),d0 beq.sequal bra.snotequal test dc.w 0 equal nop notequal nop I suspect you have done a fumble(?) - indeed, notequal is always reached... especially via the nop at equal... There /is/ one anomalous .L/.W funny. On a MOVEM.L from memory to registers, all the registers get a (free!) EXT.L done on them. Normal for address registers (a .W operation on one of them /does/ always extend to long before an operation) but a little unusual for data registers. ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] Infinity
George Gwilt wrote: On 5 Jun 2006, at 16:16, George Gwilt wrote: On 4 Jun 2006, at 14:24, Laurence Reeves wrote: George Gwilt wrote: The IEEE format of signed infinities for the FPU on Q40 and Q60 is $ (minus infinity) $7FFF (plus infinity) The fifth zero could in fact be 8 as a viable alternative. I'm confused... where does IEEE come into this? I don't think the above have anything to do with IEEE754, at least. The Motorola FPUs probably try to be IEEE754, which would give the two infinities as $FFF0... and $7FF0... with no other representations. The Programmer's Reference Manual - M68000PM/AD REV.1 contains the following: - 1.5 FLOATING-POINT DATA FORMATS The following paragraphs describe the FPU's operand data formats. ... The FPU also supports three binary floating-point formats (single, double, and extended precision) that fully comply with IEEE 754 standard. The single precision infinities are: $FF80 (minus infinity) $7F80 (plus infinity) The double precision infinities are: $FFF0 (minus infinity) $7FF0 (plus infinity) The extended precision values are as given above. In that representation, the mantissa consists of an explicit integer bit and a fraction. For normalized numbers the integer bit is 1, for denormalized numbers the integer bit is 0 and for infinities the integer bit is defined as Don't Care. That is the reason that the fifth zero could be 8 as an alternative. This may alter the amount of confusion one way or the other. NOTE. There are three (3) instances of the use of an apostrophe in the foregoing. George Ah! I see what you've done - you've left off the *fifth* 16-bit words. It may or may not still be there, but http://srfi.schemers.org/srfi-58/mail-archive/msg00087.html agrees with what I thought. I haven't dug into exactly what the Motorola FPU does, but IEE754 *defines* only two formats - single (32-bit) and double (64-bit). It *suggests* extended (80-bit) as an implementation, and that's what Intel did. It's what they have their TBYTE opcode for - defining ten-byte entities, mainly for allocating space for push/pop of the FPU stack. Both single and double do /not/ have an explicit msb in the significand. Extended does. It requires *five* 16-bit words, the first of which is all used by the sign and a 15 bit exponent. The other four are a 64-bit significand, with an explicit msb. As extended is only suggested, the precise implementation details are not defined. With all the extra bits floating about, I guess pushing an extended infinity might not care what the significand msb shows... it ought not even care what any of the last forty bits of the significand happen to be! (That because the infinities ought to be push/pop-able as single without getting confused... but I'll bet they didn't do that. GIGO). (PS. I gather IEEE prefer significand to mantissa.) -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] apostrophes
Tony Firshman wrote: Surely if there is a plural, then it can be counted? Argh! See infinity. You can't count the points on a line (finite or infinite length). They are plural, but not countable. -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] apostrophes
David Tubbs wrote: Just to wind up this one, from way back, Tony Firshman wrote: Being me, I took TF at his word, that the rule should be countable, and went onto my infinity theme. Sorry Lau, I did not take your point correctly, but certainly a nit for the picking. Not my nit. TF's definition sounded wrong, somehow. I mentioned it to someone else. They gave me the correct (or should that be a /more/ correct) rule: Use 'fewer' iff plural. No mention of counting. Who else uses iff for if, and only if,? All the logicians and mathematicians, stand up please. The rest of you (philosophers excepted, if they exist) can sit down. but does the of a finite line by the zero magnitude of the point need such a bulky demo ? I don't think I understand your banter... I never mentioned a finite line or a zero magnitude and I don't suffer from BD. -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] apostrophes
PS. (this is a Pre-script, just for variety). I've always liked: While marking their work, the teacher noted that John had written had, whereas Jim had had had had. Had had had had the teacher's approval. Just to wind up this one, from way back, Tony Firshman wrote: One very common one now is to use 'less' for everything, where 'fewer' should be used. Less people for instance. The rule is *so* simple. If one can count the noun (ie discrete items) then it is 'fewer'. http://www.askoxford.com/asktheexperts/faq/aboutgrammar/lessfewer?view=uk http://www.gcse.com/english/less.htm Being me, I took TF at his word, that the rule should be countable, and went onto my infinity theme. Firstly, I asked another friend about this, and he instantly said that the rule is just fewer with a plural and less if not (I think that makes sense). The plural does not have to be countable, hence there are infinitely fewer calculatable numbers than there are points on a straight line. Secondly, you might like to read the first chapter of The Emperor's New Mind, by Roger Penrose. It could give you a feel for why the number of computable numbers is countable, versus points on a line, which aren't. Thirdly, the IEEE spec actually allows a choice of one (projective) or two (affine) infinities. The projective one is an unsigned infinity, and is what happens when cartographers project the globe onto a plane. You sorta have the south pole at the center of the plane and the north pole is projected off to infinity, all round the plane. The IEEE spec does allow a few operations involving infinities. It will happily let you add anything finite to an infinity with a quibble - the infinity is not affected. It will even allow two similarly signed infinities to be added together, and remain the same, and so on. Fourthly, the main sort of mathematical infinities that crop up are the Aleph sequence (Hebrew alphabet - or should that say alephbeth?). Aleph-null is the countable infinity, aleph-one is the first non-countable infinity. Have a look on Wikipedia http://en.wikipedia.org/wiki/Aleph_number. Fifthly, there are other number systems that can do sums just like the conventional stuff(sic), but can handle infinity plus one as a distinct number, which you can add one to and get infinity plus 2, and so on. language head=need aspirin handy The Penrose argument about computable/countable goes roughly like this: A Turing machine can perform any function that any more complex computer (a Super-Nano-Multi-Cray, say) can do. In effect, we define a number as calculatable if there exists some Turing machine that can churn out any *specified* finite number of digits of its decimal expansion, in a finite time, and then stop. It is provable (but to spare you a little, I won't go into detail) that there exist only a countable number of Turing machines (i,e, you can give every one a serial number). Thus, at this point, which is really a lot harder than I've let on, we've got computable numbers are countable. The number of points on a line are not countable. This is most prettily proved by the diagonal slash, a reductio ad absurdum argument. Say one *could count the points on a line (say from 0 to 1). In that case, you could write them down in order: Point number 1, decimal expansion: 0.445195495... and so on... Point number 2, decimal expansion: 0.724678748... and so on... Point number 3, decimal expansion: 0.256566745... and so on... Point number 4, decimal expansion: 0.154557676... and so on... Point number 5, decimal expansion: 0.786847688... and so on... Point number 6, decimal expansion: 0.959689689... and so on... Point number 7, decimal expansion: 0.747467476... and so on... Point number 8, decimal expansion: 0.990898997... and so on... Point number 9, decimal expansion: 0.265656565... and so on... ... and so on, to countable infinity. Along comes the irritating mathematician (me) and says Hey, you've missed one out! Where's the one that goes 0.537650506. I've given the first digit as one more than the first digit of point 1, the second digit one more than the second digit of point 2, and so on (wrapping 9's back to 0's). Oh dear! you say, and disappear in a puff of logic. /language head=normal -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] apostrophes
Robert Newson wrote: She is nicer than me and you. is wrong, it should be: She is nicer than you and I. or She is nicer than I and you. 'Fraid not. Replace nicer with heavier and it becomes obvious that in the above you almost certainly should have said or not and, and the verb is then is. I'm trying quite hard to think what it might mean, should one person be nicer than a pair of other people? P.S. I've just found out that I've probably got Asperger's, which is nice, because: a) I can say the first comment above. b) I can use the Oxford comma (even though I went to the other one), and can get away with it. b) I can have the last word. c) I can stop putting the toilet seat down. d) I can have two B's (which I happen to prefer with the apostrophe (on subject! even if not on list), even though current usage dictates(sic) otherwise) and not get so worried about worrying about it (or nested parentheses, or dissimilar capitalisation, or these multiple or's, which might have worked as ORs, but would've been really uncomfortable as ors, in the same way that the B's couldn't have been bs, but could have been b's or Bs (or bees?)) anymore (where, by the time you got to that anymore, I willing to bet that that word threw you, as you'd entirely lost the thread of the sentence by then) (and I used that that that without qualms) (and now I'm getting silly) (now?). (Try saying all that without taking a breath). PPS. Tony still hasn't told me whether he'd like to have fewer or less computable numbers than points in a (mathematical) line. PEPS. Infinity. I considered introducing infinity in Minerva, but I wouldn't have been happy with just the one. -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] apostrophes
John Taylor wrote: I know everyone on here would deplore political correctness. The last few days have seen an avalanche of grammar corrections. Correcting other peoples faults is a very satisfying occupation. And the most beautiful words in the English language are I told you so. And... should we put the missing apostrophe before or after the s in peoples? -- Lau http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm
Re: [ql-users] apostrophes
John Taylor wrote: Lau There is no missing apostrophe. The people's, yes, but in this case peoples is plural. John. On 31 May 2006, at 13:01, Laurence Reeves wrote: John Taylor wrote: I know everyone on here would deplore political correctness. The last few days have seen an avalanche of grammar corrections. Correcting other peoples faults is a very satisfying occupation. And the most beautiful words in the English language are I told you so. And... should we put the missing apostrophe before or after the s in peoples Other than exceptions (where would english be without exceptions?), such as its, yours, etc, possessive forms have an apostrophe. The problem with peoples is that the people might be the simple plural of person (persons is so yucky), when the apostrophe will go before the s - giving the most common way to form the possessive: stick apostrophe ess at the end. Alternatively, people might be the singular noun for an ethnic group, or some such (e.g. The ancient peoples of the southern chunk of America were the Aztecs, Incans, Mayans, Toltecs, Olmecs, Moches, Mixtecs, Nazcas...)). In this case, peoples would be pluralising the groups, when, to form the possessive, the apostrophe would come at the end. I suspect you intended people's -- A la TF, I deplore the loss of meaning specificity that a missed apostrophe causes Punctuation rules! Eats shoots and leaves. (Probably, has a diet of both parts of a plant). Eats shoots, and leaves. (Consumes some young bean plants in a Chinky(bleugh!), say, then exits). Eats, shoots and leaves. (Has a meal, fires a gun and departs). Eats, shoots, and leaves. (Ditto, but often with a little less ambiguity) (Ambiguity? A gun? How so?). Can I go sit quietly in the corner now? -- Lau (pedantic - and proud of it) http://www.bergbland.info callto://LauReeves (see http:www.skype.com) Get a domain from http://oneandone.co.uk/xml/init?k_id=5165217 and I'll get the commission! ___ QL-Users Mailing List http://www.q-v-d.demon.co.uk/smsqe.htm