How to write a small graceful gcd function?

[Michael Wojcik]

Third, most processors don't even have division opcodes [mips, ARM, PPC
anyone?]

According to my PPC assembly reference (_PowerPC Microprocessor
Developer's Guide_, Bunda et al), PPC does have integer divide
opcodes (divd[o][.], divdu[o][.], divw[o][.], and divwu[o][.]) and
floating-point divide opcodes (fdiv[.] and fdivs[.]). It states that
some of those are only available in the 64-bit versions of the
processor, but divw is available in all versions.

I suppose that might have changed since the book was published.

 

[Richard Tobin]

For constant sized implementations of an algorithm O() doesn't apply.
O() applies to the algorithm itself when not restrained to given
operand sizes.

But there is an obvious extension, generally clear from the context,
to implementations limited to a maximum size. For example, if an
operation on a 64-bit number takes time proportional to the position
of the highest bit set in the number, we can say that it is O(log N)
even though you can't make N tend to infinity.

-- Richard

 

[Nils Weller]

Third, most processors don't even have division opcodes [mips, ARM, PPC
anyone?]

According to my PPC assembly reference (_PowerPC Microprocessor
Developer's Guide_, Bunda et al), PPC does have integer divide
opcodes (divd[o][.], divdu[o][.], divw[o][.], and divwu[o][.]) and
floating-point divide opcodes (fdiv[.] and fdivs[.]). It states that
some of those are only available in the 64-bit versions of the
processor, but divw is available in all versions.

I suppose that might have changed since the book was published.

I recently ran into this stuff when I started porting my C compiler to
PowerPC. Apparently integer division instructions are available in PPC,
but not in POWER. The IBM AIX assembler has a compatibility mode (-mcom)
in which instructions that are not available in both POWER and PowerPC
are rejected, and it rejects division. This is also the default setting.
The -many mode can be used to allow for any available instruction to be
used.

grep div y.asm divw 3, 3, 4
as y.asm -u

Assembler:
y.asm: line 53: 1252-149 Instruction divw is not implemented in the
current assembly mode COM.

 

[Keith Thompson]

Isn't saying "multiplication is O(1)" saying "multiplication takes
constant time", independent of the operands?

No, it means independent of operand SIZE [or complexity if you will].

In the computer science world O() is typically a function of input
size, e.g. sort set size, input width, etc...

Which - for fixed-size arguments, eg 32-bit int(egers) such as are
found on many machines & in many programming languages - is, I thought,
true.

For constant sized implementations of an algorithm O() doesn't apply.
O() applies to the algorithm itself when not restrained to given
operand sizes.

Then why are you wasting time arguing about how O() notation applies
to multiplication of fixed-size operands?

Multiplication of fixed-size operands is typically either O(1) or
O(meaningless) (for the moment, I really don't care which). The time
it takes to perform a 32-bit multiplication is (typically) independent
of the values of the operands. (It doesn't depend in any meaningful
way on the *sizes* of the operands, since we're assuming those sizes
are fixed.)

For example, if I have an algorithm that works on an array of 32-bit
integers, its performance is dominated by 32-bit multiplications, and
it performs N log N multiplications for an N-element array, then it's
an O(N log N) algorithm. I don't have to multiply N log N by some
term that accounts for the complexity of an individual multiplication;
that's just a constant, and it disappears.

Multiplication of variable-size operands (e.g, bignums) is O(something
bigger), perhaps O(N**2).

You're talking about two different things. Each of them is reasonably
well understood, but you're creating confusion by conflating them.

 

[Mark McIntyre]

Well, O(1) means "takes the same time irrespective of the magnitude of
the argument". I strongly suspect this is true for actual real
computer systems.

Except that O() notation doesn't apply to fixed implementations of an
algorithm because the size doesn't change [nor approach oo].

Bollocks. And End of Discussion.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Ben Bacarisse]

This is true -- or more precisely, g(n) = O(f(n)) means g(n) is
bounded above by f(n). That is, there is some constant c and value
x-sub-0 such that for all x > x-sub-0, g(x) <= c f(x). (There are
also Omega and Theta notations for bounded below, and bounded on
both sides.)

But:


This is *not* true. If k is any constant, O(k) and O(1) mean
the same thing, since the constant can be "moved out": if k is
a constant, then g(k) = k g(1), so we can replace c f(x) with
(k*c) f(x) above.

I hate to jump into such a heated debate, and particularly to correct
a post of yours since I usually find them so informative, but you have
used some algebraic smoke and mirrors there!

Yes, O(k) is O(1) if k is constant but for an operation on a
fixed-sized input we do not know if k is a constant -- it is a
function defined at only one point: 64 (or, if you insist, it can be
thought of as defined on the domain [0, 64]). Big O is only defined
for functions over R (or sometimes R+ or Z+). It has no formal
meaning (as far I know) for functions defined over finite sets.

=== On the more general argument ===

Posters on Usenet are often rather loose with big Os. To avoid
arguments such as this one must be clear about how the problem is
"measured" and exactly what the primitive operations of the abstract
machine are. Saying that multiplication of fixed-size numbers is
O(anything) is lax at best (meaningless at worst) but to describe
a given gcd algorithm as "O(whatever) in the number of arithmetic
operations performed" is fine if a little informal.

Often, if someone says "operation X is O(1)" what they really mean is
"I consider operation X to be one of the primitive operations in term
of which I want to analyse my algorithm".

For many who write gcd algorithms, multiplication is not a primitive
operation because they are thinking in term of bignums and
cryptography (certainly true the only time I had to do it) but for
someone doing matrix operations it may be perfectly reasonable to
consider all fixed-size arithmetic ops as "primitive".

To make matters worse (as happened here) people will often post some
code in C and say it has such-and-such a time (or space) complexity
when, formally, it can't have one because the inputs are bounded by
some C type or other. What they want the reader to do is abstract the
algorithm out and consider it running on some ideal C machine but it
is not always clear (as in this case) if that just involves having
arbitrary resources available or also includes unbounded integers (or
some other idealised types).

 

[av]

"Richard Heathfield" wrote in message

yes but in what i know division for 2 registers is slow than sub for 2
register

I have downloaded some of his work, a long time ago. I know that he knows
what he is talking about when it comes to bignums. I know that he is
intelligent and good at mathematics. Be that as it may, none of the GCD
algorithms presented were O(n^2).

yes is O(1) but who use 20 divisions is slower than who use 20 subs

I think his analysis is probably correct if we are finding the GCD of two
billion digit numbers with arbitrary precision number classes. But that is
not the algorithm that was up for discussion.

seems i remember O(f(n)) and n is the size in bit for input

I am through arguing about it. In fact, this thread was a reminder to me of
why I stopped posting on USENET for a couple years.

usenet is a wonderful place for to learn
in usenet is enough say our own position without much discussion
it is the reader that see who is right and for me almost always is
right who speak few

 

[Dann Corbit]

Yes, O(k) is O(1) if k is constant but for an operation on a
fixed-sized input we do not know if k is a constant -- it is a
function defined at only one point: 64 (or, if you insist, it can be
thought of as defined on the domain [0, 64]). Big O is only defined
for functions over R (or sometimes R+ or Z+). It has no formal
meaning (as far I know) for functions defined over finite sets.

Well, it works fine (math-wise) for finite sets. It just turns
degenerate: *everything* is O(1).

Of course, "real computers" are finite, so this means that every
algorithm can be called O(1). Clearly this is not what we want!
The "obvious" solution is to allow anything that is a variable
to go to infinity, even though technically the size of, e.g., an
input being sorted with an "O(n log n)" sort routine is in fact
bounded by attached storage. If you only have 10 TB of file space,
you will not be sorting 200 tera-items of data. But if we claim
that this sort is therefore O(10T log 10T) and thus O(1) ... well,
that may be *true*, but it is not a useful claim.

Posters on Usenet are often rather loose with big Os. To avoid
arguments such as this one must be clear about how the problem is
"measured" and exactly what the primitive operations of the abstract
machine are.

Indeed.

Consider the game of chess. It has a branching factor of about 35. So, on
average, there are about 35 possible moves you can make at a given stage of
the game.

By using the alpha-beta search algorithm, you can reduce the branching
factor to ~sqrt(35) which is about 6. Through various other tricks like
null move pruning, transposition tables, etc. you can reduce the branching
factor to about 2 if you have a very smart program. Now, it has been
formally proven that there are less than 6000 full moves (a full move is one
move for each side) in the game of chess.

So a really powerful chess program could {approximately} solve the game of
chess with only 6000 plies searched, which would amount to 2^6000 positions
analyzed.

As you know, 2^6000 is just a large constant. But it is so large that it
may as well be infinity (at the present stage of compute power). So
describing the branching factor of chess and considering chess as an
exponential problem still makes sense.

The notion of O(f(n)) is useful for average case projections of how a
problem set behaves. The travelling salesman problem is another hard
problem. But there are not an infinite number of cities in the world. So
(again) we could consider TSP to be O(1) with a huge constant of
proportionality. However, that is not really useful because we can't
calculate an optimal path to visit every city on earth with minimal travel
distance.

Similarly with sorting, we want to know how the problem scales over
different vector lengths. This is useful so that we can calculate how much
it will cost us to sort a given vector.

I'm not sure there is any relevance to C in this post, so probably it is
misplaced.

[additional details snipped]
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to
spammers.

 

[jaysome]

Yes, O(k) is O(1) if k is constant but for an operation on a
fixed-sized input we do not know if k is a constant -- it is a
function defined at only one point: 64 (or, if you insist, it can be
thought of as defined on the domain [0, 64]). Big O is only defined
for functions over R (or sometimes R+ or Z+). It has no formal
meaning (as far I know) for functions defined over finite sets.

Well, it works fine (math-wise) for finite sets. It just turns
degenerate: *everything* is O(1).

Of course, "real computers" are finite, so this means that every
algorithm can be called O(1). Clearly this is not what we want!
The "obvious" solution is to allow anything that is a variable
to go to infinity, even though technically the size of, e.g., an
input being sorted with an "O(n log n)" sort routine is in fact
bounded by attached storage. If you only have 10 TB of file space,
you will not be sorting 200 tera-items of data. But if we claim
that this sort is therefore O(10T log 10T) and thus O(1) ... well,
that may be *true*, but it is not a useful claim.

Posters on Usenet are often rather loose with big Os. To avoid
arguments such as this one must be clear about how the problem is
"measured" and exactly what the primitive operations of the abstract
machine are.

Indeed.

Consider the game of chess. It has a branching factor of about 35. So, on
average, there are about 35 possible moves you can make at a given stage of
the game.

By using the alpha-beta search algorithm, you can reduce the branching
factor to ~sqrt(35) which is about 6. Through various other tricks like
null move pruning, transposition tables, etc. you can reduce the branching
factor to about 2 if you have a very smart program. Now, it has been
formally proven that there are less than 6000 full moves (a full move is one
move for each side) in the game of chess.

So a really powerful chess program could {approximately} solve the game of
chess with only 6000 plies searched, which would amount to 2^6000 positions
analyzed.

As you know, 2^6000 is just a large constant. But it is so large that it
may as well be infinity (at the present stage of compute power). So
describing the branching factor of chess and considering chess as an
exponential problem still makes sense.

The notion of O(f(n)) is useful for average case projections of how a
problem set behaves. The travelling salesman problem is another hard
problem. But there are not an infinite number of cities in the world. So
(again) we could consider TSP to be O(1) with a huge constant of
proportionality. However, that is not really useful because we can't
calculate an optimal path to visit every city on earth with minimal travel
distance.

Similarly with sorting, we want to know how the problem scales over
different vector lengths. This is useful so that we can calculate how much
it will cost us to sort a given vector.

I'm not sure there is any relevance to C in this post, so probably it is
misplaced.

It wasn't misplaced for me. It made me go off and research
"alpha-beta" search algorithms and "branching factors" and "null move
pruning", inter alia. As a C programmer, I can imagine those things
might be useful someday.

Immeasurable Thanks

 

[Don]

The temporary is unnecessary, and the formatting is just odd. Here's
how I'd write it:

int gcd(int m, int n)
{
if (n == 0) {
return m;
}
else {
return gcd(n, m % n);
}
}

int gcd(int m, int n)
{
return n ? gcd(n, m%n) : m;
}

Don

 

[Keith Thompson]

int gcd(int m, int n)
{
return n ? gcd(n, m%n) : m;
}

Sure, that's also valid, but I prefer my version. Personally, I
dislike treating an integer as a condition rather than explicitly
comparing it to 0 *unless* it's actually being used as a boolean. I
also tend to prefer if/else to ?: in most cases. For something this
small, it's not a big deal, but it can quickly grow into IOCCC
material.

<OT>
To the person who e-mailed me regarding this thread: anonymous e-mails
are unwelcome and will be ignored. If you want to comment on
something I've written here, do so here. If you must contact me by
e-mail, have the courtesy to identify yourself.
</OT>

 

[lovecreatesbeauty]

Sure, that's also valid, but I prefer my version. Personally, I
dislike treating an integer as a condition rather than explicitly
comparing it to 0 *unless* it's actually being used as a boolean.

I remember that you said you dislike the _Bool keyword and bool, true,
false macros in a post before.

And, in K&R2 sec3.2, it says that the shortcut is preferred when the
expression tests its value even the expression is a numeric value. It
says, ` the most obvious is writing if (expression) instead of if
(expression ! = 0) '.

In sec5.5, it says, a comparison against 0 ('\0' equals 0, right?) is
redundant. And it writes the final abbreviation version of strcpy
containing this single statement: while (*s++ = *t++) ;

 

[Keith Thompson]

I remember that you said you dislike the _Bool keyword and bool, true,
false macros in a post before.

No, I don't believe I did. In fact, I wish that bool, true, and false
had been in the language from the very beginning <OT>as they were in
C++</OT>. Of course we can't yet assume that they're supported by all
compilers -- but it's easy enough to define them yourself if you need
them. (I find the keyword _Bool a bit ugly, but I understand the need
to avoid stepping on existing code.)

And, in K&R2 sec3.2, it says that the shortcut is preferred when the
expression tests its value even the expression is a numeric value. It
says, ` the most obvious is writing if (expression) instead of if
(expression ! = 0) '.

Ok, so I disagree with K&R2 on this point. I don't have my copy of
K&R2 handy; I'll look up the exact wording later, and perhaps comment
further.

In sec5.5, it says, a comparison against 0 ('\0' equals 0, right?) is
redundant. And it writes the final abbreviation version of strcpy
containing this single statement: while (*s++ = *t++) ;

That particular form is idiomatic enough that it doesn't bother me too
much, but in general I prefer to be more explicit, even at the expense
of a few extra keystrokes. I understand that lots of very smart
people don't share this opinion, and we all need to be able to read
code in a variety of styles even if we're more restrictive in what we
write.

 

[ozbear]

No, I don't believe I did. In fact, I wish that bool, true, and false
had been in the language from the very beginning <OT>as they were in
C++</OT>. Of course we can't yet assume that they're supported by all

<snip>

There is no such language as C++< / OT>

Haven't you been reading the rants about this sort of joining?

:O)

Oz