Fast way to add null after each char
Brad
std::string unicode_string;
std::string::const_iterator it,
for(it = s.begin(); it != s.end(); ++it)
{
unicode_string.push_back(*it);
unicode_string.push_back('\0');
}
The above for loop would make unicode_string look like this:
"e null a null s null y null"
Is there a faster way to do this... in place maybe?
Thanks for any tips,
Brad
Francesco S. Carta
> std::string s = "easy";
>
> std::string unicode_string;
>
> std::string::const_iterator it,
>
> for(it = s.begin(); it != s.end(); ++it)
> {
> unicode_string.push_back(*it);
> unicode_string.push_back('\0');
> }
>
> The above for loop would make unicode_string look like this:
>
> "e null a null s null y null"
Nay, it will make it look like "e\0a\0s\0y\0"... by the way, why do you
need to do such a thing?
> Is there a faster way to do this... in place maybe?
Faster, I don't know (measure it), in place, yes: use the
std::string::insert() method.
--
FSC - http://userscripts.org/scripts/show/59948
http://fscode.altervista.org - http://sardinias.com
Alf P. Steinbach /Usenet
Depends what you want.
It /seems/ that you're assuming a little-endian architecture, and that the
intent is to treat unicode_string as UTF-16 encoded (via some low level cast),
and that you're assuming that the original character encoding is Latin-1 or a
subset.
That's an awful lot of assumptions.
Look in the standard library for mbcstowcs or something like that, in the C
library, or 'widen'-functions in the C++ library.
Under what seems to be your assumption of Latin-1 encoding of the 'char' string,
and an additional assumption of 16-bit 'wchar_t', you can however do
<code>
#include <iostream>
#include <string>
#include <limits.h>
using namespace std;
#define STATIC_ASSERT( x ) typedef char shouldBeTrue[(x)? 1 : -1]
STATIC_ASSERT( CHAR_BIT == 8 );
STATIC_ASSERT( sizeof( wchar_t ) == 2 );
int main()
{
string const s = "Hello";
wstring const u( s.begin(), s.end() );
wcout << u << L"\n";
}
</code>
But I don't recommend that; use the widening functions, C or C++.
Cheers & hth.,
- Alf
--
blog at <url: http://alfps.wordpress.com>
SG
> in place, yes: use the
> std::string::insert() method.
Or better yet, resize() to final size, assign the non-null characters
in a backwards loop and set a couple of chars to zero:
void sillify(string & io)
{
size_t len1 = io.size();
io.resize(len1*2,'\0');
for (size_t k=len1; k-->1;)
io[k*2] = io[k];
for (size_t k=1; k<len1; k+=2)
io[k] = '\0';
}
Cheers!
SG
Francesco S. Carta
> On 5 Sep., 19:05, "Francesco S. Carta" wrote:
>> in place, yes: use the
>> std::string::insert() method.
>
> Or better yet, resize() to final size, assign the non-null characters
> in a backwards loop and set a couple of chars to zero:
>
> void sillify(string& io)
> {
> size_t len1 = io.size();
> io.resize(len1*2,'\0');
> for (size_t k=len1; k-->1;)
> io[k*2] = io[k];
> for (size_t k=1; k<len1; k+=2)
> io[k] = '\0';
> }
Define "better".
void smartify(string& s) {
for(int i = 1, e = s.size()*2; i < e; i+=2) {
s.insert(i, 1, '\0');
Marc
> SG <s.gesem...@gmail.com>, on 05/09/2010 10:17:37, wrote:
> > On 5 Sep., 19:05, "Francesco S. Carta" wrote:
> >> in place, yes: use the
> >> std::string::insert() method.
>
> > Or better yet, resize() to final size, assign the non-null characters
> > in a backwards loop and set a couple of chars to zero:
>
> > void sillify(string& io)
> > {
> > size_t len1 = io.size();
> > io.resize(len1*2,'\0');
> > for (size_t k=len1; k-->1;)
> > io[k*2] = io[k];
> > for (size_t k=1; k<len1; k+=2)
> > io[k] = '\0';
> > }
>
> Define "better".
>
> void smartify(string& s) {
> for(int i = 1, e = s.size()*2; i < e; i+=2) {
> s.insert(i, 1, '\0');
> }
> }
Faster. SG's code has linear complexity and yours is quadratic.
Readability is something else...
Francesco S. Carta
Exactly. So neither is better than the other unless we associate
"better" to "more readable" or to "faster" ;-)
Francesco S. Carta
Just for the records, a better solution, in my opinion, is to build an
appropriately sized new string and copying the original chars at the
appropriate positions - a compromise between readability and speed,
somewhat:
void foo(string& s) {
string r(s.size()*2, '\0');
for(int i = 0, e = s.size(); i < e; ++i) {
r[i*2] = s[i];
}
s.swap(r);
}
ASSUMING that the OP really wants exactly this - WRT Alf P. Steinbach's
notes in the other post.
SG
> Marc wrote:
> > On 5 sep, 19:27, Francesco S. Carta wrote:
> >> Define "better".
> > Faster. [...]
> Exactly. So neither is better than the other unless we associate
> "better" to "more readable" or to "faster" ;-)
See the original post:
"...Is there a faster way to do this..."
Cheers!
SG
Juha Nieminen
> * Brad, on 05.09.2010 18:54:
>> std::string s = "easy";
>>
>> std::string unicode_string;
>>
>> std::string::const_iterator it,
>>
>> for(it = s.begin(); it != s.end(); ++it)
>> {
>> unicode_string.push_back(*it);
>> unicode_string.push_back('\0');
>> }
>>
>> The above for loop would make unicode_string look like this:
>>
>> "e null a null s null y null"
>>
>> Is there a faster way to do this... in place maybe?
>
> Depends what you want.
>
> It /seems/ that you're assuming a little-endian architecture
No, he isn't. He is making the string UTF16LE, not assuming that the
architecture is little-endian.
Alf P. Steinbach /Usenet
Perhaps, but it would be (I think even more) unusual.
Cheers,
Francesco S. Carta
Of course, I was just playing at nitpicking after your overzealous snip
- see my further post ;-)
Geoff
Are you really trying to insert null after each character or are you looking for
a way to convert std::string into std::wstring?
Geoff
Forgot to attach the code.
#include <string>
int main()
{
std::string s = "easy";
std::wstring unicode_string;
unicode_string.assign(s.begin(),s.end());
return 0;
}
tni
>>
>> Faster. SG's code has linear complexity and yours is quadratic.
>> Readability is something else...
>
> Exactly. So neither is better than the other unless we associate
> "better" to "more readable" or to "faster" ;-)
Unnecessary quadratic code is a bug (unless you have guarantees on the
input size).
Francesco S. Carta
That was a deliberately slow implementation - see all the other posts.
tni
> tni <t...@example.invalid>, on 06/09/2010 10:37:08, wrote:
>
>> On 2010-09-05 20:04, Francesco S. Carta wrote:
>>>>
>>>> Faster. SG's code has linear complexity and yours is quadratic.
>>>> Readability is something else...
>>>
>>> Exactly. So neither is better than the other unless we associate
>>> "better" to "more readable" or to "faster" ;-)
>>
>> Unnecessary quadratic code is a bug (unless you have guarantees on the
>> input size).
>
> That was a deliberately slow implementation - see all the other posts.
>
My point isn't that the implementation is a bit slower, it's wrong and
should never be used. There is no question whether one of the two is better.
Feed your quadratic implementation a 10MB string and it will literally
run for hours.
Francesco S. Carta
You're right, of course, and finally somebody posted the correct,
explicit objection to the first response of mine, which was
over-zealously half-snipped by SG:
"Faster, I don't know (measure it), in place, yes: use the
std::string::insert() method."
My purpose was to push the OP to make all the tests and the reasonings.
But the OP disappeared and the group took circa ten posts to come down
to this, I won't post any bait like this anymore, just to save my time :-)
Goran Pusic
+1 for Alf. Chances are that you are just looking for
MultiByteToWideChar (or libiconv, but that's less likely).
Guys, aren't you a bit misleading with iterators and big-O and
stuff? ;-)
Goran.
Goran.
Francesco S. Carta
> Guys, aren't you a bit misleading with iterators and big-O and
> stuff? ;-)
My bad. I intentionally posted a wrong suggestion without clearly
marking it as such - I thought I was going to be castigated immediately,
but since the punishment didn't come at once, I kept it on to see what
was going to happen... now I realize that it wasn't all that fun for the
others, so I present my apologies to the group for the wasted time.
tni
> Goran Pusic <gor...@cse-semaphore.com>, on 06/09/2010 03:15:21, wrote:
>
>> Guys, aren't you a bit misleading with iterators and big-O and
>> stuff? ;-)
>
> My bad. I intentionally posted a wrong suggestion without clearly
> marking it as such - I thought I was going to be castigated immediately,
> but since the punishment didn't come at once, I kept it on to see what
> was going to happen... now I realize that it wasn't all that fun for the
> others, so I present my apologies to the group for the wasted time.
The sad thing is, I've seen quadratic stuff like that far too often in
production code. There certainly are more than enough (clueless) people
who wouldn't consider it a joke.
Francesco S. Carta
Indeed. And since it seems that most of those programmers has no idea of
what the O() notation is, simply saying that an algorithm has linear or
quadratic complexity is not enough to make the point clear.
Unfortunately it needs more words (and practical examples as the one you
posted in the other branch) and a big fat "quadratic is BAD" sign three
meters on each side, but it's worth the effort.
Brad
Busy weekend. Thanks for the replies (all of you).
Why do such a thing?
Over simplified, but here is why: A Microsoft NT hash is a string
(encoded as I described (utf-16le)) with MD4 then applied. In short,
that produces an NT hash. So if I wanted to create an NT hash for the
word "easy" and I had a std::string the process would look something
like this:
std::string NTHash = MD4(utf-16le_encode(std::string));
My initial post confused the issue by using the term "unicode" in a
variable name (although this is a form of unicode (utf-16le)
encoding). And no, by default wstring doesn't magically do this.
--------------------------------------
insert works fine for in place. Faster than my for loop? Does not seem
so. I'm not sure it needs to be any faster. I was just wondering.
Maybe my approach is slow. Obviously, the encoding is an additional
step to perform (plain MD4 on std::string is faster than encode
std::string then MD4... but not a whole lot). BTW, these strings would
never be 10 megs ;)
That's about it. Thanks again.
Brad
Francesco S. Carta
You're welcome.
Your initial implementation is not slow, it's pretty fine, my only
(serious) suggestion about it is to use something like the second
implementation I presented, which takes advantage of std::string::swap()
to avoid an unneeded additional copy from the working string to the
original one and optimizes the allocation by creating an
appropriately-sized string beforehand.
Completely forget the insert() method for containers such as std::vector
and std::string - because it leads to very bad performances - but
remember it for containers like std::list - where it is good.
Alf P. Steinbach /Usenet
>
> Busy weekend. Thanks for the replies (all of you).
>
> Why do such a thing?
>
> Over simplified, but here is why: A Microsoft NT hash is a string
> (encoded as I described (utf-16le)) with MD4 then applied. In short,
> that produces an NT hash. So if I wanted to create an NT hash for the
> word "easy" and I had a std::string the process would look something
> like this:
>
> std::string NTHash = MD4(utf-16le_encode(std::string));
>
> My initial post confused the issue by using the term "unicode" in a
> variable name (although this is a form of unicode (utf-16le)
> encoding). And no, by default wstring doesn't magically do this.
OK, with more information more can be said.
First, in Windows, conversion to wstring like
string s = "blah blah";
wstring u( s.begin(), s.end() )
produces exactly the byte sequence that you're laboriously creating.
You're right that no magic is involved. However, no magic is necessary.
That said, second, Windows ANSI Western is a superset, not a subset, of Latin 1,
and so this zero-insertion procedure does not in general produce UTF-16.
E.g., if s contains a '€' Euro sign you won't get proper UTF-16. If you need
proper UTF-16 you should use one of the conversion functions available in the
standard library, or alternatively in the Windows API.
Third, I've already given this advice and it gets tiresome repeating it.
Cheers & hth.,
Brad
+use...@gmail.com> wrote:
> OK, with more information more can be said.
>
> First, in Windows, conversion to wstring like
>
> string s = "blah blah";
> wstring u( s.begin(), s.end() )
>
> produces exactly the byte sequence that you're laboriously creating.
I'm not programming on Windows or using with Windows at all. Just
because I have to deal with NT hashes, doesn't mean I'm using Windows
to deal with them :)
Thanks,
Brad
Paavo Helde
news:51d49713-de07-4a98...@f25g2000yqc.googlegroups.com:
> On Sep 7, 2:52 pm, "Alf P. Steinbach /Usenet" <alf.p.steinbach
> +use...@gmail.com> wrote:
>
>> OK, with more information more can be said.
>>
>> First, in Windows, conversion to wstring like
>>
>> string s = "blah blah";
>> wstring u( s.begin(), s.end() )
>>
>> produces exactly the byte sequence that you're laboriously creating.
>
>
> I'm not programming on Windows or using with Windows at all. Just
> because I have to deal with NT hashes, doesn't mean I'm using Windows
> to deal with them :)
In that case, you have to take more care to reproduce Windows artefacts,
wchar_t and wstring are not portable enough for this purpose. In this
case you might need the UTF16-LE encoding. I would suggest:
std::string s = "blah blah"; // ASCII only!
std::vector<uint16_t> u(s.begin(), s.end());
plus byte-swapping on the application boundary if you are running on a
big-endian machine.
If you need to translate anything else than ASCII there is the iconv
library.
hth
Paavo
Stuart Golodetz
You're oversimplifying :-)
It's not that quadratic algorithms per se are necessarily bad -- for
some problems (matrix multiplication, for example), a quadratic solution
may in fact be optimal. The point is that you want to avoid implementing
solutions that are inadequate for the problem at hand (whatever their
actual complexity).
Regards,
Stu
Francesco S. Carta
Indeed, I was unconsciously implying the problem (and the context) at
hand, where anything more than linear complexity would be sub-optimal,
thank you for the refinement.
Of course, an algorithm solving the TSP with quadratic complexity would
be very very good - no idea if something like that is even conceivable,
I'm not a mathematician, and for that very reason, I must take your word
about quadratic being optimal in matrix multiplication !-)
Joshua Maurice
I assume you meant to say either that
1- O(n^2) is an optimal bound on the number of cell additions, for
doing a matrix add of two two-dimensional matrices, both of size (n,
n). In this case, you are correct.
2- O(n^3) is an optimal bound on the number of cell multiplications,
for doing a matrix multiply of two two-dimensional matrices, both of
size (n, n). Even assuming this interpretation, you are incorrect. You
can do better than O(n^3), though it's not the easiest thing to
program:
http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication
Paavo Helde
news:i66d4s$s2s$1...@speranza.aioe.org:
>> you posted in the other branch) and a big fat "quadratic is BAD" sign
>> three meters on each side, but it's worth the effort.
>
> You're oversimplifying :-)
>
> It's not that quadratic algorithms per se are necessarily bad -- for
> some problems (matrix multiplication, for example), a quadratic
> solution may in fact be optimal.
Funny that you bring up matrix multiplication, as this can be done well
and very badly, both solutions with the same big-O complexity, but the
performance for large matrices differing by several magnitudes (because
of cache behavior, which is not considered in big-O).
> The point is that you want to avoid
> implementing solutions that are inadequate for the problem at hand
> (whatever their actual complexity).
In the light of above this is even more true!
Cheers
Paavo
Stuart Golodetz
What I meant by that was that matrix multiplication of two n x n
matrices is Omega(n^2) -- i.e. you can't do better than a solution of
quadratic complexity (since the output matrix depends on all the
elements of the two input matrices, you have to at least read all of
them, which instantly makes it quadratic). Thus a quadratic solution, if
one were possible, would be optimal. Actually, I'm not sure that there
isn't a tighter lower bound than that for matrix multiplication, in
which case a quadratic solution wouldn't actually be possible -- but I
was using the example to explain what I meant (I think I failed in that,
incidentally :-))
What I wasn't saying was anything about the Big-O upper bound for either
matrix addition or multiplication. I'm aware that you can beat O(n^3)
for matrix multiplication -- e.g. Strassen's algorithm is O(n^2.807).
I've never actually sat down and implemented it, though, because I've
never personally needed it.
Cheers!
Stu
James Kanze
[...]
> First, in Windows, conversion to wstring like
> string s = "blah blah";
> wstring u( s.begin(), s.end() )
> produces exactly the byte sequence that you're laboriously creating.
Only if you compile with the /J option. By default, char is
signed, and accented characters will result in incorrect
Unicode. (You could use boost::transform_iterator to convert
the char to unsigned char.)
This isn't a Windows issue: the standard requires the above to
work, *and* defines the semantics. (Semantics which are, in
general, useless.)
--
James Kanze
Stuart Golodetz
Indeed -- for what it's worth, I only meant to nitpick you in a friendly
way, hence the :-)
Incidentally, I think it's worth observing that the algorithm with the
optimal Big-O complexity may not necessarily always be the optimal
solution to your problem. For that matter, the algorithm with the
optimal *actual* complexity (i.e. including the constant factors) may
not necessarily always be the optimal solution to your problem -- if
it's so damn hard to implement that you could have solved the problem
with the worse algorithm by the time you implemented the better one,
then you should implement the worse one and feel no guilt about it
afterwards. YMMV.
> Of course, an algorithm solving the TSP with quadratic complexity would
> be very very good - no idea if something like that is even conceivable,
> I'm not a mathematician, and for that very reason, I must take your word
> about quadratic being optimal in matrix multiplication !-)
If you came up with a quadratic complexity algorithm for TSP (which is
NP-hard), wouldn't you have just come up with a constructive proof that
P = NP? In which case that would indeed be "very very good" :-) I think
you'd probably make yourself quite a bit of money... I guess it's
conceivably possible, but unlikely in practice. (As an article of
personal faith, I strongly suspect P != NP, but maybe one day we'll know
for sure.)
In terms of matrix multiplication being at least quadratic, consider
that you have to at least read all the elements of both input matrices.
I'm not a mathematician either, btw :-)
Cheers,
Stu
Joshua Maurice
>
> What I meant by that was that matrix multiplication of two n x n
> matrices is Omega(n^2) -- i.e. you can't do better than a solution of
> quadratic complexity (since the output matrix depends on all the
> elements of the two input matrices, you have to at least read all of
> them, which instantly makes it quadratic). Thus a quadratic solution, if
> one were possible, would be optimal. Actually, I'm not sure that there
> isn't a tighter lower bound than that for matrix multiplication, in
> which case a quadratic solution wouldn't actually be possible -- but I
> was using the example to explain what I meant (I think I failed in that,
> incidentally :-))
Sorry. I was trying to ferret out exactly what you meant in a nice
way. :)
> What I wasn't saying was anything about the Big-O upper bound for either
> matrix addition or multiplication. I'm aware that you can beat O(n^3)
> for matrix multiplication -- e.g. Strassen's algorithm is O(n^2.807).
> I've never actually sat down and implemented it, though, because I've
> never personally needed it.
Indeed. My favorite way of looking at this is choice trees. I'm
fudging the formalism a little bit now, but we know that the output
matrix depends on every cell in the input matrices, so we know that
the code has to at least read each input cell. Given the instruction
set can only read a fixed finite number of cells in an instruction
(naively only 1 or 2), then we know that O(n^2) instructions are
required to do the matrix multiplication. The bound of O(n^2) is thus
a lower bound, though we don't know if any algorithm exists which can
do it in that bound from this proof of choice trees.
Also, as mentioned in the wiki link, the best we've been able to do
(for the given instruction set) is about n ^ ((log base 2) of (7)).
Stuart Golodetz
No offence taken :-) I should have been more clear.
>> What I wasn't saying was anything about the Big-O upper bound for either
>> matrix addition or multiplication. I'm aware that you can beat O(n^3)
>> for matrix multiplication -- e.g. Strassen's algorithm is O(n^2.807).
>> I've never actually sat down and implemented it, though, because I've
>> never personally needed it.
>
> Indeed. My favorite way of looking at this is choice trees. I'm
> fudging the formalism a little bit now, but we know that the output
> matrix depends on every cell in the input matrices, so we know that
> the code has to at least read each input cell. Given the instruction
> set can only read a fixed finite number of cells in an instruction
> (naively only 1 or 2), then we know that O(n^2) instructions are
> required to do the matrix multiplication. The bound of O(n^2) is thus
> a lower bound, though we don't know if any algorithm exists which can
> do it in that bound from this proof of choice trees.
I'm not totally sure what the choice tree stuff is in this context
actually -- could you elaborate?
For what it's worth, btw, I think you mean Omega(n^2) and not O(n^2) --
since as you (correctly) state it's a lower bound:
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations
But that's nitpicking on my part (and I'm far from being an expert on
complexity analysis, so I should perhaps refrain from it!).
> Also, as mentioned in the wiki link, the best we've been able to do
> (for the given instruction set) is about n ^ ((log base 2) of (7)).
Apparently there are asymptotically better algorithms that have been
discovered, e.g.
http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
However, this one (at least) isn't used in practice, because you have to
have really large matrices to make it worthwhile, and current hardware
can't handle matrices of the size required.
Cheers,
Stu
Joshua Maurice
The best example I can think of is for proving lower bounds on sorting
algorithms. Let's take an array of N elements. For arbitrary elements,
we know that any permutation of the input is possibly the correct
output. If we model our program as being able to "choose" a subset of
the remaining possibles at every step, then we end up with our program
being modeled by a binary tree, with time going from the root to the
leaves, and each leaf representing a single possible output
permutation. The middle nodes represent subsets of size bigger than 1,
but less than the whole. Each step of the algorithm removes some of
the possible answers from the answer space until only the correct
answer remains.
It's been a while, so I'm slightly fuzzy on the exact formalism, so I
know I'm explaining it badly. I /think/ that you can say, for unknown
input, you can calculate the size of the answer space, (size X), and
for "standard instruction sets", each "step" can only take one branch
in the binary decision tree, so the minimum number of steps depends on
the height of a balanced binary tree with X leafs.
I'm not sure it exactly applied to the reasoning I attempted to use. I
think I used something analogous. I know that the algorithm must at
least read every single input cell, each read takes O(1) cycle, and
there are O(N^2) cycles, so the algorithm running time in cycles must
be at least O(N^2).
> For what it's worth, btw, I think you mean Omega(n^2) and not O(n^2) --
> since as you (correctly) state it's a lower bound:
>
> http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80....
>
> But that's nitpicking on my part (and I'm far from being an expert on
> complexity analysis, so I should perhaps refrain from it!).
I was being somewhat informal, and I'm not really quite sure myself. I
know what it means for a function to be Big O and Big Theta, but I'm
not sure of the exact standard commonly used. Let me take a stab at
something a little more formal:
For an instruction set in which you can read at most a fixed finite
number of matrix cells per "cycle", any correct matrix multiplication
implementation for two N by N matrices must have its running time
describable as a function f : input size -> number of cycles, where f
is little-o (N^2).
> > Also, as mentioned in the wiki link, the best we've been able to do
> > (for the given instruction set) is about n ^ ((log base 2) of (7)).
>
> Apparently there are asymptotically better algorithms that have been
> discovered, e.g.
>
> http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
>
> However, this one (at least) isn't used in practice, because you have to
> have really large matrices to make it worthwhile, and current hardware
> can't handle matrices of the size required.
Mmm. I was unaware. I was just going off what I read off the matrix
multiply wiki page, and we all know how reliable that is.
Stuart Golodetz
Thanks, I think I sort of see what you're getting at -- would need to
look at it in more detail to properly understand it though I think
(perhaps when it's not 1am :-)) I should add that the explanation itself
isn't the problem so much as the ability of my tired brain to understand it!
> I'm not sure it exactly applied to the reasoning I attempted to use. I
> think I used something analogous. I know that the algorithm must at
> least read every single input cell, each read takes O(1) cycle, and
> there are O(N^2) cycles, so the algorithm running time in cycles must
> be at least O(N^2).
>
>> For what it's worth, btw, I think you mean Omega(n^2) and not O(n^2) --
>> since as you (correctly) state it's a lower bound:
>>
>> http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80....
>>
>> But that's nitpicking on my part (and I'm far from being an expert on
>> complexity analysis, so I should perhaps refrain from it!).
>
> I was being somewhat informal, and I'm not really quite sure myself. I
> know what it means for a function to be Big O and Big Theta, but I'm
> not sure of the exact standard commonly used. Let me take a stab at
> something a little more formal:
>
> For an instruction set in which you can read at most a fixed finite
> number of matrix cells per "cycle", any correct matrix multiplication
> implementation for two N by N matrices must have its running time
> describable as a function f : input size -> number of cycles, where f
> is little-o (N^2).
To the best of my knowledge, little-o (as I've seen it used) is still an
upper bound -- specifically, it's a strict upper bound, whereas Big-O is
a weak one. For instance, f is O(n^2) means that f is no worse than
quadratic, whereas f is o(n^2) means that f is better than quadratic.
For lower bounds, Omega(n^2) means that f is no better than quadratic,
whereas omega(n^2) means that f is worse than quadratic. In this case,
it's clear that matrix multiplication is Omega(n^2), i.e. no better than
quadratic, but it's not clear at first glance that it's omega(n^2) --
although it may well be.
>>> Also, as mentioned in the wiki link, the best we've been able to do
>>> (for the given instruction set) is about n ^ ((log base 2) of (7)).
>> Apparently there are asymptotically better algorithms that have been
>> discovered, e.g.
>>
>> http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
>>
>> However, this one (at least) isn't used in practice, because you have to
>> have really large matrices to make it worthwhile, and current hardware
>> can't handle matrices of the size required.
>
> Mmm. I was unaware. I was just going off what I read off the matrix
> multiply wiki page, and we all know how reliable that is.
Likewise :-) Just a different wiki page to the one you were reading -- I
guess there should have been a link between the two which someone forgot
to add. Just thought I'd give you the link in case you were interested(!)
Best,
Stu