Funnily enough that list was just the/small/ set of algorithms that I come in contact with almost every day (I'm a softie & mathematician). I live in my own small world. I was hoping to see lots of other lists from people who work and think in other fields. I'm sure there are a vast number of Chemists, Physicists, and Engineers, for example, who could open my eyes when it comes to algoritms. (Applied maths was never my strong point)
Ditto with more high-tech Comp-Sci algorithms.
Thanks for posting those, it's a shame you're sitting there at Score 0, as I nearly missed your reply. I shall look them up (and snarf the papers for fun future bus-journey reads).
" Step 1: Generate a rather lengthy list of non repeating, as random as possible numbers. "
BZZZT!
Have you learnt nothing from the Germans and Enigma? If you specify that the numbers mustn't repeat then you've reduced the entropy - you've made the next number more predictable.
If you want to be random, be random. "AAAA" is just as random as "OGVI" (typed by 4 throws of a rubber ball off the monitor onto the keyboard).
However, the one time pad is simply a method of transporting a secure channel through time...
In order to have a one time pad, and be perfectly, provably, secure, you must at some point earlier in time (maybe face to face in a secret bunker, where there are no bugs or cameras or tempest devices etc.) have had a secure channel over which to transmit and receive the pad.
The pad lets you transport that secrecy to another point in time. However, you must have had the secure channel in the first place. Are you sure that bunker is as secret as you think it is?
So yes, it's mathematically proven, but it's often very hard to set up in practice, because the preconditions are strict.
A one-type pad could be considered encryption key too though. The difference is that the theoretical kolmogorov complexity of a OTP is at least its own length.
If this nonsense can have it's 'pad generation algorithm' transmitted in b bits, then its kolmogorov complexity is at most b bits.
And if the algorithm is transmitted using a secure channel then the 'pad' is no more secure than that initial channel.
It's like the other old con - you can't use the tail end of a one-time pad to send the next whole one-time pad, no matter what they tell you.
So yes, you're right, the thing's just oozing bogons[*], and is fuxored from the start.
THL [* The elementary particle of bogosity]
Re:Lempel-Ziv?? [Re:Off the top of my head]
on
Deep Algorithms?
·
· Score: 1
The Lempel-Ziv family is a large one. Clunky - dunno what you're refering to here. LZ77 was poop in my book. That might count as clunky in your book.
Arbitrary - Oh god yes. Several parameters to chose from, and then evolution such the the parameters would adapt themselves to the problem-size in question.
Wasteful, inefficient - really? That's probably bad parametrisation, and a cheap and nasty entropy compressor as the back end. Throw it away, bolt on a decent entropy compressor. If you use the right kind of LZ variant, then you wont be more than 5-10% off the more high-tech modern ones.
Maybe LZP is such a variant - I don't know of it, or not by that name - what's the particular twist that LZP has?
Pretty please - URL will do.
However, like you - I just love the BWT technique. Here's a great way to compress data - shuffle the tokens around! My jaw dropped when I first read their paper. Hmmm, I had some potential improvements to their transform, I must try them out some time. (They've probably been done already I'm sure).
People do code mimicked stacks though. I do, if I need to (though I'm more of a merge or heap man myself). Register windowing, and branch prediction have made recusion less of a pain too.
So I certainly shouldn't say that there's no overhead, but the overhead is _really small_ compared with the rest of the job that needs to be done. O(n ln(n)) kicks in really quickly for sorts. I'll heap 20 things if there's a chance it might baloon to 30, say.
Actaully I was wrong about the 2.84, it's 3*ln(7)/ln(8) = 2.80 (7 from 8 not 8 from 9!). Strassen's IIRC.
Indeed theres a ~2.3 theoretical method (Winograd), but the scaling constant is huge, and for most purposes the algorithm is of no use for anything short of unimaginable.
Having said that, they probably said that about some bignum algorithms, and look at what GIMPS are playing with currently.
THL.
Re:Are sorting algorithms "deep"?
on
Deep Algorithms?
·
· Score: 3, Interesting
There's a clever derivative called "Shell short", which might be what you're refering to. It sends coarse combs across the data at first Then it sends finer ones, and finally the last comb is the same as the 'exchange consecutive elements only' step in quicksort.
However, whilst it appears similar, it's actually very different because it uses an iterative refinement, first coarse, then medium, then fine. The number of phases is normally much closer to about n^0.4 in typical implementations, rather than n in BS.
To say it's like bubble-sort is to say quick-sort is like radix-sort. In some ways it's true, but it misses a lot of the point.
(One pass of an in-place binary radix sort is just like one pass of a quick-sort - notta lotta people know that! You lose the order-preserving nature, but you gain in-place. Basically you hard-code the pivots to be the odd multiples of decreasing powers of 2. b10000..., then b01000... and b11000... etc.)
Where I'm from the noun form of leaving is an exact obverse of arrival. /please pick up an id card on arrival and hand it to a steward on leaving./ Sure, it has forms where a swap doesn't make sense.
I also think I was trying to mimic the word-lengths at the time (love/hate has it, email addy has it). (It was a long time back.)
Recursion adds _bugger all_ overhead. What kind of machine are you using - is it based on punched cards? Recursion is no more expensive than a loop overhead. How many loops does bubble-sort have to set up?
"and then do bubble sort on those. "
I hope not. I mean, you've got selection, insertion, in-place merge, and hard coded minimal exchange sorts to chose from; there's no need to bubble. Ever!
" There are also algorithms that do matrix multiplication in O(n^2.blah) time. The naive method is cubic. How come no one uses these fancy methods? Because they are a pain to implement and require n to be so large before they actually start performing better than the naive implementation. "
Yeah but the 2.blah you're thinking about is 3*ln(8)/ln(9) = 2.84. Which is damn close to 3 compared with how vastly different O(n^(1+o(1))) is from O(n^2) in the sorting examples.
g) Cryptographic algorithms - Hashes, Private Key Fiestel Networks, Public Key 'bignum' techniques. I'll throw in CRCs here too as they're close to hashes.
h) Bignum algorithms - Karatsuba, Barrett, Montgomery, Oooh, I've had FFTs already, can I have them again?
It's effectively a set of rules for substitutions. That's about as broad brush as I can make it, in order to try to get it to appear similar to - Church's lambda calculus - Post's strings - LISP There is no real 'machine' that's being virtualised. It's wholy abstract.
Note - don't believe everything he says on that page.
For example: [[[ In order to obtain such narrow directivity from a traditional loudspeaker system, one would need a loudspeaker array fifty meters across!
A loudspeaker is like a light bulb, but the Audio Spotlight is like a laser. ]]]
Not strictly true. Line up drivers in a vertical array. Look at the speakers of a PA in an auditorium, they're probably 5 driver units high. They create a lobe that extends to about 10 degrees. OK, it's far short of the 3 degrees he's talking about, but still, that's a common or garden PA system. (It works by correlation on the axis, and decorrelation off the axis). i.e. Sound _can_ be reasonably focussed with common equipment.
"All prey send out the same infra-red light, different to the predators, and the audience will see that the prey robots have no instinct to run from each other but are happy to graze side-by-side under the light sources. "
If there was real evolution, one of the prey could learn that it could become dominant by preying off other prey. They'd be trusted, and would have a massive advantage.
I think what they're demonstrating is clever detection and manipulation, but not in any way intelligence (AI) or evolution.
"What's neat is that Borland uses the same compiler for both their Pascal and C++ IDEs, so there is not a lot of reworking on their end and you can use both C++ and Pascal in the same project."
Am I the only one who had trouble understanding that?
C is C, use gcc to compile C.
C++ is C++, use g++ to compile C++.
C++ is not C. C is not C++.
There exists a non-empty intersection of C and C++. That intersection can be compiled by either gcc or g++.
You're forgetting the gay.com story. (or whatever the site was)
The server used PHP to answer every
your-mate's-name-here.is.gay.com
request with a faux news page revealing the fact that
Your Mate's Name Here was in fact gay.
For some bizarre and stupid reason the site was pulled because a senator (kennedy?!?) put his own name in the URL box of his browser, and didn't like what he saw.
i.e. If you are responsible for the 2LD (or 3LD in the case of countries with.ac/.co etc. 2LDs), then you are responsible for everything under your 2LD.
There is, if you use one of the alternative DNS roots!
However, if you use one of the roots that doesn't have.sucks them you can go through the cooperative.glue TLD which the alternative roots agreed would to use as a gateway. Funny, I'd have thought it was more of sniffs.glue rather than sucks.glue!
THL.
(yes, I know that's not how.glue works, but once I had the idea of sucks + glue I couldn't drop the idea. OK, I'll shut up now!)
They've registered almost all common non-national [TLD]sucks.[TLD] second level domain names, and therefore can hand out third level ones of whatever variety you want.
So you could create names like MSN.NETsucks.info if you like. (case of course being irrelevant).
"
And you prefer Debian? Debian (whole) takes MULTIPLE CD's.
"
Funny, I have a system running in only 150MB of hard disk, uncompressed, and with swapo space included. And what's a CD?
If a full sorceror setup is so compact, why are they making claims about it coming with all the latest apps? I surmise there must be 7CDs of apps it doesn't come with, guessing that SuSE's up to about 8CDs now.
"
Again, you prefer Debian, which is obsolete TODAY
"
They're _all_ obsolete today though. It was tongue in cheek!
"Now for the conspiracy theorists: He wasn't ACTUALLY using 40-bit encryption[...]"
And the article says:
"Even so, it took the equivalent of a set of supercomputers running for five days, 24 hours a day, to find the key."
Pulling figures out of my arse:
Say a supercomputer is equal to 50 1GHz PCs.
A "set" is 5.
CPU cycles in 5 days = 1G * 250 * 86400 =
21.6 * 10^15.
Search space = 2^40 = 10^12
=> 43200 cycles per test.
Hard to decide, it's a bit long though, so doubtful even at face value. If "supercomputers" are in fact 2000 node beowolf clusters, then the estimates change somewhat, and make the 40-bit claim untenable.
However, why would they use actual 'computers' to do the job when custom hardware can work a thousand times quicker? 56-bit DES is crackable in 10 minutes, for example (according to a summary by Bob Silverman, of RSA Labs, that I read the other day). If there's custom hardware, then it's certainly looking like 64-bits to take that time - either that or _extreme_ incompetance.
" it will include the very latest Linux applications "
If you don't put rose tinted specs on that translates to
1) It's bloated
2) It'll be obsolete tomorrow.
However, it will almost certainly be someone's cup of tea. Hell, I tried 5 distributions before I found the right one for my tastes. It can only be a good thing if a thousand people install it, work out what they like, what they don't like, and the _give feedback_.
Slashdot Mirror
Funnily enough that list was just the /small/ set of algorithms that I come in contact with almost every day (I'm a softie & mathematician). I live in my own small world.
I was hoping to see lots of other lists from people who work and think in other fields. I'm sure there are a vast number of Chemists, Physicists, and Engineers, for example, who could open my eyes when it comes to algoritms. (Applied maths was never my strong point)
Ditto with more high-tech Comp-Sci algorithms.
Thanks for posting those, it's a shame you're sitting there at Score 0, as I nearly missed your reply. I shall look them up (and snarf the papers for fun future bus-journey reads).
THL.
"
Step 1: Generate a rather lengthy list of non repeating, as random as possible numbers.
"
BZZZT!
Have you learnt nothing from the Germans and Enigma? If you specify that the numbers mustn't repeat then you've reduced the entropy - you've made the next number more predictable.
If you want to be random, be random. "AAAA" is just as random as "OGVI" (typed by 4 throws of a rubber ball off the monitor onto the keyboard).
THL.
However, the one time pad is simply a method of transporting a secure channel through time...
In order to have a one time pad, and be perfectly, provably, secure, you must at some point earlier in time (maybe face to face in a secret bunker, where there are no bugs or cameras or tempest devices etc.) have had a secure channel over which to transmit and receive the pad.
The pad lets you transport that secrecy to another point in time. However, you must have had the secure channel in the first place. Are you sure that bunker is as secret as you think it is?
So yes, it's mathematically proven, but it's often very hard to set up in practice, because the preconditions are strict.
THL.
Kinda sorta.
A one-type pad could be considered encryption key too though. The difference is that the theoretical kolmogorov complexity of a OTP is at least its own length.
If this nonsense can have it's 'pad generation algorithm' transmitted in b bits, then its kolmogorov complexity is at most b bits.
And if the algorithm is transmitted using a secure channel then the 'pad' is no more secure than that initial channel.
It's like the other old con - you can't use the tail end of a one-time pad to send the next whole one-time pad, no matter what they tell you.
So yes, you're right, the thing's just oozing bogons[*], and is fuxored from the start.
THL
[* The elementary particle of bogosity]
The Lempel-Ziv family is a large one.
Clunky - dunno what you're refering to here. LZ77 was poop in my book. That might count as clunky in your book.
Arbitrary - Oh god yes. Several parameters to chose from, and then evolution such the the parameters would adapt themselves to the problem-size in question.
Wasteful, inefficient - really? That's probably bad parametrisation, and a cheap and nasty entropy compressor as the back end. Throw it away, bolt on a decent entropy compressor. If you use the right kind of LZ variant, then you wont be more than 5-10% off the more high-tech modern ones.
Maybe LZP is such a variant - I don't know of it, or not by that name - what's the particular twist that LZP has?
Pretty please - URL will do.
However, like you - I just love the BWT technique. Here's a great way to compress data - shuffle the tokens around! My jaw dropped when I first read their paper. Hmmm, I had some potential improvements to their transform, I must try them out some time. (They've probably been done already I'm sure).
THL
People do code mimicked stacks though. I do, if I need to (though I'm more of a merge or heap man myself). Register windowing, and branch prediction have made recusion less of a pain too.
So I certainly shouldn't say that there's no overhead, but the overhead is _really small_ compared with the rest of the job that needs to be done. O(n ln(n)) kicks in really quickly for sorts. I'll heap 20 things if there's a chance it might baloon to 30, say.
Actaully I was wrong about the 2.84, it's 3*ln(7)/ln(8) = 2.80 (7 from 8 not 8 from 9!).
Strassen's IIRC.
Indeed theres a ~2.3 theoretical method (Winograd), but the scaling constant is huge, and for most purposes the algorithm is of no use for anything short of unimaginable.
Having said that, they probably said that about some bignum algorithms, and look at what GIMPS are playing with currently.
THL.
There's a clever derivative called "Shell short", which might be what you're refering to.
It sends coarse combs across the data at first
Then it sends finer ones, and finally the last comb is the same as the 'exchange consecutive elements only' step in quicksort.
However, whilst it appears similar, it's actually very different because it uses an iterative refinement, first coarse, then medium, then fine. The number of phases is normally much closer to about n^0.4 in typical implementations, rather than n in BS.
To say it's like bubble-sort is to say quick-sort is like radix-sort. In some ways it's true, but it misses a lot of the point.
(One pass of an in-place binary radix sort is just like one pass of a quick-sort - notta lotta people know that! You lose the order-preserving nature, but you gain in-place. Basically you hard-code the pivots to be the odd multiples of decreasing powers of 2. b10000..., then b01000... and b11000... etc.)
THL.
It's in Knuth.
Where I'm from the noun form of leaving is an exact obverse of arrival.
/please pick up an id card on arrival and hand it to a steward on leaving./
Sure, it has forms where a swap doesn't make sense.
I also think I was trying to mimic the word-lengths at the time (love/hate has it, email addy has it). (It was a long time back.)
I'm amazed people get the reference still.
Well, here come some nice -1 Offtopics...
Unless I mention the THL parody algorithm?
Phil
"Quick Sort is recursive"
Recursion adds _bugger all_ overhead.
What kind of machine are you using - is it based on punched cards? Recursion is no more expensive than a loop overhead. How many loops does bubble-sort have to set up?
"and then do bubble sort on those. "
I hope not. I mean, you've got selection, insertion, in-place merge, and hard coded minimal exchange sorts to chose from; there's no need to bubble. Ever!
"
There are also algorithms that do matrix multiplication in O(n^2.blah) time. The naive method is cubic. How come no one uses these fancy methods? Because they are a pain to implement and require n to be so large before they actually start performing better than the naive implementation.
"
Yeah but the 2.blah you're thinking about is 3*ln(8)/ln(9) = 2.84. Which is damn close to 3 compared with how vastly different O(n^(1+o(1))) is from O(n^2) in the sorting examples.
THL.
Gotta agree with you, but not on its own.
I can't narrow it down to about 50, personally. Here're the broad-brush "highlights":
a) All of quicksort, mergesort, heapsort and radixsort.
b) FFT, DFT, their relatives, whilst I'm divide and conquering. Convolutions and shite too.
c) Graph algorithms including Kruskal's, Dijkstras. Coloring algorithms (useful for compilers).
d) Parsing algoriths, while I've got compilers in mind
e) String matching algoritms ditto
f) Compression algorithms - Huffman, Arithmetic, LZ*, BWT.
g) Cryptographic algorithms - Hashes, Private Key Fiestel Networks, Public Key 'bignum' techniques. I'll throw in CRCs here too as they're close to hashes.
h) Bignum algorithms - Karatsuba, Barrett, Montgomery, Oooh, I've had FFTs already, can I have them again?
i) Pure Maths - Euclid, XGCD. Addition Chains (e.g. Pippinger). Eratosthenes, Bernstien-Atkin likewise.
j) Trial division, Fermat's Method, Brent/Pollard Rho, Pollard/Williams P+/-1, Lenstra's ECM, Quadratic Sieve, (S/G)NFS.
k) Applied Maths - Newton-Raphson, Runge-Kutta, Tchebyshev interpolation.
Too many to count...
THL
They had to lay off 85% of the testers due to them being under 18.
Or is that another story?
THL
(erm, sorry?)
*DIVIDE*, *DIVIDE*
(it's a Dilbert reference...)
THL
It's effectively a set of rules for substitutions. That's about as broad brush as I can make it, in order to try to get it to appear similar to
- Church's lambda calculus
- Post's strings
- LISP
There is no real 'machine' that's being virtualised. It's wholy abstract.
Phil
Note - don't believe everything he says on that page.
For example:
[[[
In order to obtain such narrow directivity from a traditional loudspeaker system, one would need a loudspeaker array fifty meters across!
A loudspeaker is like a light bulb, but the Audio Spotlight is like a laser.
]]]
Not strictly true. Line up drivers in a vertical array. Look at the speakers of a PA in an auditorium, they're probably 5 driver units high. They create a lobe that extends to about 10 degrees. OK, it's far short of the 3 degrees he's talking about, but still, that's a common or garden PA system. (It works by correlation on the axis, and decorrelation off the axis). i.e. Sound _can_ be reasonably focussed with common equipment.
So "lightbulb" isn't a fair comparison.
THL.
Do you take lions and gazelles and stick them in an arena and claim you're witnessing evolution.
Same answer.
THL.
They've hard-coded too many rules already.
one simple example from the first linked doc:
"All prey send out the same infra-red light, different to the predators, and the audience will see that the prey robots have no instinct to run from each other but are happy to graze side-by-side under the light sources. "
If there was real evolution, one of the prey could learn that it could become dominant by preying off other prey. They'd be trusted, and would have a massive advantage.
I think what they're demonstrating is clever detection and manipulation, but not in any way intelligence (AI) or evolution.
THL.
"What's neat is that Borland uses the same compiler for both their Pascal and C++ IDEs, so there is not a lot of reworking on their end and you can use both C++ and Pascal in the same project."
Am I the only one who had trouble understanding that?
THL.
C is C, use gcc to compile C.
C++ is C++, use g++ to compile C++.
C++ is not C. C is not C++.
There exists a non-empty intersection of C and C++. That intersection can be compiled by either gcc or g++.
Geddit?
THL.
Oooh huggy huggies - you're a dear, I can never thank you enough!
xxx
THL
You're forgetting the gay.com story. (or whatever the site was)
.ac/.co etc. 2LDs), then you are responsible for everything under your 2LD.
The server used PHP to answer every
your-mate's-name-here.is.gay.com
request with a faux news page revealing the fact that
Your Mate's Name Here was in fact gay.
For some bizarre and stupid reason the site was pulled because a senator (kennedy?!?) put his own name in the URL box of his browser, and didn't like what he saw.
i.e. If you are responsible for the 2LD (or 3LD in the case of countries with
THL.
There is, if you use one of the alternative DNS roots!
.sucks them you can go through the cooperative .glue TLD which the alternative roots agreed would to use as a gateway. Funny, I'd have thought it was more of sniffs.glue rather than sucks.glue!
.glue works, but once I had the idea of sucks + glue I couldn't drop the idea. OK, I'll shut up now!)
However, if you use one of the roots that doesn't have
THL.
(yes, I know that's not how
http://freespeechcenter.org/portfolio/com.html
It is a _third level domain_ that you get.
They've registered almost all common non-national [TLD]sucks.[TLD] second level domain names, and therefore can hand out third level ones of whatever variety you want.
So you could create names like MSN.NETsucks.info if you like. (case of course being irrelevant).
Hope that's clear now.
THL.
"
And you prefer Debian? Debian (whole) takes MULTIPLE CD's.
"
Funny, I have a system running in only 150MB of hard disk, uncompressed, and with swapo space included. And what's a CD?
If a full sorceror setup is so compact, why are they making claims about it coming with all the latest apps? I surmise there must be 7CDs of apps it doesn't come with, guessing that SuSE's up to about 8CDs now.
"
Again, you prefer Debian, which is obsolete TODAY
"
They're _all_ obsolete today though. It was tongue in cheek!
THL
"Now for the conspiracy theorists: He wasn't ACTUALLY using 40-bit encryption[...]"
And the article says:
"Even so, it took the equivalent of a set of supercomputers running for five days, 24 hours a day, to find the key."
Pulling figures out of my arse:
Say a supercomputer is equal to 50 1GHz PCs.
A "set" is 5.
CPU cycles in 5 days = 1G * 250 * 86400 =
21.6 * 10^15.
Search space = 2^40 = 10^12
=> 43200 cycles per test.
Hard to decide, it's a bit long though, so doubtful even at face value. If "supercomputers" are in fact 2000 node beowolf clusters, then the estimates change somewhat, and make the 40-bit claim untenable.
However, why would they use actual 'computers' to do the job when custom hardware can work a thousand times quicker? 56-bit DES is crackable in 10 minutes, for example (according to a summary by Bob Silverman, of RSA Labs, that I read the other day). If there's custom hardware, then it's certainly looking like 64-bits to take that time - either that or _extreme_ incompetance.
THL.
" it will include the very latest Linux applications "
If you don't put rose tinted specs on that translates to
1) It's bloated
2) It'll be obsolete tomorrow.
However, it will almost certainly be someone's cup of tea. Hell, I tried 5 distributions before I found the right one for my tastes. It can only be a good thing if a thousand people install it, work out what they like, what they don't like, and the _give feedback_.
THL.
(Debian, of course)