Large number libraries/algorithms

[boltar2003]

Does anyone know of an API that will do standard math ops (*,+,-,/,% etc) on
very large numbers (stored in char arrays presumably)? ie The sort of numbers
that have no chance of fitting in even a 64 bit int or double. Or failing
that is there a good site explaining how to implement them yourself?

Thanks for any info

B2003

 

[Mark Bluemel]

Does anyone know of an API that will do standard math ops (*,+,-,/,% etc) on
very large numbers (stored in char arrays presumably)? ie The sort of numbers
that have no chance of fitting in even a 64 bit int or double. Or failing
that is there a good site explaining how to implement them yourself?

A web search for "C bignum" is probably a good start.

 

[Heikki Kallasjoki]

Does anyone know of an API that will do standard math ops (*,+,-,/,% etc) on
very large numbers (stored in char arrays presumably)? ie The sort of numbers
that have no chance of fitting in even a 64 bit int or double. Or failing
that is there a good site explaining how to implement them yourself?

The GNU Multiple Precision Arithmetic Library (GMP) is relatively
popular:

http://gmplib.org/
http://gmplib.org/manual/Integer-Functions.html

 

[Noob]

Does anyone know of an API that will do standard math ops (*,+,-,/,% etc) on
very large numbers (stored in char arrays presumably)? ie The sort of numbers
that have no chance of fitting in even a 64 bit int or double. Or failing
that is there a good site explaining how to implement them yourself?

https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

fefe's comparison:
http://dl.fefe.de/bignum.pdf

TomsFastMath:
http://libtom.org/?page=features&whatfile=tfm
https://github.com/libtom/tomsfastmath/raw/master/doc/tfm.pdf

Regards.

 

[boltar2003]

The GNU Multiple Precision Arithmetic Library (GMP) is relatively
popular:

http://gmplib.org/
http://gmplib.org/manual/Integer-Functions.html

Thanks, thats just what I need.

B2003

 

[boltar2003]

If your numbers will fit into 128-bit ints, then I think it is quite
common to support 128-bit types in 64-bit compilers, and they will be

I didn't know that. Whats the C type definition for 128 bit ints?

B2003

 

[James Kuyper]

On Mon, 22 Oct 2012 13:29:51 +0200


I didn't know that. Whats the C type definition for 128 bit ints?

in128_t, int_least128_t, int_fast128_t. They're not guaranteed
to be supported, but those names are reserved for that use, and you can
check whether or not the corresponding macros in <stdint.h> are
#defined; they are not allowed to be #defined unless the corresponding
types are supported.

 

[Eric Sosman]

Does anyone know of an API that will do standard math ops (*,+,-,/,% etc) on
very large numbers (stored in char arrays presumably)? ie The sort of numbers
that have no chance of fitting in even a 64 bit int or double. Or failing
that is there a good site explaining how to implement them yourself?

This is Question 18.15d on the comp.lang.c Frequently Asked
Questions (FAQ) page at <http://www.c-faq.com/>.

 

[James Kuyper]

On 22/10/2012 14:01, James Kuyper wrote: ....

in128_t, int_least128_t, int_fast128_t. They're not guaranteed
to be supported, but those names are reserved for that use, and you can
check whether or not the corresponding macros in <stdint.h> are
#defined; they are not allowed to be #defined unless the corresponding
types are supported.

I don't know whether these are necessarily supported by compilers

I do. They aren't. I already said so above.

... (but
if your compiler has them, then use them). Other possibilities are
__int128 (and unsigned __int128), or "long long int".

A conforming implementation of C90 can support long long only as an
extension. An implementation that conforms to either C99 or C2011, and
supports any 128-bit type (with no padding bits, and if signed, 2's
complement representation), has no excuse for not supporting the
corresponding <stdint.h> types. Therefore, looking for other names is
mainly needed only if you're using a C90 implementation that supports
128-bit types. I'm not sure how common those are - but I'd expect them
to be rare.

 

[Ben Bacarisse]

On 22/10/2012 14:01, James Kuyper wrote: ...

in128_t, int_least128_t, int_fast128_t. They're not guaranteed
to be supported, but those names are reserved for that use, and you can
check whether or not the corresponding macros in <stdint.h> are
#defined; they are not allowed to be #defined unless the corresponding
types are supported.

I don't know whether these are necessarily supported by compilers

I do. They aren't. I already said so above.

... (but
if your compiler has them, then use them). Other possibilities are
__int128 (and unsigned __int128), or "long long int".

A conforming implementation of C90 can support long long only as an
extension. An implementation that conforms to either C99 or C2011, and
supports any 128-bit type (with no padding bits, and if signed, 2's
complement representation), has no excuse for not supporting the
corresponding <stdint.h> types. Therefore, looking for other names is
mainly needed only if you're using a C90 implementation that supports
128-bit types.

You also need to look for them for purely practical reasons. For
example, with my gcc version, there is a 128-bit integer type meeting
all the right conditions but int128_t does not exist in c99 mode. The
reason, I imagine, is that compiler and library development are somewhat
separate in gcc, so it's easier to keep stdint.h (and glibc's printf
family) at some sort of "lowest common denominator" level.

 

[Keith Thompson]

If your numbers will fit into 128-bit ints, then I think it is quite
common to support 128-bit types in 64-bit compilers, and they will be
much more efficient than arbitrarily long number libraries. But that
only helps if 128 bits is big enough.

I don't think I've ever seen a C compiler that supports 128-bit
integers. Can you provide an example?

 

[tom st denis]

     This is Question 18.15d on the comp.lang.c Frequently Asked
Questions (FAQ) page at <http://www.c-faq.com/>.

Someone really needs to update that response...

Tom

 

[Ben Bacarisse]

Doesn't Jacob Navia's? And GCC on 64 bit targets usually has at least
partial support.

It supports a type called int128, but it's not an integer type. For
example, you can't cast it to another integer type. It's implemented as
a struct using lcc-win32's operator overloading so it's a matter of
debate if a program using it is using a "C compiler". Jacob's operator
overloading is deliberately unobtrusive but I have not studied the
consequences of not using the compiler in a conforming mode.

gcc provides __int128 "for targets having an integer mode wide enough to
hold 128-bit". I'm not sure exactly what's included in that.

 

[Keith Thompson]

Someone really needs to update that response...

Update it how?

If you have an update, there's a feedback link on each page, or
you can send e-mail to Steve Summit. It doesn't look like there
have been any updates since 2005. I don't know Steve's level of
interest in updating it. (Some information on C11 would be nice.)

 

[tom st denis]

Update it how?

If you have an update, there's a feedback link on each page, or
you can send e-mail to Steve Summit.  It doesn't look like there
have been any updates since 2005.  I don't know Steve's level of
interest in updating it.  (Some information on C11 would be nice.)

The current answer reads:

"Some popular packages are the ``quad'' functions within the BSD Unix
libc sources (ftp.uu.net, /systems/unix/bsd-sources/.../src/lib/libc/
quad/*), the GNU MP library ``libmp'', the MIRACL package (see
http://indigo.ie/~mscott/), the ``calc'' program by David Bell and
Landon Curt Noll, and the old Unix libmp.a."

I doubt "quad" has been maintained for a long time. I can't even get
on the ftp.uu.net server let alone check the status of the package.
GMP is called libgmp.a (fairly certain) and has been for a while.
MIRACL is proprietary, etc...

There are plenty of more modern packages. GMP being one [updated ref
maybe link], the LTM/TFM libraries I worked on back in the day (though
unmaintained are still useful and perform great on modern machines).
The LTM library I wrote for instance is the basis for the bignum
support in Tcl. It's also used by HP on some of their newer
calculators to perform arbitrary precision math internally, etc...

I wouldn't expect a CFAQ maintainer to know about these things, but it
probably wouldn't hurt to google around once in a while...

Tom

 

[Keith Thompson]

[...]
I don't think I've ever seen a C compiler that supports 128-bit
integers. Can you provide an example?

Doesn't Jacob Navia's? And GCC on 64 bit targets usually has at least
partial support.

It supports a type called int128, but it's not an integer type. For
example, you can't cast it to another integer type. It's implemented as
a struct using lcc-win32's operator overloading so it's a matter of
debate if a program using it is using a "C compiler". Jacob's operator
overloading is deliberately unobtrusive but I have not studied the
consequences of not using the compiler in a conforming mode.

gcc provides __int128 "for targets having an integer mode wide enough to
hold 128-bit". I'm not sure exactly what's included in that.

gcc certainly provides it for 64-bit amd64 targets - and I'm guessing
also for other 64-bit targets (such as PPC, MIPS, IA-64). It is
treated much like any other integer type as far as gcc is concerned.
Generated code will use two registers and twice as many operations
compared to 64-bit integers, but that's standard for C compilers
working with integers wider than the registers.

It would not surprise me unduly if gcc supported 128-bit integers on
32-bit targets as well (after all, it happily supports 64-bit integers
on 8-bit targets), but I haven't checked.

gcc 4.7 does *not* support __int128 on 32-bit x86.

On a 64-bit system (I have "x86_64-w64-mingw32-gcc" version 4.5.3
under Cygwin), it does support __int128 -- but intmax_t is still
only 64 bits.

 

[Chad]

Another question here is do you have to use C? You might be better off

using a language like Python that handles arbitrary precision integers

directly (probably using GMP behind the scenes).

What about Haskell?

 

[James Kuyper]

On 10/24/2012 03:01 AM, David Brown wrote:
....

I noticed that (on gcc 4.5 on Linux-64). There is also no int128_t or
related types in <stdint.h>. And there is no way to express an int128_t
literal for targets that whose "long long" is smaller than 128 bits. On
x86-64, "long long" is 64-bit (with "long" being 32-bit on Windows,
64-bit on Linux), so until "long long long int" or "really long int" is
added to C, the language is missing a bit of support for 128-bit integers.

There's no need for that - that's what int128_t, int_least128_t and
int_fast128_t are reserved for. The language isn't missing anything,
it's just that particular implementation which has failed to implement
something which is already part of the language.

 

[Noob]

I noticed that (on gcc 4.5 on Linux-64). There is also no int128_t
or related types in <stdint.h>. And there is no way to express an
int128_t literal for targets whose "long long" is smaller than 128
bits. On x86-64, "long long" is 64-bit (with "long" being 32-bit on
Windows, 64-bit on Linux), so until "long long long int" or "really
long int" is added to C, the language is missing a bit of support for
128-bit integers.

I was under the impression that there existed an obscure GCC-specific
syntax to define 128-bit integer types:

typedef unsigned int myUI64 __attribute__((mode(TI)));

http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html

mode(foo)
This attribute specifies the data type for the declaration,
whichever type corresponds to the mode foo. This in effect
lets you request an integer or floating point type according
to its width.

Not sure what one can then do with an object of type myUI64.
(add? sub? shift? mul? div?)
And perhaps this has been obsolete for a long time?

cf. also
http://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html
http://stackoverflow.com/questions/4559025/what-does-gcc-attribute-modexx-actually-do

On a somewhat related note, cf. also:
http://locklessinc.com/articles/256bit_arithmetic/

Regards.

 

[Ben Bacarisse]

Yes, these type names are suitable for that purpose (though I am not
sure they are reserved for it by C99) - and it is the implementation
here that has failed to include them in <stdint.h> (I am not sure
whether this is the responsibility of the compiler or the library).

I commented on this a couple of days ago. I image the fact that
__int128 is in the compiler but int128_t is not it stdint.h is simply
the desire to keep the number of versions of stdint.h to a minimum.
Since C99 requires at least a 64-but int, limiting yourself to that
length keeps stdint.h very simple. However, I don't think gcc has the
mechanisms in place to make intmax_t be the 128-bit type (see below) and
that may be the real reason stdint.h stop st 64-bit types.

(A further reason might be simply that if you provide int128_t intmax_t
must be this type and all pre-processor arithmetic must be done using
it -- or at least *as if* it were being used.)

However, it is possible to express a 32-bit zero as "0", and a 64-bit
("long long") zero as "0LL". But there is no way to write a literal
128-bit zero, without extending C to allow "0LLL".

The "int128_t" and related types are enough to do most 128-bit integer
work in C. But there are unfortunately a number of places where the C
language and library specifications are tied to the poorly-defined
"int", "short", "long", "long long" types rather than size-specific
types.

But an implementation that has a 128-bit int can provide some
system-specific suffix (or, indeed, some other syntax) and stdint.h can
hide it to make the code portable. If your program needs a 128-bit
integer, you should be able to use int_least128_t and write constants
using INT128_C(value). gcc has provided __int128 but there is no
extension to write 128-bit constants yet. This may be the another
reason that stdint.h stops where it does.

This includes the suffixes on literals, and the format
specifiers in printf() (the "PRId32" style macros help enormously, but
they are not exactly elegant - and since they expand to specifiers for
short, int, long or long long, they can't support 128-bit integers).

I don't think that true. PRId128 could expand to some reserved but
currently unused length specifier. I don't think these macros are
limited to the specifiers for the standard integer types.