I vaguely remember that there existed some trick to count the bits == 1
in a fixnum in constant time.
(bitcount 7) => 3
(bitcount 8) => 1
(bitcount 9) => 2
(bitcount 10) => 2
something with logior, logand or similar...
can anybody point me to the trick?
--
Reini
In article <··················@judy.x-ray.local>, ······@sbox.tu-graz.ac.at wrote:
> I vaguely remember that there existed some trick to count the bits == 1
> in a fixnum in constant time.
> (bitcount 7) => 3
> (bitcount 8) => 1
> (bitcount 9) => 2
> (bitcount 10) => 2
>
> something with logior, logand or similar...
> can anybody point me to the trick?
> --
> Reini
in ANSI CL:
LOGCOUNT integer
[Function]
returns the number of �on� bits in integer. If integer is positive, then
the one bits in its binary representation are counted; if integer is
negative, then the zero bits in the two�s-complement representation are
counted.
Kent M Pitman wrote: [1999-08-01 07:23 +0000]
> ······@lavielle.com (Rainer Joswig) writes:
>
> >
> > In article <··················@judy.x-ray.local>,
> > ······@sbox.tu-graz.ac.at wrote:
> >
> > > I vaguely remember that there existed some trick to count the bits == 1
> > > in a fixnum in constant time.
>
> (Incidentally, "constant time" is a funny metric here, unless you
> expect the fixnum size not to be a constant.
(This reminds me of the old `pearl' that it is a good thing to use a named
constant for pi as this makes life easy should the value of pi change...)
More seriously, fixnum size is a run-time constant (even a compile-time
constant), but not necessarily a design-time constant or a compose-time
constant. (Where `design-time' refers to the time the program is designed
and `compose-time' to the time the program is written (composed) by the
programmer. I avoid `write-time' because this is ambiguous---could also
mean the time the results are written to the output stream(s).)
> Something that iterates
> down all the bits in a word testing each and adding them up works in
> constant time, after all. I think the word ds you might have been
> looking for are more like "nice and fast". :-)
[...]
I have no idea how implementations do LOGCOUNT and in particular if
they handle fixnums specially (LOGCOUNT, after all, has to do bignums
too, and with them a loop is inevitable). And while it is difficult to
imagine a case when the programmer would have to roll out their own
counter, rather than use Common Lisp's LOGCOUNT, I think that the
`proper' meaning of `constant time' here refers to precomputing
a table with the bit counts for all possible 8-bit bytes (or, if memory
is plenty, all possible 16-bit bytes) and computing the count by
splitting the word into such bytes and adding the values obtained
by lookup in that table. I believe this is the `closest' one could get to
counting bits in a way that does not depend on the word size. In
other words, there is no `closed expression' (not involving an
explicit or implicit loop) which yields the number of `on' bits in
a word, but with table lookup the loop can be `minimised.'
Vassil Nikolov
Permanent forwarding e-mail: ········@poboxes.com
For more: http://www.poboxes.com/vnikolov
Abaci lignei --- programmatici ferrei.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
······@lavielle.com (Rainer Joswig) writes:
>
> In article <··················@judy.x-ray.local>,
> ······@sbox.tu-graz.ac.at wrote:
>
> > I vaguely remember that there existed some trick to count the bits == 1
> > in a fixnum in constant time.
(Incidentally, "constant time" is a funny metric here, unless you
expect the fixnum size not to be a constant. Something that iterates
down all the bits in a word testing each and adding them up works in
constant time, after all. I think the word ds you might have been
looking for are more like "nice and fast". :-)
> in ANSI CL:
>
> LOGCOUNT integer
> [Function]
> returns the number of �on� bits in integer. If integer is
> positive, then the one bits in its binary representation are
> counted; if integer is negative, then the zero bits in the
> two�s-complement representation are counted.
Right. But I *think* the integer doesn't have to be stored in 2's complement;
these functions are just defined to work as if they were.
Kent M Pitman <······@world.std.com> wrote:
>> > I vaguely remember that there existed some trick to count the bits == 1
>> > in a fixnum in constant time.
>
>(Incidentally, "constant time" is a funny metric here, unless you
>expect the fixnum size not to be a constant. Something that iterates
>down all the bits in a word testing each and adding them up works in
>constant time, after all. I think the word ds you might have been
>looking for are more like "nice and fast". :-)
no, i meant the trick to count it in constant time for a known wordsize
(32-bit, but 16-bit and 64-bit versions exist as well) and twos
complement of course. the "nice and quite fast version" was much too
slow.
the looping version is too slow and the recursive version
as this in autolisp:
(defun LOGCOUNT (n)
(cond ((zerop n) 0)
((minusp n) (logcount (~ n)))
(t (+ (logcount (lsh n -4))
(nth (rem n 16) '(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)
)))))
or in scheme with vectors (from the slib):
(define (logical:ash-4 x)
(if (negative? x)
(+ -1 (quotient (+ 1 x) 16))
(quotient x 16)))
(define (logical:logcount n)
(cond ((zero? n) 0)
((negative? n) (logical:logcount (logical:lognot n)))
(else
(+ (logical:logcount (logical:ash-4 n))
(vector-ref '#(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)
(modulo n 16))))))
is logarithmic for bigint, but O(2) for 32-bit fixnums.
the constant version does some logand and shifting as in this c (better
"d") version:
from clisp for 32-bit ints
x32 = (x32 & 0x55555555UL) + ((x32 & 0xAAAAAAAAUL) >> 1);
x32 = (x32 & 0x33333333UL) + ((x32 & 0xCCCCCCCCUL) >> 2);
x16 = high16(x32)+low16(x32);
x16 = (x16 & 0x0F0FU) + ((x16 & 0xF0F0U) >> 4);
x16 = (x16 & 0x00FFU) + (x16 >> 8);
this is the trick i looked for because i uses some magic numbers not so
easy to guess. cmucl has the fast assembler versions for all CPU's but I
couldn't remember the name what to look for. LOGCOUNT was the hint.
i could only vaguely remember knuth or bentley mentioning the trick
somewhere. thanks.
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
······@xarch.tu-graz.ac.at (Reini Urban) writes:
Beware, some nit-picking ahead. No offence intended.
> Kent M Pitman <······@world.std.com> wrote:
> >> > I vaguely remember that there existed some trick to count the bits == 1
> >> > in a fixnum in constant time.
> >
> >(Incidentally, "constant time" is a funny metric here, unless you
> >expect the fixnum size not to be a constant. Something that iterates
> >down all the bits in a word testing each and adding them up works in
> >constant time, after all. I think the word ds you might have been
> >looking for are more like "nice and fast". :-)
>
> no, i meant the trick to count it in constant time for a known wordsize
> (32-bit, but 16-bit and 64-bit versions exist as well) and twos
> complement of course. the "nice and quite fast version" was much too
> slow.
But technically speaking, if you limit the size of the word, this is
always constant time. You can only speak of "non-constant" time, if
you let the wordsize vary, since then the run-time can be a function
of this variable. If you don't have variables (parameters), all your
functions are constants. And if you get really technical, and enter
O-calculus, you even have to let your variable proceed to infinity,
before you can speak about something being O(n), or similar things.[1]
> is logarithmic for bigint, but O(2) for 32-bit fixnums.
It does not make sense to speak of some piece of code being O(2).
Regs, Pierre.
Footnotes:
[1] This is a very non-technical "O in a nutshell" type of
statement, but sadly this margin is too small to contain a correct
introduction to O-calculus.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
····@acm.org (Pierre R. Mai) wrote:
>······@xarch.tu-graz.ac.at (Reini Urban) writes:
>Beware, some nit-picking ahead. No offence intended.
thanks. no problem. i tried to use a "vague BigO" which makes sense to
me, at least, because i'm a total freshman of how to express a vague
run-time of known problem sizes without Big O notation.
constant is in "Big O" notation so wrongly used here.
but speaking assembler ops or cpu cycles is also overkill.
Knuth does it, but who wants to be Knuth.
>It does not make sense to speak of some piece of code being O(2).
how do you call this commonly abbrevated then?
T(2) or two atomic time units?
my understanding (� la algorithmic and complexity textbooks) goes like
this:
O(2) which really is O(i+2*x) => O(1)
i: initialization factor
x: hidden runtime factor
strict BigO only knows some cases, i found six:
constant (=1),
logarithmic (=lgn or log2(n)),
linear (=n)
n*lgn ("almost linear" and strangely enough very common)
polynomial (=n^k) and
exponential (=k^n).
is this correct?
>> Kent M Pitman <······@world.std.com> wrote:
>> >> > I vaguely remember that there existed some trick to count the bits == 1
>> >> > in a fixnum in constant time.
>> >
>> >(Incidentally, "constant time" is a funny metric here, unless you
>> >expect the fixnum size not to be a constant. Something that iterates
>> >down all the bits in a word testing each and adding them up works in
>> >constant time, after all. I think the word ds you might have been
>> >looking for are more like "nice and fast". :-)
>>
>> no, i meant the trick to count it in constant time for a known wordsize
>> (32-bit, but 16-bit and 64-bit versions exist as well) and twos
>> complement of course. the "nice and quite fast version" was much too
>> slow.
>
>But technically speaking, if you limit the size of the word, this is
>always constant time. You can only speak of "non-constant" time, if
>you let the wordsize vary, since then the run-time can be a function
>of this variable. If you don't have variables (parameters), all your
>functions are constants. And if you get really technical, and enter
>O-calculus, you even have to let your variable proceed to infinity,
>before you can speak about something being O(n), or similar things.[1]
>
>> is logarithmic for bigint, but O(2) for 32-bit fixnums.
>
>It does not make sense to speak of some piece of code being O(2).
--
Reini
Reini Urban wrote:
[Pierre Mai:]
>> It does not make sense to speak of some piece of code being O(2).
>
> how do you call this commonly abbrevated then?
> T(2) or two atomic time units?
I don't think there is any common simple way of writing that.
If you're doing analyses that precise, it's probably best to
write it out explicitly -- "5+2N+0.01N^2 basic operations" or
whatever.
> strict BigO only knows some cases, i found six:
> constant (=1),
> logarithmic (=lgn or log2(n)),
> linear (=n)
> n*lgn ("almost linear" and strangely enough very common)
> polynomial (=n^k) and
> exponential (=k^n).
>
> is this correct?
No.
"Doing <foo> takes time O(blah)" means: there's some constant K
such that doing <foo> always takes time at most K*blah. So,
for instance, "heapsort takes time O(exp(exp(exp(N))))" is true
but rather misleading. :-)
The notation is often misused to mean "within a constant factor of"
instead of "at most a constant factor of"; so you might say "Heapsort
takes time O(N log N), whereas insertion sort takes time O(N^2),
so heapsort is better for large N". Strictly, as I say, this is
a misuse; pedants like me either say "on the order of" or write
a capital theta, which means "within a constant factor of".
The six cases you list aren't anything like exhaustive. For instance,
multiplying two n-bit integers takes time of order something like
n*log(n)*log(log(n)) if you do it by the best algorithm known;
some number-theoretical algorithms -- important in e.g. cryptography --
are believed to take time like exp(C.n^{1/3}.(log n)^{2/3}).
So the thing inside O() can be very untidy.
--
Gareth McCaughan ················@pobox.com
sig under construction
······@xarch.tu-graz.ac.at (Reini Urban) writes:
> how do you call this commonly abbrevated then?
> T(2) or two atomic time units?
The main problem with this is that you have to define whether you mean all
instructions take the same length of time, and you have to define what the
overhead of all kinds of things like function calls are. The beauty of
big-O notation is that it gets away from that level of detail and gives you
a way of comparing things which, yes, only really matters at the high end
of things and isn't very practical when you're comparing small numbers, but
for all its trouble has the property that it's reasonably free of concern
about instruction speeds, compiler smarts (other than global algorithm
optimization, which almost no one does; certainly open-coding vs
closed-coding and peephole optimization and register optimization and
probably even paging performance are largely ignored by big-O notation).
the programming language MOO has something like what you're talking about.
It is a time-sliced multi-user system and you only get a fixed quantum
of time. Two parallel times are kept: one is a wallclock time so that if
you do a long operation like "foo in bar", which is like (member foo bar),
you will get charged more wallclock time if bar is really huge and you can
blow it out this way before you run out of the other measure; but the other
measure it records is a set of units called "ticks" which are carefully
defined by the language so that they are processor-independent and so doing
x+y takes 1 tick and doing x+y+1 takes 2 ticks. But function calls cost,
etc. and you have to know the details. If the details were not laid out
and agreed on by all as the necessary gating factor for something else to
happen, I'm not sure the strategy would be meaningful. Suppose I disagreed
withyou about how to assign values in bigT notation? Would I make my own?
Who would be right? Can anyone be right? ... BigO has the property that
it's hard for it to be wrong. It may not mean what you want it to mean,
but it's somewhat "uniquely determined" insofar as what it says is meaningful
at all. The same is not true of your BigT notation, which is arbitrary
in its meaning except if you pin down the specific processor, compiler, etc.
Or so it seems to me. You're welcome to tell me I'm confused. It's been
kind of a long day, and I don't claim to be infallible.
"Pierre R. Mai" wrote:
> It does not make sense to speak of some piece of code being O(2).
I disagree, and I specilaizd in algorithms for my grad work. When
discussing practical algorithms, that could be the differerence between
an algorithm which takes 300 assembler instructions, and 600 assembler
instructions.
Heapsort nd quicksort are good examples. Mergesort is basically
n lg n ( though sqrt ( n! ) is better ) and heapsort is also order
n lg n. Actually, though, it's 2(n lg n) and many books list it
as such. Though it's unusual notation to see o(2) I think it's
still acceptable, as we all know what it means, more or less..
dave
David Hanley <···@ncgr.org> wrote:
> > It does not make sense to speak of some piece of code being O(2).
>
> I disagree, and I specialized in algorithms for my grad work.
But O(1) = O(2), since if f(n) is in O(2) then
there exist k,N such that 0 <= f(n) < 2k for all n>N
by definition, hence
there exists k',N' such that 0 <= f(n) < k' for all n>N'
by taking k'=2k and N'=N. Hence
f(n) is in O(1)
by definition. This is why it makes no sense to talk about O(2), or
indeed O(k) for any fixed k. If you're counting instructions or have
some other precise measure of algorithm cost, you don't use big-O
notation.
> as such. Though it's unusual notation to see o(2) I think it's
> still acceptable, as we all know what it means, more or less..
Little-o notation is something else entirely (an upper bound that is not
asymptotically tight). Did you really specialize in algorithms?
--
Gareth Rees
Gareth Rees wrote:
> David Hanley <···@ncgr.org> wrote:
> > > It does not make sense to speak of some piece of code being O(2).
> >
> > I disagree, and I specialized in algorithms for my grad work.
>
> But O(1) = O(2),
You should do a little work in logic. You can't refute an argument
by simply defining your answer to be correct.
> by definition. This is why it makes no sense to talk about O(2), or
> indeed O(k) for any fixed k. If you're counting instructions or have
> some other precise measure of algorithm cost, you don't use big-O
> notation.
I do, as do a lot of others. Knuth and Baase both do this in their
algorithm books.
> > as such. Though it's unusual notation to see o(2) I think it's
> > still acceptable, as we all know what it means, more or less..
>
> Little-o notation is something else entirely (an upper bound that is not
> asymptotically tight). Did you really specialize in algorithms?
Yes, but the goal was providing useful things ( algorithms , code ),
not intellectual masturbation.
dave
Gareth Rees wrote:
> If you're counting instructions or have some other precise measure of
> algorithm cost, you don't use big-O notation [as a means of comparing
> functions to within constant factors].
David Hanley wrote:
> I do, as do a lot of others. Knuth and Baase both do this in their
> algorithm books.
I'd be interested to see a reference to such a use. Knuth's
"Fundamental Algorithms" says (p. 107):
Every appearance of O(f(n)) means precisely this: There are positive
constants M and n_0 such that the number x_n represented by O(f(n))
satisfies the condition |x_n| <= M|f(n)|, for all integers n >= n_0.
which agrees with the definition I gave except for the use of absolute
magnitude in the comparison, and being a bit more careful about the
definition (so that a statement like "1^2 + 2^2 + ... + n^2 = O(n^3)"
can be made precise).
--
Gareth Rees
Gareth Rees wrote:
> Gareth Rees wrote:
> > If you're counting instructions or have some other precise measure of
> > algorithm cost, you don't use big-O notation [as a means of comparing
> > functions to within constant factors].
>
> David Hanley wrote:
> > I do, as do a lot of others. Knuth and Baase both do this in their
> > algorithm books.
>
> I'd be interested to see a reference to such a use. Knuth's
> "Fundamental Algorithms" says (p. 107):
>
> Every appearance of O(f(n)) means precisely this: There are positive
> constants M and n_0 such that the number x_n represented by O(f(n))
> satisfies the condition |x_n| <= M|f(n)|, for all integers n >= n_0.
> which agrees with the definition I gave except for the use of absolute
> magnitude in the comparison, and being a bit more careful about the
> definition (so that a statement like "1^2 + 2^2 + ... + n^2 = O(n^3)"
> can be made precise).
I disagree with your interpretation of this statement. It doen't require
that constant factors be dropped in O notation. This is a common teaching
device but it is not required. Knuth is showing a simple case; in other
parts of the book he gives polynomials with constants for algorithmic
runtimes. even if f(n)=Mf(n) in his notation, that doesn't obviate
o(3n^2 + 18N ). There is a difference between adjusting for processor
speeds and determining where algorithmic complexity crossover
points will occur. Back to the original statement, o(1) will always
beat o(2) if analysis is proper.
dave
David Hanley wrote:
[about big-O notation in Knuth]
> I disagree with your interpretation of this statement. It doen't require
> that constant factors be dropped in O notation. This is a common teaching
> device but it is not required.
It is not a "common teaching device". It is the meaning of the big-O
notation. Of course you don't have to drop the constant factors, but
the meaning of "O(2)" is exactly the same as the meaning of "O(1)".
If you choose to make a convention that when you say "O(...)" you
mean something different from what everyone else means by it, that's
up to you; but it certainly is not what Knuth means by it.
> Knuth is showing a simple case; in other
> parts of the book he gives polynomials with constants for algorithmic
> runtimes.
Inside O() ? Could you give some examples of places where Knuth
bothers with constant factors inside O() other than as an intermediate
stage in simplification? Or of places where he compares two estimates
written in O() notation and concludes that one is bigger than another
because of different constant factors?
> even if f(n)=Mf(n) in his notation, that doesn't obviate
> o(3n^2 + 18N ).
What do you mean by "obviate"? The only thing "wrong" with saying
"O(3n^2+18N)" is that you could equally well write "O(n^2+N) and
save some ink or some typing.
> There is a difference between adjusting for processor
> speeds and determining where algorithmic complexity crossover
> points will occur. Back to the original statement, o(1) will always
> beat o(2) if analysis is proper.
It's useful to have a notation that takes account of constant
factors. However, O() and o() do not, as used by any mathematician
or computer scientist known to me, do so.
I could quote passages from textbooks, but since presumably you'd
just say "Like I said, it's a common teaching device" there doesn't
seem much point. What *would* count for you as evidence that your
interpretation is incorrect?
--
Gareth McCaughan ················@pobox.com
sig under construction
On 03 Aug 1999 23:54:49 +0100, Gareth McCaughan wrote:
>David Hanley wrote:
>> even if f(n)=Mf(n) in his notation, that doesn't obviate
>> o(3n^2 + 18N ).
>What do you mean by "obviate"? The only thing "wrong" with saying
>"O(3n^2+18N)" is that you could equally well write "O(n^2+N) and
>save some ink or some typing.
If you're going to be formal about it -- which is certainly what you're
being -- that's not valid either; it's a shorthand. That should be
O(n^2), by what I recall. IANAAA (I Am Not An Algorithms Analyst :).
I think formality is wonderful. It solves a lot of problems. It seems to
me that this thread is preoccupied with using formality to create problems.
>It's useful to have a notation that takes account of constant
>factors. However, O() and o() do not, as used by any mathematician
>or computer scientist known to me, do so.
I've seen it used that way informally as well. Do you know of any correct
way of expressing the same thing?
>Gareth McCaughan ················@pobox.com
>sig under construction
--
-William "Billy" Tanksley
William Tanksley wrote:
[me:]
>> What do you mean by "obviate"? The only thing "wrong" with saying
>> "O(3n^2+18N)" is that you could equally well write "O(n^2+N) and
>> save some ink or some typing.
>
> If you're going to be formal about it -- which is certainly what you're
> being -- that's not valid either; it's a shorthand. That should be
> O(n^2), by what I recall. IANAAA (I Am Not An Algorithms Analyst :).
I was assuming that n and N were different quantities.
>> It's useful to have a notation that takes account of constant
>> factors. However, O() and o() do not, as used by any mathematician
>> or computer scientist known to me, do so.
>
> I've seen it used that way informally as well. Do you know of any correct
> way of expressing the same thing?
Not that's as brief, but that's probably just as well since you need
to be careful about your units if you try to keep track of constant
factors, and it would be naive to expect everyone to use the same
units, or even to expect any one person to use the same units all the
time, so *somewhere* along the line you have to be more verbose
than the O() notation is...
I'd say "This takes at most 18n^3+27.5n+C cycles, for some constant C"
or something, having defined the notion of "cycles" earlier. Or, if
it wasn't a matter of counting cycles, "2M log N + 3N log M function
evaluations" or "(2 log log log n)^1000 comparisons" or whatever.
--
Gareth McCaughan ················@pobox.com
sig under construction
Gareth Rees wrote:
> I'd be interested to see a reference to such a use. Knuth's
> "Fundamental Algorithms" says (p. 107):
>
> Every appearance of O(f(n)) means precisely this: There are positive
> constants M and n_0 such that the number x_n represented by O(f(n))
> satisfies the condition |x_n| <= M|f(n)|, for all integers n >= n_0.
David Hanley wrote:
> I disagree with your interpretation of this statement. It doesn't
> require that constant factors be dropped in O notation.
It doesn't *require* that constant factors be dropped, but it does make
the inclusion of constant factors meaningless. Can you point me at an
instance where Knuth writes "O(2n)" or "O(3n^2)"? I am certain that you
cannot.
Knuth *does* do precise analysis of algorithm behaviour in terms of
number of instructions executed or number of memory locations used. But
he doesn't abuse big-O notation to do it.
--
Gareth Rees
David Hanley <···@ncgr.org> writes:
> "Pierre R. Mai" wrote:
>
> > It does not make sense to speak of some piece of code being O(2).
>
> I disagree, and I specilaizd in algorithms for my grad work. When
I think we don't have to argue about the fact that given big-O
notation, it doesn't make sense to distinguish between O(2) and O(1).
That follows from the definition of big-O notation, and IMHO if you
use a given notation that has a precisely defined meaning, it should
be used correctly or not at all. Otherwise communication gets a bit
difficult, concepts blur, and misunderstandings abound...
> discussing practical algorithms, that could be the differerence between
> an algorithm which takes 300 assembler instructions, and 600 assembler
> instructions.
Or it could be the difference between 1 and 2 instructions, or indeed the
difference between 1 instruction and 2 instructions which are executed in
parallel, or the difference between one slow instruction and two fast
ones, or the difference between 1 millenium and 2 millenia, or any number
of things. If you care about instructions, then count instructions, or
count steps, or comparissons or whatever you want to count.
big-O notation is used to abstract away exactly these "details", to
talk about algorithmic complexity in the asymptotic case. I'd be
the first to agree with you, that in practice a lot of other things
influence the speed at which a given algorithm executes in a given
implementation for a given problem set. But big-O notation isn't
the language to talk about those, since it's not rich enough to
distinguish things that are practically relevant, yet theoretically
uninteresting.
> Heapsort nd quicksort are good examples. Mergesort is basically
> n lg n ( though sqrt ( n! ) is better ) and heapsort is also order
> n lg n. Actually, though, it's 2(n lg n) and many books list it
> as such. Though it's unusual notation to see o(2) I think it's
But they don't say that heapsort is O(2(n lg n)), at least if they are
worth their salt. And there are a whole lot of things you have to
take into account when estimating speed: For example it pays to
differentiate between comparisons and swaps, since in practice, the
constant factors involved in comparing two things and swapping them
can be quite different (this all gets even more complicated in the
presence of caches and SMP, ephemeral GC, etc.). All of that can't be
talked about using big-O notation.
> still acceptable, as we all know what it means, more or less..
I'd argue that we know more _less_ than more what it means.
Especially if big-O notation is used in conjunction with restrictions
on the input size. If I restrict input sizes (i.e. n), then even an
algorithm with O(n^2) can be quite a bit faster than an algorithm with
O(n), for suitably large constant factors and suitably small values of
n. And this isn't a purely theoretical point: In practice it often
pays to use an algorithm with higher algorithmic complexity for small
(and even not so small) input sizes.
So what I'd like to see is a stricter use of big-O notation, precisely
to avoid people assuming that big-O notation is a meaningful measure
of "practical speed", or that O(n lg n) is just a funny way of saying
that something takes n lg n steps to compute, or similar things.
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
····@acm.org (Pierre R. Mai) writes:
> big-O notation is used to abstract away exactly these "details", to
> talk about algorithmic complexity in the asymptotic case.
Make no mistake, big-O still needs a `unit of measurement'. Just
saying algorithm such and such is "O(log n)" does not mean much. You
also have to define what the function means that is approximated by
"O(log n)". So you might say "multiplication two general n x n
matrices requires O(n^3) multiplications if we do it the obvious way."
You still have to say what "n" is and what the things are that you are
counting. So it would be a valid thing to say that some algorithm has
O(...) storage accesses or cache misses or need O(..) cpu cycles or
something. For sorting algorithm, the big-O mostly counts
comparisons, I think, and "n" is the number of elements in the input
set.
Just so that it doesn't get lost although Gareth Rees has already
stated it, here is how big-O is actually defined:
g(n) = O(f(n)) means that there exist K and N such that
|g(n)| < |K*f(n)| for all n > N
Big-O is a tool for expressing approximations in a compact way. But
it nevertheless is precisely defined.
- Marius
On 03 Aug 1999 23:37:06 +0200, Marius Vollmer <···@zagadka.ping.de> wrote:
>Make no mistake, big-O still needs a `unit of measurement'. Just
>saying algorithm such and such is "O(log n)" does not mean much. You
I may be speaking out of my butt when I say this, but Billy has observed me
talking (occasionally) in terms of /decibels/ when referring to algorithm
performance. For me, a ham radio operator, it just comes naturally. In
this case, I was referring to dBs (specific units being seconds). The
advantage of decibels is that, through the establishment of a standard
implementation for comparison, the decibel allows most, if not all, the
qualitative comparisons permitted by the O(x) notation, and also has the
benefit of being able to assign specific units thereto. This could be dBKB
(decimals of kilobytes with respect to ...), dBs (decibels of seconds with
respect to...), or most any other limited resource a computer might have.
What I propose, then, is that someone create a reference algorithm for
something. Let's take the following:
(defun count-atoms (list)
(cond
((endp list) 0)
((consp list) (count-atoms (rest list)))
(T (+ 1 (count-atoms (rest list))))))
You see, whether this algorithm is good OR BAD, it doesn't matter -- it's
just a REFERENCE. We define this reference to be 0dBs and 0dBkB in
performance and compactness (dBs measures time, dBkB measures memory
consumption).
Now let's say that someone writes the same function using a different set of
LISP expressions:
; HYPOTHETICAL -- bear with me here, folks.
; (if (expression) (true-result) (false-result))
(defun my-count-atoms (list)
(if (endp list) 0
(if (consp list) (count-atoms (rest list))
(+ 1 (count-atoms (rest list))))))
For some reason or other, let's assume the latter example works four times
faster in most LISP environments. We can say that there's a 6dB gain in
performance (it would exhibit -6dBs behavior), just by changing the cond to
a set of nested if expressions. Let's say it uses twice the memory, though.
Here, we see a 3dB loss in compactness (3dBB or 3dBkB -- doesn't matter if
you're using bytes or kilobytes).
Comments, suggestions or ideas welcome. Flames ignored.
==========================================================================
KC5TJA/6 | -| TEAM DOLPHIN |-
DM13 | Samuel A. Falvo II
QRP-L #1447 | http://www.dolphin.openprojects.net
Oceanside, CA |......................................................
On Tue, 03 Aug 1999 22:54:05 GMT, Samuel A. Falvo II <······@dolphin.openprojects.net> wrote:
>implementation for comparison, the decibel allows most, if not all, the
>qualitative comparisons permitted by the O(x) notation, and also has the
OK, I was speaking out of my butt. I just realized that O(x) is used when
comparing algorithms in isolation. For instance, in both the count-atoms
examples I gave in the previous post, they'd both be O(n).
The decibel idea is best applied when comparing two or more implementations
of algorithms, which is how I am interpretting the debate in front of me.
So really, I see the two systems being used concurrently as a major, major
advantage in the cataloging of algorithms.
For instance, assuming we're cataloging and/or charting dictionary
implementation, we could easily see the following chart take form:
ALGORITHMS FOR DICTIONARY IMPLEMENTATIONS
80386 68000 65816
Algorithm O() Memory Time Memory Time Memory Time
---------------------------------------------------------------------------
Hashing 1 0dBB 0dBs 0dBB 1.2dBs 0.04dBB 0.9dBs
B-Tree n ln n 6dBB -3dBs 5dBB -8dBs 10dBB -4dBs
Suffix Tree ?? 12dBB -12dBs 12dBB -12dBs 12.4dBB -10dBs
.... ... .. .. .. .. .. ..
---------------------------------------------------------------------------
I think the idea is readily clear. Here, we are forming, more or less, a
listing of available algorithms to use to solve a particular problem, with
data pertaining to expected run-time versus data set size (the O() column),
memory and time relationships for a variety of processors, all of which can
be used to help build applications.
>Comments, suggestions or ideas welcome. Flames ignored.
This still applies. :-)
==========================================================================
KC5TJA/6 | -| TEAM DOLPHIN |-
DM13 | Samuel A. Falvo II
QRP-L #1447 | http://www.dolphin.openprojects.net
Oceanside, CA |......................................................
Reini Urban wrote: [1999-08-02 20:50 +0000]
[...]
> strict BigO only knows some cases, i found six:
> constant (=1),
> logarithmic (=lgn or log2(n)),
> linear (=n)
> n*lgn ("almost linear" and strangely enough very common)
This is called linearithmic (LINEar-logARITHMIC); I forget who
invented this word.
> polynomial (=n^k) and
> exponential (=k^n).
>
> is this correct?
Well, you could also have n^k*log(n) etc. Also, k could be a ratio
in which case I'm not sure one uses the term `polynomial.'
And it gets more interesting when there is more than one
parameter, e.g. O(m*n^2*exp(k)).
Vassil Nikolov
Permanent forwarding e-mail: ········@poboxes.com
For more: http://www.poboxes.com/vnikolov
Abaci lignei --- programmatici ferrei.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Reini Urban wrote: [1999-08-01 14:32 +0000]
[...]
> the looping version is too slow
I suppose this refers to doing it 1 bit at at time
(otherwise `looping' vs. `recursive' (below) does
not make much sense).
> and the recursive version
> as this in autolisp:
> (defun LOGCOUNT (n)
> (cond ((zerop n) 0)
> ((minusp n) (logcount (~ n)))
> (t (+ (logcount (lsh n -4))
> (nth (rem n 16) '(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)
> )))))
>
> or in scheme with vectors (from the slib):
> (define (logical:ash-4 x)
> (if (negative? x)
> (+ -1 (quotient (+ 1 x) 16))
> (quotient x 16)))
> (define (logical:logcount n)
> (cond ((zero? n) 0)
> ((negative? n) (logical:logcount (logical:lognot n)))
> (else
> (+ (logical:logcount (logical:ash-4 n))
> (vector-ref '#(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)
> (modulo n 16))))))
>
> is logarithmic for bigint,
_Linear_ in the length of the bignum (would be logarithmic if
the bigger the bignum, the bigger the pieces were that are
`consumed' at every iteration): if the integer has n bits,
this takes n/4 iterations.
> but O(2) for 32-bit fixnums.
O(2) is the same as O(1) or O(1024), as has already been pointed out.
> the constant version does some logand and shifting as in this c (better
> "d") version:
> from clisp for 32-bit ints
> x32 = (x32 & 0x55555555UL) + ((x32 & 0xAAAAAAAAUL) >> 1);
> x32 = (x32 & 0x33333333UL) + ((x32 & 0xCCCCCCCCUL) >> 2);
> x16 = high16(x32)+low16(x32);
> x16 = (x16 & 0x0F0FU) + ((x16 & 0xF0F0U) >> 4);
> x16 = (x16 & 0x00FFU) + (x16 >> 8);
Wouldn't it be more perspicuous if the last line were written as
count = high8(x16) + low8(x16);
(yes, I can guess that high16() and low16() are probably primitives
but I am primarily interested in expressiveness).
> this is the trick i looked for because i uses some magic numbers not so
> easy to guess. cmucl has the fast assembler versions for all CPU's but I
> couldn't remember the name what to look for. LOGCOUNT was the hint.
> i could only vaguely remember knuth or bentley mentioning the trick
> somewhere. thanks.
It is certainly an interesting exercise to come up with this solution
but in terms of speed I don't see it radically^1 faster than the solution
which does it in 4-bit bytes and table lookup (ceteris paribus, i.e.
with the same efficiency and optimisations of fixnum operations
in both cases) and I expect that doing table lookup by 8-bit bytes
(not to mention 16-bit bytes) would be faster (4 LDB's, 4 vector
references, 3 additions vs. 4 LDB's, 5 masks, 5 additions for the
magic number solution) (here LDB is considered to be equivalent
to `mask and shift').
__________
^1 `radically' means at least by an order of magnitude
Vassil Nikolov
Permanent forwarding e-mail: ········@poboxes.com
For more: http://www.poboxes.com/vnikolov
Abaci lignei --- programmatici ferrei.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Reini Urban <······@sbox.tu-graz.ac.at> wrote:
+---------------
| I vaguely remember that there existed some trick to count the bits == 1
| in a fixnum in constant time. ...
| something with logior, logand or similar...
| can anybody point me to the trick?
+---------------
Not sure how to make this work nicely with arbitrarily-large bignums,
but for fixed-sized numbers the standard "trick" you're probably thinking
of is to add up the bits in ever-widening "combs". Please excuse my use of
C here -- I'm not familiar enough with the corresponding operations in CL.
Assuming type "unsigned long" is 32 bits, then we have:
int countbits(unsigned long x) {
if (x == 0) /* fast case */
return 0;
x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);
x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff);
return (int)x;
}
After the first assignment, successive pairs of bits within "x" each
have the value 0, 1, or 2, depending on whether the original pair was
both clear, one set, or both set. The "trick" is that this sum cannot
overflow into an adjacent pair. And so it goes, with the width of
the "sum buckets" doubling each time until there is just one "bucket"
containing the count of the total number of non-zero bits in the
original word.
-Rob
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. FAX: 650-933-0511
Mountain View, CA 94043 PP-ASEL-IA
····@rigden.engr.sgi.com (Rob Warnock) writes:
<
< Reini Urban <······@sbox.tu-graz.ac.at> wrote:
< +---------------
< | I vaguely remember that there existed some trick to count the bits == 1
< | in a fixnum in constant time. ...
< | something with logior, logand or similar...
< | can anybody point me to the trick?
< +---------------
<
< Not sure how to make this work nicely with arbitrarily-large bignums,
< but for fixed-sized numbers the standard "trick" you're probably thinking
< of is to add up the bits in ever-widening "combs". Please excuse my use of
< C here -- I'm not familiar enough with the corresponding operations in CL.
< Assuming type "unsigned long" is 32 bits, then we have:
<
< int countbits(unsigned long x) {
< if (x == 0) /* fast case */
< return 0;
< x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
< x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
< x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
< x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);
< x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff);
< return (int)x;
< }
I think a close equivalent would be like so.
(defun countbits (x)
;; (check-type x (unsigned-byte 32))
(setq x (ldb (byte 32 0) x))
(unless (zerop x)
(setq x (+ (logand (ash x -1) #x55555555) (logand x #x55555555)))
(setq x (+ (logand (ash x -2) #x33333333) (logand x #x33333333)))
(setq x (+ (logand (ash x -4) #x0f0f0f0f) (logand x #x0f0f0f0f)))
(setq x (+ (logand (ash x -8) #x00ff00ff) (logand x #x00ff00ff)))
(setq x (+ (logand (ash x -16) #x0000ffff) (logand x #x0000ffff))))
x)
< After the first assignment, successive pairs of bits within "x" each
< have the value 0, 1, or 2, depending on whether the original pair was
< both clear, one set, or both set. The "trick" is that this sum cannot
< overflow into an adjacent pair. And so it goes, with the width of
< the "sum buckets" doubling each time until there is just one "bucket"
< containing the count of the total number of non-zero bits in the
< original word.