Computing desk
< October 11	<< Sep \| October \| Nov >>	October 13 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 12

Cryptographic hash in less than O(n)

Do any known cryptographic hash functions run in less than linear time? Neon Merlin 01:14, 12 October 2008 (UTC)[reply]

Bad ones can run in far less than O(n) time. Consider the worse one of all: Just use the first X bits as the hash. That is O(1). But, you can use whatever integer you want for X and get arbitrary length hashes! I do see that the list of popular hash functions on cryptographic hash function doesn't have runtime costs. Checking the articles, I don't even see anything in there. Looks like we need some research. -- kainaw ™ 02:31, 12 October 2008 (UTC)[reply]

Even worse and faster hash function: always return 42. Not so "cryptographic" though. --71.106.183.17 (talk) 04:14, 12 October 2008 (UTC)[reply]

I doubt that any good cryptographic hash functions run in less than linear time. You might be able to fudge "good" for a particular application, and get away with less, but not in general. Consider the property "second preimage resistant" as described in the article Cryptographic hash function: It should be very hard, given one input x, to generate a second input y, such that hash(x)=hash(y). To get that, you need every byte of the input to have an effect on the output. But doing anything to every byte of input is necessarily going to take at least O(n) time.

It's also a minor point from a practical perspective. Most of the times that you're interested in the cryptographic hash of some data, you're also doing something else with the data -- storing it on disk, or transmitting it across a network -- that takes O(n) time, and a fairly substantial amount of time at that. So any gains you'd make from having a sub-O(n) hash function would be swamped to insignificance by the cost of your other operations.

The only application that comes to mind where it's not moot would be something like Open Source Tripwire (checking to see if files have been modified, in part by checking their hashes) since you're potentially hashing the file a lot more often than you read it, or write it, or transfer it. But I think that's one application where you couldn't "fudge" things -- if you don't use each and every byte in your hash, an attacker could conceivably slip something into the bytes you ignore.

On a parting note: I think (but I'm no expert) that currently used cryptographic hashes are all O(n) in time and O(1) in space (excluding any space used to hold the input). -- Why Not A Duck 04:37, 12 October 2008 (UTC)[reply]

Think about it. For a hash to be at all cryptographic, it needs to exhibit the avalanche effect, meaning that if one bit flips, about 50% of the bits in the has should flip. Even a truly terrible hash needs to give at least a different value if you flip one bit. So say, you're hashing two 100 gigabyte files that are identical except for the last bit. You want those two files to hash to different values (otherwise, what's the point of a hash?). But to do that, the hash needs to read all of the file, it has to check all of the bits. This makes it O(n).

The general rule is that if you have a problem where in order to solve it, an algorithm has to check every part item that's part of the problem, it can't possibly be any less than O(n). Think of sorting algorithms for instance. It is easy to see why those have to be at least O(n), because in order to place all items in a list in the correct order, it has to look at every item at least once. Otherwise, it will have no idea where to put it! It's the same with hashing.

You could, if you wanted to, instead just hash the first X bits of a file, then it would be O(1) (assuming X is a constant, otherwise it would be O(X)). But then you're not hashing the file, you're hashing the first X bits of the file. And there's no point in doing that. 90.235.19.68 (talk) 22:28, 16 October 2008 (UTC)[reply]

Google 2001 and phrases

A google 2001 search for "Sarah Palin" with quotes gives no hits, but doing a search for Sarah Palin Alaska (without quotes) reveals that pages featuring the phrase "Sarah Palin" existed back then. Does anything like this happen for any other search terms in google 2001? Andjam (talk) 04:09, 12 October 2008 (UTC)[reply]

It looks like the quoted phrase feature didn't work back then. --Sean 21:56, 12 October 2008 (UTC)[reply]

Doing a google 2001 search for "Steven Bradbury" with and without quotes gives different results, so I don't think that's it. Andjam (talk) 08:04, 13 October 2008 (UTC)[reply]

I remember being asked how to search for phrases, by a coworker at a firm that dissolved at the end of 2001, so the capability must indeed have existed then; though I think it was not then true that hand-rail, say, would find both "handrail" and "hand rail". —Tamfang (talk) 04:00, 14 October 2008 (UTC)[reply]

Firefox: Predict my URL please, but not a whole bunch of nonsense

Hi all,

I set Firefox to auto-fill my url bar as I type some time ago (using about:config, I don't exactly remember where), so that typing in 'news.g' would fill in 'news.google.com' and I could just hit enter. After the latest update, though, it's started filling in much more than I typed, and instead filling in addresses it's been to, e.g. news.google.com/news/url?sa=t&ct=:ePkh8BM9E2IF2mHAArFFW[.....], forcing me to finish typing and hit delete, or using my mouse to delete the rest.

How can I tell Firefox to only auto-fill addresses that I've actually typed, instead of addresses that I've been to?

Thanks! — Sam 07:58, 12 October 2008 (UTC)

Found it at last! It's another about:config change. Set browser.urlbar.matchOnlyTyped to True. Incidentally, there's a couple of lists of about:config settings - at http://kb.mozillazine.org/About:config_entries and http://kb.mozillazine.org/Category:Preferences . AJHW (talk) 10:46, 13 October 2008 (UTC)[reply]

Great! Thanks for tracking that down. — Sam 03:05, 14 October 2008 (UTC) —Preceding unsigned comment added by 146.115.120.108 (talk)

ASP.NET: <%# %>

Can someone remind me what that is called? In between it would be an expression. I would search for it, but those characters aren't coming up in google or msdn. Thanks Louis Waweru Talk 15:40, 12 October 2008 (UTC)[reply]

is that like a preprocessor directive? 68.146.178.33 (talk) 18:51, 12 October 2008 (UTC)[reply]

I'm pretty sure that you are right...it's strange but I can't find anything about them to confirm this. Someone else described them the way you do, and give this list of them #if #else #elif #endif #define #undef #warning #error #line #region #endregion. That one in this section title is the only one I've been using, it's always been with binding data...I'm trying to figure out how many there are and how to use them to see what I can and can't do with them. But they're not turning up anything for me. Louis Waweru Talk 22:31, 12 October 2008 (UTC)[reply]

gnome 2.24

Is there a .deb package of GNOME 2.24 available for downlaod for either Debian or Ubuntu (latest stable versions of both)? Thanks in advance :) —Preceding unsigned comment added by 71.138.187.117 (talk) 16:06, 12 October 2008 (UTC)[reply]

Linux: inline text editing

What is "inline text editing" in Linux? Thanks. Smaug 16:45, 12 October 2008 (UTC)[reply]

Currently, "inline text editing" almost exclusively pertains to editing web page content through a web browser directly on the web page's server. For example, when you click "edit" on Wikipedia, you are using an inline text editor. Linux doesn't really have anything to do with it. The web server could be Linux, Windows, Mac, Commodore... -- kainaw ™ 16:57, 12 October 2008 (UTC)[reply]

There is something, when you are editing a text document in Linux. There is graphical, there is stuff like nano, and there is "inline text editing". What is inline text editing? Or does it refer to graphical or nano/w/e? Smaug 17:09, 12 October 2008 (UTC)[reply]

Tell us where you saw this term? SteveBaker (talk) 18:58, 12 October 2008 (UTC)[reply]

Maybe ed, the "line-oriented editor"? - IMSoP (talk) 19:26, 12 October 2008 (UTC)[reply]

Re SteveBaker: "1. What are two advantages of graphical and inline text editing?" Smaug 21:45, 12 October 2008 (UTC)[reply]

Oh-oh. Now your confessing to having asked us a homework question...which we're not allowed to answer. But if this is indeed homework - then the answer must be somewhere in the books you're working from. Personally (and I've been using Linux since almost the first version - and I've used other UNIX versions since the mid-1970's)...I have never heard this term. It's possible they are talking about "line editors" versus "visual editors" - you can see a 'line' editor in Linux by opening up a text console and running 'ex filename' versus a 'visual' editor by running 'vi filename'. (These are actually different modes of the same underlying program). SteveBaker (talk) 00:27, 13 October 2008 (UTC)[reply]

On yet another hand, if vi (which I use heavily!) were invented today it's unlikely that anyone would describe it as "visual", because it doesn't follow the usual WIMP conventions. —Tamfang (talk) 03:52, 14 October 2008 (UTC)[reply]

Versatile Flash Animation Software

Howdy folks, I've been looking a whole lot lately into animation and the like, and I was wondering what exactly the "Standard" software is for Flash animation. I've been looking at Flash MX, but I've heard there's some stuff out there that's better purely for animation, however I still want a decent amount of versatility. Thanks!

Kenjibeast (talk) 17:10, 12 October 2008 (UTC)[reply]

There are different types of web animation, one of them is Flash. Flash animation is any animation made using Flash. Flash MX is an old (though still very good) version of Flash. It has since been followed by Flash 8 and Flash CS3.

I have not used any animation software other than Flash MX and Flash 8, but I find both to be great for animation and great for other stuff. I even use it to make static diagrams, or in place of powerpoint presentations. Smaug 17:46, 12 October 2008 (UTC)[reply]

Vista track number help

I have a folder with more than 200 songs and I'm giving them track numbers. However, when I try to give a song a track number over 99, I get an error. Can Vista not handle track numbers over 99 or something? How do I fix this; use WMP?--Oldman55 (talk) 17:59, 12 October 2008 (UTC)[reply]

You're going to have to edit the id3 tag in a different program. You can do it manually in WMP, but some programs will let you automate something like that...I can recommend Tag&Rename.Louis Waweru Talk 18:54, 12 October 2008 (UTC)[reply]

I don't know of any albums with more than 99 tracks! Your problem is almost certainly that you're trying to put a bunch of songs that are not part of the same album into a single album. You need to put them into the albums they came from originally. SteveBaker (talk) 18:55, 12 October 2008 (UTC)[reply]

Well they're all ripped from a game that doesn't have an OST, and I want them all in one folder and with track numbers following each other so they stay in one spot on my ipod.--Oldman55 (talk) 18:57, 12 October 2008 (UTC)[reply]

Weird browser glitch?

Hi. This has happened four times already, including three times today. The first time happened a while back, when I was uploading an image of a Northern Cardinal to Commons from my computer. I think I had one Wikipedia window and two Commons windows open in my browser. I use IE. As I closed either one or two windows, I don't remember, new windows started randomly popping up, each an exact duplicate of a window I closed. If I pressed "Esc", the new windows would just come up like 'there is nothing to display'. Today, when I was opening new windows from my watchlist, once while editing persimmon, another time while editing The Weather Network, and another time with Cyclone Nargis, I closed the window I was editing to come back to my watchlist, and the exact same thing happened again! As I closed the window, more windows would pop up of the window I closed. The only way to stop this is by closing all the windows, in which I have to log back in again if I closed my watchlist window. Since my computer is a bit slow, it took a while for the windows to load, so today by the time I closed all the windows only about six or seven managed to stay up at the same time. If left unattended, perhaps it could open indefinitely. I remember with the TWN and Nargis articles, the page hadn't completely finished loading before I closed it. Is this a general browser glitch, or could it be some sort or virus? I'm not asking for professional advice. The problem is, this has never happened without me closing a window and also not without closing a wiki website, or at least I saved something, closed it before finished loading, and this happens. Any ideas? Thanks. ~A H 1^(TCU) 19:43, 12 October 2008 (UTC)[reply]

Wikipedia has melted down. See my question below. Powerzilla (talk) 20:43, 12 October 2008 (UTC)[reply]

Keyboard Problem

Hello, my 'e' key is at the point where it's barely responding. I have to press down on it fairly hard for the letter to appear on screen and it's significantly lowering my typing speed. Is there any quick fixes for this? Thank you —Preceding unsigned comment added by 69.236.176.39 (talk) 20:34, 12 October 2008 (UTC)[reply]

Buy a new keyboard? They only cost about £10-15. Algebraist 20:44, 12 October 2008 (UTC)[reply]

It's a laptop... —Preceding unsigned comment added by 69.236.176.39 (talk) 20:52, 12 October 2008 (UTC)[reply]

Other option, get a vacuum cleaner and completely vacuum the contents of your keyboard. You would be surprised how much crap collects between the keys and the pad or membrane underneath! :) Thor Malmjursson (talk) 20:54, 12 October 2008 (UTC)[reply]

Most laptops let you unscrew the faceplate of the keyboard, giving you better access to clean the inside of the keyboard with blowers, wipes or whatever. If you need online intructions, there's a good site for MAcs, ifixit.com, and I'll bet there are guides out there for some PC laptops. — Sam 21:09, 12 October 2008 (UTC) —Preceding unsigned comment added by 69.38.252.83 (talk)

You can buy some "switch cleaner" spray - (you'd get it in any decent computer store...or RadioShack) gently lever off the keycap with a flat screwdriver and spray a good squirt down into the center of the hole - put the keycap back on and tap the key repeatedly. If you've lead a good and virtuous life - your key will gradually come back to life. If it gets a bit better, do it again...but if not...give up and buy a USB keyboard - it should work just fine - even with a laptop. (Although it's going to be kinda inconvenient if you actually use your laptop for mobile computing). SteveBaker (talk) 00:20, 13 October 2008 (UTC)[reply]

When this has happened to me, it's been because something solid is stuck underneath the key (on my laptop). I usually just pop the key off and pull whatever it is out with tweezers... but be warned, you can damage the key doing this. I recently had to replace my keyboard, so I had a dummy to test on. Should you decide to do this (at your risk) you usually just lift on the side or bottom of the key and the cap will just pop off... depending on the manufacturer. On my new gateway, you lift from the bottom, on a slightly older gateway, it's the side. Anyway, make sure you don't lose the little squishy plastic piece underneath. To put it back on, just line up half of the key (generally under some hook things), and then push down on the other half to put it back on. (Again, at your own risk! I've broken keys doing this occasionally). DaRkAgE7 _[Talk] 04:29, 13 October 2008 (UTC)[reply]

Is Wikipedia Having a MELT-DOWN?!

Is Wikipedia having a melt-down? It is repeatedly malfunctioning. Getting really weird shit on it, disconnects from wikipedia. I guess it finally blew up. Powerzilla (talk) 20:42, 12 October 2008 (UTC)[reply]

I've had no problems. Can we have a bit more info? What operating system are you on? What browser are you using? --Alinnisawest,^{Dalek Empress} (extermination requests here) 21:32, 12 October 2008 (UTC)[reply]

Wikipedia sometimes has a little hiccup but it's usually fixed within hours. Just be patient. Seems fine now. --98.217.8.46 (talk) 02:07, 13 October 2008 (UTC)[reply]

no, wikipedia and the whole wiki network is absolutely fine. what you have experienced is most probable some maintenance interruption.

anubhav.g october 17, 2008

Ignoring Users on YouTube

Is there a way to find out which users are ignoring you on YouTube or how to find out if a certain user is ignoring you?Serpentipes (talk) 21:35, 12 October 2008 (UTC)[reply]

You mean users who have blocked you? You can try individually by trying to subscribe to their channel. It won't let you subscribe if they blocked you. ScienceApe (talk) 00:08, 13 October 2008 (UTC)[reply]