Agreed. If I say it takes three minutes to soft-boil an egg but ten minutes (say) to hard-boil one, you could reply that I've left out the time to go and buy the egg and then to eat it afterwards. But as you know it's usually implicit in the discussion that these things have been done. Otherwise it would be very hard to talk about such things. So include loading and saving time if you wish, but make it clear that you are doing so otherwise people will get confused. Perhaps the common computer science usage of 'an O(log n) algorithm' is wrong, I don't know. But it is the way people discuss these things and we have to follow the same definitions. Conventionally, you don't count time to load in the data or save out the result unless you specifically say this.
You can optimize for 686 but keep 386 compatibility. Use -march=i386 -mcpu=i686, IIRC. Then it's reasonably well optimized for newer CPUs (at least as far as instruction order, etc., if not using newly-added opcodes) while on a 386 it's not that much slower than it would be anyway. I think Red Hat does this. Similarly you can optimize for 686 keeping 586 compat., and so on.
No no, in the expression O(n) the 'n' refers to the physical size of the input (in bits, or characters, or whatever), not to its numerical value. So the data will always take O(n) time to copy. Transfers from the hard disk to main memory will be O(n). If you think about binary numbers, you'll see that a physical size of n means the number can be up to 2^n or so, so you might think an algorithm is O(log2 n) when it is really O(n) because of mistakenly counting the magnitude of the number instead of the size of its representation. (Look up 'pseudo-polynomial algorithms' for another example of this.)
The point is that not every algorithm requires the data to be fully copied in and out again. Suppose you have a program that loads some data, then does lots and lots of binary searches on it, then writes it out again. The loading and saving will be O(n) but each binary search is O(log n). Suppose that the number of such searches is proportional to the size of the input. Then the reading and writing takes O(n) as before and the searches altogether take O(n log n). The n log n factor dominates. The total execution time allowing for input and output is O(n log n).
Suppose instead that you had used linear search rather than binary search. Then each search takes O(n) time and total searching time is O(n^2). The total execution time is O(n^2).
So switching from linear search to binary search gives a real improvement in asymptotic complexity - even when input and output are taken into account. But we couldn't work that out without the knowledge that one algorithm, by itself with no I/O, takes O(log n) time and the other takes O(n) time. It is a meaningful thing to say.
You are right that you have to account for reading and writing time, but don't assume that every algorithm must read in all its data sequentially, operate on it and then output the result sequentially. If you're running many algorithms or the same one more than once then this reading and writing cost is spread between all of them.
Yes I concede that if you assume that the data must be sent one character at a time, and fully loaded into memory before the algorithm can return its result, then no algorithm can do better than O(n). Those aren't usually the assumptions you make when discussing these things however.
Both in the real world and in the ivory towers of computer science, it's acceptable to talk about algorithms which take O(log n) time or even less. The binary search I mentioned is the obvious example. As a programmer, you would do poorly to implement linear search instead of binary search simply on the grounds that no algorithm can do better than linear time.
On the point about the sender taking O(n) time to send the data to you, try running something like 'seq 0 1000000000 | head -1' and compare the time taken to run that command piped to tail -1 instead. Is this a 'true algorithmic discussion'? I don't know.
For end-users, there could be ready-made policies for the most popular applications. But by doing that you might be vulnerable to (spurious or otherwise) legal threats from the authors of those applications.
User-mode Linux is probably overkill; if you can restrict the system calls an application makes to the kernel then you have already controlled its access to the outside world. Although possibly a virtual machine approach would be simpler and so easier to secure.
As I said, a 'Wine policy' would be leaky, but kernel-level control of system calls (perhaps with a Wine layer on top to return nice error values to the application) should be watertight. Apart from covert channels (like signalling messages in Morse code by varying the system load), but it's not usually worth worrying about those.
Well with the new RandR extension to XFree86 you can rotate your display by a right angle. So just turn your existing 4:3 monitor on its side. Maybe some LCDs already have stands which support this.
I'm surprised disks aren't sold with both interfaces, SCSI and IDE (perhaps using a small external dongle to make the plugs fit). It sounds like it would be cheaper to have a single production line for both.
No, the interface makes no difference to the seek time. What you mean is that fast, high-end disks are typically sold with a SCSI interface, while slower models get IDE.
In the future couldn't there be two SATA connectors on a single device? Not running in lockstep like a parallel interface, but two separate connectors with data being sent along both. That sounds like an easy way to increase bandwidth without the syncronization problems of having parallel wires at the hardware level. But I don't know if the SATA standard supports this.
I think that although the PS/2 keyboard connector is a different size to the AT's, it is exactly the same interface (you can buy simple adaptors). OTOH, the AT and XT keyboards have the same plug but incompatible interfaces (which is annoying to those of us who have some of the lovely old XT keyboards but no machine to use them with). They are both some kind of serial port though. I wonder if it would be possible to hook up the keyboard to some kind of analogue sampler and decode the keypress messages in software.
Can you ever have an alg. that runs in less time than it takes to read in the entire input?
It depends on your model of computation... if you take something like an ordinary computer, and have the input already in memory, then binary search runs in O(log n) time where n is the number of elements. In fact it is still O(log n) if the data are stored on disk or some other random-access device.
Even if you take a computing device that must read its input one character at a time, and doesn't have a random-access memory, then there are still some algorithms that take less time than reading the whole input. Returning the first element of a list, for example.
Hmm. If you're O(f), then you take time bounded by f(x) for sufficiently large input of size x. Theta(f) means you take at least f(x) time. And Omega(f) means you are both O(f) and Theta(f).
(But notationally we write things like O(n^2) instead of O(lambda n . n^2).
So... maybe you want to say 'I'm a Theta(n) person', meaning I require *at least* time proportional to the input, 'in an O(log n) world', ie one that gives you *at most* log n amount of time. Or whatever:-).
There was recently some discussion on the Wine newsgroup about limiting emulated applications' access to the system. This could be handy for dealing with semi-malware or just programs that don't fully like the emulated environment (and might need to be prevented from doing too many suspicious is-it-really-Windows checks). The reply was that since a Wine emulated program is running as an ordinary executable, it could call Unix system calls anyway, so there would be little point (from a strict security point of view).
However, something like NetBSD's and OpenBSD's recently added feature to monitor system calls and define policies could potentially be very handy for running binary-only programs you don't fully trust: and of course most such programs are on the Windows platform.
I've never used a Mac but I used to use an Acorn machine (which is probably about equal on the fanatic scale, a little above trackballs, but below the Amiga). The Filer on that OS was a neat filesystem interface, one window per directory and not trying to hide the real layout of your disk underneath layers of menu structure and 'shortcuts'. It helped that applications were selfcontained directories that could be moved and copied at will - so organizing your collection of applications is just moving and copying files, upgrading to a larger hard disk is just selecting the contents of the root directory and dragging them across. Mac OS X also has the applications-as-directories feature I think, since it came from NeXT.
Anyway the point of this rambling post is to say that ROX-Filer is supposed to be quite cool.
Encrypting messages could hide who the recipient is, in principl. Someone could makea messaging protocol that encrypts all traffic and maybe has 'hints' about where to deliver each message but not a definite recipient; the message would be sent to dozens of people but only the intended recipient would be able to decrypt it.
In practice this is not true of course. Anyone can see who you are sending messages to and from. But that was the case anyway. Unless you believe that mail servers or network links will never be compromised, you just have to live with it.
Although you could backwards-compatibly obscure the details of who sends messages to who by having lots of encrypted junk messages sent to random people at random intervals. Perhaps 999 junk messages for every real message (and still email would use hardly any bandwidth compared to the Web). Only the person who decrypts the message can see that it is junk and discard it.
Rereading my own message I have a sudden urge to register a userid 'Slashdot Groupthink'. But I'll let someone else do that. It sounds like a girl's name to me.
If every Ethernet card chose a MAC address completely at random, what is any given user's chance of a collision? Considering that the MAC address is only used on that particular Ethernet.
If two interfaces do choose the same MAC address, and by some freak accident happen to be on the same Ethernet, doesn't it just affect frames sent to those two interfaces? Everyone else can communicate as normal.
(In practice the new address may not be random, there may be certain digits you have to leave alone, I don't know the details.)
Quite. The problem isn't that the government is trying to read cleartext network traffic, it's the 'guilty unless proven innocent' mandatory key disclosure that's the real problem. A pity that the press concentrates on the first issue (probably because it is easier to understand). 'Stop MI5 snooping on e-mails' read one headline a while ago. They should have mentioned that every citizen already has the ability to stop messages being read by MI5 or anyone else (unless they break into your house or the receiver's).
What's the big deal? Slashdot groupthink has been saying (correctly) for years now that standard network protocols like SMTP and HTTP are very easy to sniff, and if you want privacy you should use encryption. There are people (govt or otherwise) sniffing network traffic right now, all that the British minister has done is bring the issue into the open.
You should assume that whatever you send over your network link is publicly readable (if not always modifyable) and encrypt accordingly.
So how do I tell if my PSU is about to die horribly? The air coming out of it is a bit warmer than when I had the P200 board, but adding up the power consumption of the parts in the machine it seems that 235W is comfortably enough. Are there any danger signs to watch out for?
(And if PSUs take out other components when they go, does this mean that even low-end boxes from Dell and Wal-Mart will have decent PSUs, to cut down on warranty costs - or is it cheaper to fit crappy power supplies and just replace more things when they blow?)
I upgraded a machine from a P200 to a 1.73GHz Palomino by replacing the motherboard, but kept the 235W 'Sunshine' power supply. No problems so far.
As I see it, if a power supply is crap, there's no great loss when it eventually dies. Just keep using it until it does, and replace it if and when you need to - not on the basis of FUD and some vague belief that a higher wattage must be better even when you're not drawing that much power. If the air blowing out the PSU is warm, so what? Any modern motherboard will cut out when the CPU gets too hot anyway; as long as your hard disk keeps reasonably cool you should just let the system run.
A large chunk of classical music manuscripts are out of copyright. That means that if you can find someone to perform it, you can create free music. How are musicians paid? Recordings of concerts, where the costs are already met by selling tickets, might be one way. The quality won't be as high as a specially-made recording but it might be good enough. Whether the performers would agree depends on how much money they would get from enforcing copyright on the recording and trying to sell it commercially (not much I suspect).
Re:Keeping .su as an area?
on
See Ya .su
·
· Score: 1
Damn right, every sequence of one or more characters should be a TLD. Why not?
Re:Keeping .su as an area?
on
See Ya .su
·
· Score: 5, Insightful
The whole system of TLDs is meaningless when an organization can get.com, a company can register.org and.net no longer has any connection with ISPs. Once you add country-specific domains it gets even more futile (aol.co.uk or uk.aol.com or aol-uk.net, or aoluk.cx, or...).
So why not. Why not add geographical area domains as another supposed convention which nobody takes any notice of. It'll bring in more revenue for the registrars, and perhaps help relieve the artificial scarcity of the existing TLDs. In fact, any two-letter combination should be a legal TLD.
(FWIW there is the.int domain for organizations like the UN, EU, etc. But AFAIK this is not open to the public.)
Slashdot Mirror
Agreed. If I say it takes three minutes to soft-boil an egg but ten minutes (say) to hard-boil one, you could reply that I've left out the time to go and buy the egg and then to eat it afterwards. But as you know it's usually implicit in the discussion that these things have been done. Otherwise it would be very hard to talk about such things. So include loading and saving time if you wish, but make it clear that you are doing so otherwise people will get confused. Perhaps the common computer science usage of 'an O(log n) algorithm' is wrong, I don't know. But it is the way people discuss these things and we have to follow the same definitions. Conventionally, you don't count time to load in the data or save out the result unless you specifically say this.
Even intelligent beings make mistakes. So the extinction of the dinosaurs is not a reason to say that natural selection (or God) lacks intelligence.
But anyway, if n.s. were intelligent, what would its goals be?
You can optimize for 686 but keep 386 compatibility. Use -march=i386 -mcpu=i686, IIRC. Then it's reasonably well optimized for newer CPUs (at least as far as instruction order, etc., if not using newly-added opcodes) while on a 386 it's not that much slower than it would be anyway. I think Red Hat does this. Similarly you can optimize for 686 keeping 586 compat., and so on.
No no, in the expression O(n) the 'n' refers to the physical size of the input (in bits, or characters, or whatever), not to its numerical value. So the data will always take O(n) time to copy. Transfers from the hard disk to main memory will be O(n). If you think about binary numbers, you'll see that a physical size of n means the number can be up to 2^n or so, so you might think an algorithm is O(log2 n) when it is really O(n) because of mistakenly counting the magnitude of the number instead of the size of its representation. (Look up 'pseudo-polynomial algorithms' for another example of this.)
The point is that not every algorithm requires the data to be fully copied in and out again. Suppose you have a program that loads some data, then does lots and lots of binary searches on it, then writes it out again. The loading and saving will be O(n) but each binary search is O(log n). Suppose that the number of such searches is proportional to the size of the input. Then the reading and writing takes O(n) as before and the searches altogether take O(n log n). The n log n factor dominates. The total execution time allowing for input and output is O(n log n).
Suppose instead that you had used linear search rather than binary search. Then each search takes O(n) time and total searching time is O(n^2). The total execution time is O(n^2).
So switching from linear search to binary search gives a real improvement in asymptotic complexity - even when input and output are taken into account. But we couldn't work that out without the knowledge that one algorithm, by itself with no I/O, takes O(log n) time and the other takes O(n) time. It is a meaningful thing to say.
You are right that you have to account for reading and writing time, but don't assume that every algorithm must read in all its data sequentially, operate on it and then output the result sequentially. If you're running many algorithms or the same one more than once then this reading and writing cost is spread between all of them.
Yes I concede that if you assume that the data must be sent one character at a time, and fully loaded into memory before the algorithm can return its result, then no algorithm can do better than O(n). Those aren't usually the assumptions you make when discussing these things however.
Both in the real world and in the ivory towers of computer science, it's acceptable to talk about algorithms which take O(log n) time or even less. The binary search I mentioned is the obvious example. As a programmer, you would do poorly to implement linear search instead of binary search simply on the grounds that no algorithm can do better than linear time.
On the point about the sender taking O(n) time to send the data to you, try running something like 'seq 0 1000000000 | head -1' and compare the time taken to run that command piped to tail -1 instead. Is this a 'true algorithmic discussion'? I don't know.
For end-users, there could be ready-made policies for the most popular applications. But by doing that you might be vulnerable to (spurious or otherwise) legal threats from the authors of those applications.
User-mode Linux is probably overkill; if you can restrict the system calls an application makes to the kernel then you have already controlled its access to the outside world. Although possibly a virtual machine approach would be simpler and so easier to secure.
As I said, a 'Wine policy' would be leaky, but kernel-level control of system calls (perhaps with a Wine layer on top to return nice error values to the application) should be watertight. Apart from covert channels (like signalling messages in Morse code by varying the system load), but it's not usually worth worrying about those.
Well with the new RandR extension to XFree86 you can rotate your display by a right angle. So just turn your existing 4:3 monitor on its side. Maybe some LCDs already have stands which support this.
I'm surprised disks aren't sold with both interfaces, SCSI and IDE (perhaps using a small external dongle to make the plugs fit). It sounds like it would be cheaper to have a single production line for both.
No, the interface makes no difference to the seek time. What you mean is that fast, high-end disks are typically sold with a SCSI interface, while slower models get IDE.
In the future couldn't there be two SATA connectors on a single device? Not running in lockstep like a parallel interface, but two separate connectors with data being sent along both. That sounds like an easy way to increase bandwidth without the syncronization problems of having parallel wires at the hardware level. But I don't know if the SATA standard supports this.
I think that although the PS/2 keyboard connector is a different size to the AT's, it is exactly the same interface (you can buy simple adaptors). OTOH, the AT and XT keyboards have the same plug but incompatible interfaces (which is annoying to those of us who have some of the lovely old XT keyboards but no machine to use them with). They are both some kind of serial port though. I wonder if it would be possible to hook up the keyboard to some kind of analogue sampler and decode the keypress messages in software.
It depends on your model of computation... if you take something like an ordinary computer, and have the input already in memory, then binary search runs in O(log n) time where n is the number of elements. In fact it is still O(log n) if the data are stored on disk or some other random-access device.
Even if you take a computing device that must read its input one character at a time, and doesn't have a random-access memory, then there are still some algorithms that take less time than reading the whole input. Returning the first element of a list, for example.
Hmm. If you're O(f), then you take time bounded by f(x) for sufficiently large input of size x. Theta(f) means you take at least f(x) time. And Omega(f) means you are both O(f) and Theta(f).
:-).
(But notationally we write things like O(n^2) instead of O(lambda n . n^2).
So... maybe you want to say 'I'm a Theta(n) person', meaning I require *at least* time proportional to the input, 'in an O(log n) world', ie one that gives you *at most* log n amount of time. Or whatever
There was recently some discussion on the Wine newsgroup about limiting emulated applications' access to the system. This could be handy for dealing with semi-malware or just programs that don't fully like the emulated environment (and might need to be prevented from doing too many suspicious is-it-really-Windows checks). The reply was that since a Wine emulated program is running as an ordinary executable, it could call Unix system calls anyway, so there would be little point (from a strict security point of view).
However, something like NetBSD's and OpenBSD's recently added feature to monitor system calls and define policies could potentially be very handy for running binary-only programs you don't fully trust: and of course most such programs are on the Windows platform.
I've never used a Mac but I used to use an Acorn machine (which is probably about equal on the fanatic scale, a little above trackballs, but below the Amiga). The Filer on that OS was a neat filesystem interface, one window per directory and not trying to hide the real layout of your disk underneath layers of menu structure and 'shortcuts'. It helped that applications were selfcontained directories that could be moved and copied at will - so organizing your collection of applications is just moving and copying files, upgrading to a larger hard disk is just selecting the contents of the root directory and dragging them across. Mac OS X also has the applications-as-directories feature I think, since it came from NeXT.
Anyway the point of this rambling post is to say that ROX-Filer is supposed to be quite cool.
Encrypting messages could hide who the recipient is, in principl. Someone could makea messaging protocol that encrypts all traffic and maybe has 'hints' about where to deliver each message but not a definite recipient; the message would be sent to dozens of people but only the intended recipient would be able to decrypt it.
In practice this is not true of course. Anyone can see who you are sending messages to and from. But that was the case anyway. Unless you believe that mail servers or network links will never be compromised, you just have to live with it.
Although you could backwards-compatibly obscure the details of who sends messages to who by having lots of encrypted junk messages sent to random people at random intervals. Perhaps 999 junk messages for every real message (and still email would use hardly any bandwidth compared to the Web). Only the person who decrypts the message can see that it is junk and discard it.
Rereading my own message I have a sudden urge to register a userid 'Slashdot Groupthink'. But I'll let someone else do that. It sounds like a girl's name to me.
If every Ethernet card chose a MAC address completely at random, what is any given user's chance of a collision? Considering that the MAC address is only used on that particular Ethernet.
If two interfaces do choose the same MAC address, and by some freak accident happen to be on the same Ethernet, doesn't it just affect frames sent to those two interfaces? Everyone else can communicate as normal.
(In practice the new address may not be random, there may be certain digits you have to leave alone, I don't know the details.)
Quite. The problem isn't that the government is trying to read cleartext network traffic, it's the 'guilty unless proven innocent' mandatory key disclosure that's the real problem. A pity that the press concentrates on the first issue (probably because it is easier to understand). 'Stop MI5 snooping on e-mails' read one headline a while ago. They should have mentioned that every citizen already has the ability to stop messages being read by MI5 or anyone else (unless they break into your house or the receiver's).
What's the big deal? Slashdot groupthink has been saying (correctly) for years now that standard network protocols like SMTP and HTTP are very easy to sniff, and if you want privacy you should use encryption. There are people (govt or otherwise) sniffing network traffic right now, all that the British minister has done is bring the issue into the open.
You should assume that whatever you send over your network link is publicly readable (if not always modifyable) and encrypt accordingly.
So how do I tell if my PSU is about to die horribly? The air coming out of it is a bit warmer than when I had the P200 board, but adding up the power consumption of the parts in the machine it seems that 235W is comfortably enough. Are there any danger signs to watch out for?
(And if PSUs take out other components when they go, does this mean that even low-end boxes from Dell and Wal-Mart will have decent PSUs, to cut down on warranty costs - or is it cheaper to fit crappy power supplies and just replace more things when they blow?)
I upgraded a machine from a P200 to a 1.73GHz Palomino by replacing the motherboard, but kept the 235W 'Sunshine' power supply. No problems so far.
As I see it, if a power supply is crap, there's no great loss when it eventually dies. Just keep using it until it does, and replace it if and when you need to - not on the basis of FUD and some vague belief that a higher wattage must be better even when you're not drawing that much power. If the air blowing out the PSU is warm, so what? Any modern motherboard will cut out when the CPU gets too hot anyway; as long as your hard disk keeps reasonably cool you should just let the system run.
For servers it's a different matter of course.
A large chunk of classical music manuscripts are out of copyright. That means that if you can find someone to perform it, you can create free music. How are musicians paid? Recordings of concerts, where the costs are already met by selling tickets, might be one way. The quality won't be as high as a specially-made recording but it might be good enough. Whether the performers would agree depends on how much money they would get from enforcing copyright on the recording and trying to sell it commercially (not much I suspect).
Damn right, every sequence of one or more characters should be a TLD. Why not?
The whole system of TLDs is meaningless when an organization can get .com, a company can register .org and .net no longer has any connection with ISPs. Once you add country-specific domains it gets even more futile (aol.co.uk or uk.aol.com or aol-uk.net, or aoluk.cx, or...).
.int domain for organizations like the UN, EU, etc. But AFAIK this is not open to the public.)
So why not. Why not add geographical area domains as another supposed convention which nobody takes any notice of. It'll bring in more revenue for the registrars, and perhaps help relieve the artificial scarcity of the existing TLDs. In fact, any two-letter combination should be a legal TLD.
(FWIW there is the