C90 long long

[Bartc]

From an article about implementing a C99 to C90 translator...

How does someone use integer arithmetic of at least 64 bits, and write in
pure C90?

As I understand C90 (the standard is very elusive), long int is guaranteed
to be at least 32 bits only.

So, do people rely on their known compiler limits, use clunky emulations, or
do not bother with 64 bits when writing ultra-portable code?

 

[Harald van Dijk]

From an article about implementing a C99 to C90 translator...

How does someone use integer arithmetic of at least 64 bits, and write
in pure C90?

As I understand C90 (the standard is very elusive), long int is
guaranteed to be at least 32 bits only.

Correct. And as long int is the widest type, C90 does not guarantee the
presence of any 64-bit integer type.

So, do people rely on their known compiler limits, use clunky
emulations, or do not bother with 64 bits when writing ultra-portable
code?

People do whatever works best for their situation. Sometimes, that may
involve redefining the problem to fit 32-bit arithmetic (or floating-
point). Sometimes, that may be to rely on long being 64 bits. Sometimes,
that may be to use implementation extensions. In any case, it's very much
the same as how C90 programs have to deal with complex arithmetic. The
language and library don't provide any possibility, so portable programs
have no choice but to implement it themselves.

 

[jacob navia]

From an article about implementing a C99 to C90 translator...

Interesting interesting.

And when you are going to do a C89 to K&R translator?

How does someone use integer arithmetic of at least 64 bits, and write in
pure C90?

There is no 64 bit arithmetic in C89. And you will have to do it
yourself!

(It is really easy. You just write it in C89. Not very difficult)

You translate

long long a,b,c;

....

b = (a+b)/(5+c);

by

assign64(div64(sum64(a,b),sum64(5,c)),&b);

You define
struct INT64{long hipart;long lowpart;};

and there you go!

Since you are doing a translator, nobody cares about how
difficult is to write the resulting code, or how readable it is!

 

[Barry Schwarz]

From an article about implementing a C99 to C90 translator...

How does someone use integer arithmetic of at least 64 bits, and write in
pure C90?

As I understand C90 (the standard is very elusive), long int is guaranteed
to be at least 32 bits only.

So, do people rely on their known compiler limits, use clunky emulations, or
do not bother with 64 bits when writing ultra-portable code?

Many use a "big number library" that simulates arithmetic on very wide
integers. I think Richard Heathfield put one on the web and google
can probably find you others.


Remove del for email

 

[jacob navia]

Many use a "big number library" that simulates arithmetic on very wide
integers. I think Richard Heathfield put one on the web and google
can probably find you others.


Remove del for email

That GUARANTEES that the software will run VERY slowly using
ALL the CPU for nothing. Heathfield's big numbers use characters
as the base representation.

 

[Keith Thompson]

Interesting interesting.

And when you are going to do a C89 to K&R translator?

It's been done; google "ansi2knr". Though as I recall it's not a
complete translator; mostly it converts prototypes to old-style
function declarations.

The point, of course, is that a C89 to K&R translator, though it was
quite useful years ago, is no longer of much interest today, since the
C89 standard is almost universally supported (it would be difficult to
find a platform that has a K&R compiler but no C89 compiler). This is
not yet the case for C99, a fact that you insist on ignoring, even
though your own lcc-win doesn't support the full language.

A C99 compiler that uses C89 as its intermediate language might be a
very useful thing. If it managed to generate portable C89 code, it
could even permit the use of C99 on platforms where no C99 compiler
yet exists (something I would think you'd welcome).

I suspect that modifying an existing C89 compiler to handle C99 would
be easier than writing a complete translator (but the latter would
potentially only have to be done once for all target platforms).

There is no 64 bit arithmetic in C89. And you will have to do it
yourself!

Yes, that's probably one of the more difficult aspects of translating
C99 to C89. A quibble, though: C89 has no *guaranteed* 64-bit
arithmetic; it's perfectly legal to make long 64 bits.

 

[jacob navia]

Barry Schwarz said:



Actually, no, I haven't. I've got one, but I haven't published it.

As Mr Navia notes elsethread, it uses an array of unsigned char to store
the data. He seems to think that this "GUARANTEES that the software will
run VERY slowly using ALL the CPU for nothing". It doesn't, of course.
Nevertheless, performance was not my highest priority. Those who want a
super-fast bignum library would be well advised to use GMP or Miracl.

Using a char to store bignum data is like using a scooter to
move a 38 ton trailer.

It will work of course, and the 38 ton trailer will have a cruising
speed of several centimeters/hour...

Who cares?

That solution is PORTABLE. You can carry a scooter anywhere, they
are standard solutions, etc.


Portability means very often that you make mediocre software
that runs anywhere because it never uses the hardware/OS to
its maximum possibilities but just uses the least common
denominator of each one.

This is fine if you do not care about usability or similar problems.
GUIs?

Not portable. The command line is portable. Use the command line

Network?
Not portable...

Etc.

But this is more a philosophical question. Heathfield's viewpoint
is perfectly acceptable if you say:

Usability is less valuable than portability.
As he said, performance wasn't a concern for his software.
Portability was.

Result?

A mediocre but perfectly portable software.

 

[Richard]

Using a char to store bignum data is like using a scooter to
move a 38 ton trailer.

It will work of course, and the 38 ton trailer will have a cruising
speed of several centimeters/hour...

Who cares?

That solution is PORTABLE. You can carry a scooter anywhere, they
are standard solutions, etc.


Portability means very often that you make mediocre software
that runs anywhere because it never uses the hardware/OS to
its maximum possibilities but just uses the least common
denominator of each one.

This is fine if you do not care about usability or similar problems.
GUIs?

Not portable. The command line is portable. Use the command line

Network?
Not portable...

Etc.

But this is more a philosophical question. Heathfield's viewpoint
is perfectly acceptable if you say:

Usability is less valuable than portability.
As he said, performance wasn't a concern for his software.
Portability was.

Result?

A mediocre but perfectly portable software.

And guess what? Most of the blowhards in this group write SW which never
gets ported anywhere anyway.

 

[Flash Gordon]

Richard wrote, On 06/04/08 19:41:
Richard has on more than one occasion explicitly recommended using other
bignum libraries if you want one with high performance. He even provided
such recommendations in the post you responded to. Of course, a library
that is not fully portable can (and if performance is the aim should)
make use of non-portable tricks to get all the performance it can,
possibly including conditional use of in-line assembler.

And guess what? Most of the blowhards in this group write SW which never
gets ported anywhere anyway.

Where is your proof that people have been lying when they have been
talking about the porting of their SW that occurs in real life?

 

[Bartc]

From an article about implementing a C99 to C90 translator...

How does someone use integer arithmetic of at least 64 bits, and write in
pure C90?

As I understand C90 (the standard is very elusive), long int is guaranteed
to be at least 32 bits only.

So, do people rely on their known compiler limits, use clunky emulations,
or do not bother with 64 bits when writing ultra-portable code?

OK, so for this to be practical, such a translator needs to know the
capabilities of a C90 installation. If it has 64+ bit ints, then use them,
otherwise make other arrangements. A pure translator would be of academic
interest only.

Attend to 1000 other details and such a translator may be feasible.

(Note: I am not creating such a software, just interested in the issues.)

 

[jacob navia]

OK, so for this to be practical, such a translator needs to know the
capabilities of a C90 installation. If it has 64+ bit ints, then use them,
otherwise make other arrangements. A pure translator would be of academic
interest only.

Attend to 1000 other details and such a translator may be feasible.

(Note: I am not creating such a software, just interested in the issues.)

The bad news is that you will need:

o alloca() for implementing VLA arrays.
o a complex math library
o a 64 bit library
o Your own printf/scanf/ versions
o Many math library functions like remquo(), erf() lgamma()
and several others
o You will have to implement fexxx() functions (floating point
environment manipulating functions).
This needs to be done in assembly for the most part.
o You will need a C99 parser


The good news is that I can sell you all of the above for several
popular OSes

 

[Keith Thompson]

The bad news is that you will need:

o alloca() for implementing VLA arrays.

[snip]

No, the usual behavior of alloca() (space is deallocated on return
from the calling function) is incompatible with the requirements for
VLAs. For example, given this:

for (int i = 1; i <= 1000; i ++) {
int vla;
// ...
}

an alloca-based implementation would allocate space for all 1000
instances of ``vla'' before deallocating any of them. I suppose you
could argue that the standard doesn't actually require that the
storage be physically deallocated on leaving the object's scope, but
it would be a seriously flawed implementation.

If you have an alloca()-like function that frees the storage on exit
from the scope, then that's not a problem (though it wouldn't satisfy
the usual, somewhat informal, requirements for alloca()).

(Didn't we discuss this just recently?)

 

[Bartc]

The bad news is that you will need:

o alloca() for implementing VLA arrays.

I'm sure VLA and/or alloca() can be emulated with malloc(), where the native
C90 does not have alloca().

o a complex math library

I would eliminate that completely, even though the popularity of my
translator would really suffer.

o a 64 bit library

And written in C90, I know.

o Your own printf/scanf/ versions

These are not in C90? Just a few extra formats needed.

o Many math library functions like remquo(), erf() lgamma()
and several others
o You will have to implement fexxx() functions (floating point
environment manipulating functions).
This needs to be done in assembly for the most part.

C seems a popular intermediate language, and presumably that is not C99. So
how do those other language compilers get around the problem of implementing
fexxx/remquo etc in assembler?

o You will need a C99 parser

This should be OS-independent at least.

The good news is that I can sell you all of the above for several popular
OSes

It would have to be for *every* OS; anything that has a C90 implementation.
And it would all have to be pure C90, no assembler.

 

[jacob navia]

I'm sure VLA and/or alloca() can be emulated with malloc(), where the native
C90 does not have alloca().

Yes but you will have to free the malloced memory
at block exit...

I would eliminate that completely, even though the popularity of my
translator would really suffer.

Then you are not C99 compliant

And written in C90, I know.


These are not in C90? Just a few extra formats needed.

You will need to parse "%Lg" for instance, long double modifiers,
then "ll" long long modifiers, the hexadecimal %a for floats,
and many other goodies...

I *thought* that I could write my own printf by just "preprocessing"
the format string and calling an underlying printf but that wasn't very
efficient nor was it very easy. I ended up implementing my own
printf. Since you are not concerned about code quality, you can take
the preprocessing approach.

C seems a popular intermediate language, and presumably that is not C99.

Yes it is. I would recommend you buying the standard C99 first.
Specifically the floating point manipulating functions are part
of the standard. All of the functions I named above are part
of the standard.

So
how do those other language compilers get around the problem of implementing
fexxx/remquo etc in assembler?

lcc-win implements it in assembler. What else?

This should be OS-independent at least.


It would have to be for *every* OS; anything that has a C90 implementation.
And it would all have to be pure C90, no assembler.

printf/erf/lgamma are written in C. The floating point environment
manipulating functions are in assembler, and they *have* to be written
in assembler for EACH supported FPU.

 

[Bartc]

jacob navia said:

[big num stuff]

Fine, if you say so - but that's *my* problem, right? Nobody else's.
I'm not advocating that anyone else should use this software. For the
record, however, yes, my bignum library is significantly slower than
GMP (it takes about 20 times as long as GMP to calculate factorials,
for instance). So what?

How long does it take to calculate 5^(4^(3^(2^1)))? (Ie. raising to the
power.)

This came up in comp.programming a few weeks back. I knocked up a quick
library that used byte arrays and stored a single decimal digit in each
byte. And that was in interpreted code! (Only add unsigned and multiply by
single digit were compiled.)

This took some 15 minutes to calculate the 183000-digit result (on a slowish
Pentium cpu).

Just interested in how much extra work is needed...

 

[jacob navia]

jacob navia said:

[big num stuff]

Fine, if you say so - but that's *my* problem, right? Nobody else's.
I'm not advocating that anyone else should use this software. For the
record, however, yes, my bignum library is significantly slower than
GMP (it takes about 20 times as long as GMP to calculate factorials,
for instance). So what?

How long does it take to calculate 5^(4^(3^(2^1)))? (Ie. raising to the
power.)

This came up in comp.programming a few weeks back. I knocked up a quick
library that used byte arrays and stored a single decimal digit in each
byte. And that was in interpreted code! (Only add unsigned and multiply by
single digit were compiled.)

This took some 15 minutes to calculate the 183000-digit result (on a slowish
Pentium cpu).

Just interested in how much extra work is needed...

The french package "pari" calculates that in around 0.5 seconds
(In a dual core amd)

 

[Bartc]

jacob navia said:

[big num stuff]

It will work of course, and the 38 ton trailer will have a cruising
speed of several centimeters/hour...
Fine, if you say so - but that's *my* problem, right? Nobody else's.
I'm not advocating that anyone else should use this software. For
the record, however, yes, my bignum library is significantly slower
than GMP (it takes about 20 times as long as GMP to calculate
factorials, for instance). So what?

How long does it take to calculate 5^(4^(3^(2^1)))? (Ie. raising to
the power.)

This came up in comp.programming a few weeks back. I knocked up a
quick library that used byte arrays and stored a single decimal
digit in each byte. And that was in interpreted code! (Only add
unsigned and multiply by single digit were compiled.)

This took some 15 minutes to calculate the 183000-digit result (on a
slowish Pentium cpu).

Just interested in how much extra work is needed...

The french package "pari" calculates that in around 0.5 seconds
(In a dual core amd)

So I need to make it about 1000 times faster then, on my slower machine. No
problem..

 

[user923005]

Dann Corbit said:

[...] Those who want a
super-fast bignum library would be well advised to use GMP or Miracl.

Neither of those libraries are a good choice for 64 bit operations.

Quite so, although the way I see it, if you need more than 32 bits, you
probably need arbitrarily many bits, or at least way more than 64. The
most common use I'm aware of for needing more than C90 gives you is calcs
involving RSA and D-H, for both of which 64 bits isn't anywhere like
enough.

There are also lots of useful calculations that benefit directly from
64 bit math like Chess programming (uses a 64 bit integer to hold the
board representation frequently) and things like the UMAC hash:
http://fastcrypto.org/umac/

Database systems often need to use 64 bit values, because 32 bit
values (e.g. transaction IDs or record serial ID values) tend to
overflow over time.

 

[user923005]

user923005 said:

[...] if you need more than 32 bits, you
probably need arbitrarily many bits, or at least way more than 64. The
most common use I'm aware of for needing more than C90 gives you is
calcs involving RSA and D-H, for both of which 64 bits isn't anywhere
like enough.

There are also lots of useful calculations that benefit directly from
64 bit math like Chess programming (uses a 64 bit integer to hold the
board representation frequently) and things like the UMAC hash:
http://fastcrypto.org/umac/

I accept that I ought to have remembered bitboards.

Database systems often need to use 64 bit values, because 32 bit
values (e.g. transaction IDs or record serial ID values) tend to
overflow over time.

Well, no, what they need is "big-enough" values. If overflow is
unacceptable, then the day may come when a 64-bit value won't do.

Admittedly that day may be some way away. A computer whose job is to record
every human born on this planet (assuming the population continues to grow
at about 10% every 7 years) will not overflow a 64-bit ID until the year
3604, by which time - with 123000 people for every square metre of land -
we'll have more to worry about than computers not working properly.

That day has been here for a long time now. Take a look at the
PostgreSQL mailing list and you will see that 32 bit values caused no
end of headaches due to wrap around.
All of these systems perform over one million TPS:
http://www.tpc.org/tpcc/results/tpcc_perf_results.asp
There are 86400 seconds in one day, so we have 86,400,000,000
transactions in one day. It will take about one hour to exhaust a 32
bit transaction ID or overflow a 32 bit serial value for a synthetic
primary key to store on disk.

There are dozens of petabyte database systems today.

 

[jacob navia]

Dann Corbit said:

[...] Those who want a
super-fast bignum library would be well advised to use GMP or Miracl.

Neither of those libraries are a good choice for 64 bit operations.

Quite so, although the way I see it, if you need more than 32 bits, you
probably need arbitrarily many bits, or at least way more than 64. The
most common use I'm aware of for needing more than C90 gives you is calcs
involving RSA and D-H, for both of which 64 bits isn't anywhere like
enough.

<snip>

Never used a file bigger than 4GB?

With disks of 500GB now, a database of more than 4GB is
quite common.

Timestamps are 64 bits now, under windows.