Large number libraries/algorithms

Discussion in 'C Programming' started by boltar2003@boltar.world, Oct 22, 2012.

  1. Guest

    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
    , Oct 22, 2012
    #1
    1. Advertising

  2. Mark Bluemel Guest

    On 22/10/2012 10:11, wrote:
    > 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.
    Mark Bluemel, Oct 22, 2012
    #2
    1. Advertising

  3. On 2012-10-22, <> wrote:
    > 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


    --
    Heikki Kallasjoki
    Heikki Kallasjoki, Oct 22, 2012
    #3
  4. Noob Guest

    boltar2003 wrote:
    > 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.
    Noob, Oct 22, 2012
    #4
  5. Guest

    On Mon, 22 Oct 2012 09:19:52 GMT
    Heikki Kallasjoki <> wrote:
    >On 2012-10-22, <> wrote:
    >> 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


    Thanks, thats just what I need.

    B2003
    , Oct 22, 2012
    #5
  6. Guest

    On Mon, 22 Oct 2012 13:29:51 +0200
    David Brown <> wrote:
    >On 22/10/2012 11:11, wrote:
    >> 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
    >>

    >
    >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
    , Oct 22, 2012
    #6
  7. James Kuyper Guest

    On 10/22/2012 07:53 AM, wrote:
    > On Mon, 22 Oct 2012 13:29:51 +0200
    > David Brown <> wrote:

    ....
    >> 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?


    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.
    --
    James Kuyper
    James Kuyper, Oct 22, 2012
    #7
  8. Eric Sosman Guest

    On 10/22/2012 5:11 AM, wrote:
    > 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/>.

    --
    Eric Sosman
    d
    Eric Sosman, Oct 22, 2012
    #8
  9. James Kuyper Guest

    On 10/22/2012 08:41 AM, David Brown wrote:
    > 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.
    --
    James Kuyper
    James Kuyper, Oct 22, 2012
    #9
  10. James Kuyper <> writes:

    > On 10/22/2012 08:41 AM, David Brown wrote:
    >> 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.

    > I'm not sure how common those are - but I'd expect them
    > to be rare.


    --
    Ben.
    Ben Bacarisse, Oct 22, 2012
    #10
  11. David Brown <> writes:
    > On 22/10/2012 11:11, wrote:
    >> 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

    >
    > 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?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Will write code for food.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 22, 2012
    #11
  12. tom st denis Guest

    On Oct 22, 8:23 am, Eric Sosman <>
    wrote:
    > On 10/22/2012 5:11 AM, wrote:
    >
    > > 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/>.


    Someone really needs to update that response...

    Tom
    tom st denis, Oct 22, 2012
    #12
  13. Robert Wessel <> writes:

    > On Mon, 22 Oct 2012 10:31:54 -0700, Keith Thompson <>
    > wrote:
    >
    >>David Brown <> writes:
    >>> On 22/10/2012 11:11, wrote:
    >>>> 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
    >>>
    >>> 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?

    >
    >
    > 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.

    --
    Ben.
    Ben Bacarisse, Oct 23, 2012
    #13
  14. tom st denis <> writes:
    > On Oct 22, 8:23 am, Eric Sosman <>
    > wrote:
    >> On 10/22/2012 5:11 AM, wrote:
    >>
    >> > 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/>.

    >
    > 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.)

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Will write code for food.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 23, 2012
    #14
  15. tom st denis Guest

    On Oct 22, 8:05 pm, Keith Thompson <> wrote:
    > tom st denis <> writes:
    >
    > > On Oct 22, 8:23 am, Eric Sosman <>
    > > wrote:
    > >> On 10/22/2012 5:11 AM, wrote:

    >
    > >> > 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/>.

    >
    > > 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.)


    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
    tom st denis, Oct 23, 2012
    #15
  16. David Brown <> writes:
    > On 23/10/2012 01:01, Ben Bacarisse wrote:
    >> Robert Wessel <> writes:
    >>> On Mon, 22 Oct 2012 10:31:54 -0700, Keith Thompson <>
    >>> wrote:

    [...]
    >>>> 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.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Will write code for food.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 23, 2012
    #16
  17. Chad Guest

    On Monday, October 22, 2012 5:47:31 AM UTC-7, David Brown wrote:
    > On 22/10/2012 11:11, wrote:
    >
    > > 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

    >
    > >

    >
    >
    >
    >
    >
    > 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?
    Chad, Oct 23, 2012
    #17
  18. James Kuyper Guest

    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.
    --
    James Kuyper
    James Kuyper, Oct 24, 2012
    #18
  19. Noob Guest

    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 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.
    Noob, Oct 24, 2012
    #19
  20. David Brown <> writes:

    > On 24/10/2012 13:18, James Kuyper wrote:
    >> 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.
    >>

    >
    > 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.

    > On the other hand, I don't see how this would limit practical 128-bit
    > usage much. After all, how often do you need to write 128-bit
    > literals, or printf them out?
    >


    --
    Ben.
    Ben Bacarisse, Oct 24, 2012
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Karsten Wutzke
    Replies:
    21
    Views:
    901
    Roedy Green
    Jun 29, 2007
  2. eliben
    Replies:
    3
    Views:
    571
    Mensanator
    Feb 18, 2009
  3. Sriram Srinivasan
    Replies:
    13
    Views:
    548
    Benjamin Kaplan
    Nov 12, 2009
  4. Ketchup
    Replies:
    1
    Views:
    233
    Jan Tielens
    May 25, 2004
  5. Replies:
    5
    Views:
    850
    Xho Jingleheimerschmidt
    Apr 2, 2009
Loading...

Share This Page