Dealing with a large integer

Discussion in 'C Programming' started by yong, Mar 3, 2006.

  1. yong

    yong Guest

    Hi all

    I have an large integer in this format
    x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
    now I must convert it to this format
    y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5

    x1-x5 is given.I must get y1-y4 from it.

    How can I do this on my 32bit PC?

    Sorry for that my English is poor.

    Thanks.
    yong, Mar 3, 2006
    #1
    1. Advertising


  2. > I have an large integer in this format
    > x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
    > now I must convert it to this format
    > y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5
    >
    > x1-x5 is given.I must get y1-y4 from it.
    >
    > How can I do this on my 32bit PC?
    >
    > Sorry for that my English is poor.


    Use a language that has big numbers support, or find yourself a library
    that does it for you.



    Igmar
    Igmar Palsenberg, Mar 3, 2006
    #2
    1. Advertising

  3. yong

    Guest

    yong wrote:
    > I have an large integer in this format
    > x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
    > now I must convert it to this format
    > y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5
    >
    > x1-x5 is given.I must get y1-y4 from it.
    >
    > How can I do this on my 32bit PC?
    >
    > Sorry for that my English is poor.


    You can try to be fancy about modulo arithmetic and get it done with
    32-bit integers, but since you are posting to comp.lang.c, your machine
    ought to implement "double." In IEEE floating point, doubles have a 52
    bit mantissa, which is big enough to hold both 256^6 and 900^5. So
    just compute

    double f = x[1];
    for (i = 2; i <= 6; i++)
    f = f * 256 + x;
    for (i = 5; y >= 1; y--) {
    y = f % 900;
    f /= 900;
    }
    , Mar 3, 2006
    #3
  4. yong

    Suman Guest

    wrote:
    [...]
    > double f = ...

    [ ... ]
    > y = f % 900;


    n869: 6.5.5 Multiplicative operators
    [ ...]
    Constraints
    2 [...] The operands of the % operator shall have integer type.
    Suman, Mar 3, 2006
    #4
  5. writes:
    > yong wrote:
    >> I have an large integer in this format
    >> x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
    >> now I must convert it to this format
    >> y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5
    >>
    >> x1-x5 is given.I must get y1-y4 from it.
    >>
    >> How can I do this on my 32bit PC?
    >>
    >> Sorry for that my English is poor.

    >
    > You can try to be fancy about modulo arithmetic and get it done with
    > 32-bit integers, but since you are posting to comp.lang.c, your machine
    > ought to implement "double." In IEEE floating point, doubles have a 52
    > bit mantissa, which is big enough to hold both 256^6 and 900^5.

    [...]

    Using double (or long double) to represent large integers can
    sometimes work, but it's dangerous. If any calculations exceed the
    range of values that can be represented exactly, the result silently
    loses precision.

    C99 requires 64-bit integers, and many C90 implementations provide
    them as well, even on 32-bit systems.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Mar 3, 2006
    #5
  6. yong wrote:
    > I have an large integer ...
    > How can I do this on my 32bit PC?


    Every Unix or Linux machine has a 'bc' command which
    is *very* convenient for *very* big numbers.

    To make this on-topic in comp.lang.c, let me mention that I sometimes
    write C programs to do calculations, in which, for example (Note 1)
    sprintf(c, "(%s)*(%s)", a, b); /* this is how we do c = a * b */

    Eventually the output of the C executable is sent to bc to get
    the numeric answers.

    Note 1. Some anally retentive c.l.c'ers will have to point that *they*
    could never do this because they're too unsure of themselves
    to allocate an adequate buffer for c.

    Note 2. Bill Gates was afriad to empower you by offering 'bc'?
    Download Linux.

    James D. Allen
    James Dow Allen, Mar 4, 2006
    #6
  7. yong

    Jordan Abel Guest

    On 2006-03-04, James Dow Allen <> wrote:
    >
    > yong wrote:
    >> I have an large integer ...
    >> How can I do this on my 32bit PC?

    >
    > Every Unix or Linux machine has a 'bc' command which
    > is *very* convenient for *very* big numbers.
    >
    > To make this on-topic in comp.lang.c, let me mention that I sometimes
    > write C programs to do calculations, in which, for example (Note 1)
    > sprintf(c, "(%s)*(%s)", a, b); /* this is how we do c = a * b */
    >
    > Eventually the output of the C executable is sent to bc to get
    > the numeric answers.
    >
    > Note 1. Some anally retentive c.l.c'ers will have to point that *they*
    > could never do this because they're too unsure of themselves
    > to allocate an adequate buffer for c.


    it is possible for a program to know how long the resulting string from
    a sprintf statement will be. if that was a dig at the recent gets
    debate, keep in mind it is NOT possible for a program to know how much
    the user will type.
    Jordan Abel, Mar 4, 2006
    #7
  8. James Dow Allen said:

    > To make this on-topic in comp.lang.c, let me mention that I sometimes
    > write C programs to do calculations, in which, for example (Note 1)
    > sprintf(c, "(%s)*(%s)", a, b); /* this is how we do c = a * b */
    >
    > Eventually the output of the C executable is sent to bc to get
    > the numeric answers.
    >
    > Note 1. Some anally retentive c.l.c'ers will have to point that *they*
    > could never do this because they're too unsure of themselves
    > to allocate an adequate buffer for c.


    Are you a qualified psychiatrist? If not, please refrain from using
    psychiatric terms as if you knew what you were talking about.

    It's trivial to allocate an adequate buffer for c. strlen(a) + strlen(b) + 6
    bytes are required in this case, and malloc can handle that easily enough.

    > Note 2. Bill Gates was afriad to empower you by offering 'bc'?


    Bill who?

    > Download Linux.


    I prefer CDs, but yes, the principle is sound.


    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Mar 4, 2006
    #8
  9. yong

    yong Guest

    James Dow Allen wrote:
    > yong wrote:
    >
    >>I have an large integer ...
    >>How can I do this on my 32bit PC?

    >
    >
    > Every Unix or Linux machine has a 'bc' command which
    > is *very* convenient for *very* big numbers.
    >
    > To make this on-topic in comp.lang.c, let me mention that I sometimes
    > write C programs to do calculations, in which, for example (Note 1)
    > sprintf(c, "(%s)*(%s)", a, b); /* this is how we do c = a * b */
    >
    > Eventually the output of the C executable is sent to bc to get
    > the numeric answers.
    >
    > Note 1. Some anally retentive c.l.c'ers will have to point that *they*
    > could never do this because they're too unsure of themselves
    > to allocate an adequate buffer for c.
    >
    > Note 2. Bill Gates was afriad to empower you by offering 'bc'?
    > Download Linux.
    >
    > James D. Allen
    >


    I'm using linux.And I found another variable type named uint64_t in
    stdint.h which represents a 64bit integer.It's seems not standard but
    very useful.

    Thanks all.



    --Yong
    yong, Mar 4, 2006
    #9
  10. yong

    Default User Guest

    yong wrote:


    > I'm using linux.And I found another variable type named uint64_t in
    > stdint.h which represents a 64bit integer.It's seems not standard but
    > very useful.


    Actually, that is standard as of the latest standard. From the C99
    draft standard:


    7.18.1.1 Exact-width integer types

    [#2] The typedef name uintN_t designates an unsigned integer
    type with width N. Thus, uint24_t denotes an unsigned
    integer type with a width of exactly 24 bits.


    An implementation is not required to provide them.


    Brian
    Default User, Mar 4, 2006
    #10
  11. yong

    Guest

    Default User wrote:
    > yong wrote:
    > > I'm using linux.And I found another variable type named uint64_t in
    > > stdint.h which represents a 64bit integer.It's seems not standard but
    > > very useful.

    >
    > Actually, that is standard as of the latest standard. From the C99
    > draft standard:


    Right, but gcc does not implement C99. So its existence is actually an
    extension to gcc (perhaps yong has some other compiler on Linux that
    actually does support C99.) Of course you can get this "extension" for
    many more compilers than just gcc from here:

    http://www.pobox.com/~qed/pstdint.h

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    , Mar 4, 2006
    #11
  12. yong

    Guest

    wrote:
    > yong wrote:
    > > I have an large integer in this format
    > > x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
    > > now I must convert it to this format
    > > y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5
    > >
    > > x1-x5 is given.I must get y1-y4 from it.
    > >
    > > How can I do this on my 32bit PC?
    > >
    > > Sorry for that my English is poor.

    >
    > You can try to be fancy about modulo arithmetic and get it done with
    > 32-bit integers,


    I would actually endorse and recommend this method. Its the most
    portable way to do it, and its just a little math.

    > [...] but since you are posting to comp.lang.c, your machine
    > ought to implement "double." In IEEE floating point, doubles have a 52
    > bit mantissa, which is big enough to hold both 256^6 and 900^5.


    Uhhh ... does ANSI C insist that double have sufficient range for
    numbers of this size? Turbo C implements double's as 32-bit floats
    (but Turbo C is not a fully compliant ANSI C compiler so that might not
    prove anything.)

    > [...] So just compute
    >
    > double f = x[1];
    > for (i = 2; i <= 6; i++)
    > f = f * 256 + x;
    > for (i = 5; y >= 1; y--) {
    > y = f % 900;


    This is illegal, you should use the modf() function instead: y =
    900 * modf (f / 900, &f);

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    , Mar 4, 2006
    #12
  13. yong

    Micah Cowan Guest

    "Default User" <> writes:

    > yong wrote:
    >
    >
    > > I'm using linux.And I found another variable type named uint64_t in
    > > stdint.h which represents a 64bit integer.It's seems not standard but
    > > very useful.

    >
    > Actually, that is standard as of the latest standard. From the C99
    > draft standard:
    >
    >
    > 7.18.1.1 Exact-width integer types
    >
    > [#2] The typedef name uintN_t designates an unsigned integer
    > type with width N. Thus, uint24_t denotes an unsigned
    > integer type with a width of exactly 24 bits.
    >
    >
    > An implementation is not required to provide them.


    It /is/ required to provide them for widths of 8, 16, 32 or 64 bits, if:

    - it is a C99 implementation, and
    - it is actually capable of providing them.

    -Micah
    Micah Cowan, Mar 4, 2006
    #13
  14. "James Dow Allen" <> writes:
    [...]
    <OT>
    > Note 2. Bill Gates was afriad to empower you by offering 'bc'?
    > Download Linux.


    I have "bc" on my Windows systems, under Cygwin.
    </OT>

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Mar 4, 2006
    #14
  15. yong

    Micah Cowan Guest

    writes:

    > wrote:
    > > [...] but since you are posting to comp.lang.c, your machine
    > > ought to implement "double." In IEEE floating point, doubles have a 52
    > > bit mantissa, which is big enough to hold both 256^6 and 900^5.

    >
    > Uhhh ... does ANSI C insist that double have sufficient range for
    > numbers of this size? Turbo C implements double's as 32-bit floats
    > (but Turbo C is not a fully compliant ANSI C compiler so that might not
    > prove anything.)


    It only insists that IEEE floating point is used if __STDC_IEC_559__
    is defined. I don't have the standard, but wikipedia seems to bear
    these figures out in this case.

    If IEEE floating point is not available (improbable), it's still
    guaranteed that a double can hold 10 decimal digits, which means that
    it is big enough to hold (10^10)-1. This only means it's enough to
    hold 4 complete base-256 digits, or 3 base-900 digits, which is not
    enough for the specified needs.
    Micah Cowan, Mar 4, 2006
    #15
  16. yong

    Jordan Abel Guest

    On 2006-03-04, Micah Cowan <> wrote:
    > "Default User" <> writes:
    >
    >> yong wrote:
    >>
    >>
    >> > I'm using linux.And I found another variable type named uint64_t in
    >> > stdint.h which represents a 64bit integer.It's seems not standard but
    >> > very useful.

    >>
    >> Actually, that is standard as of the latest standard. From the C99
    >> draft standard:
    >>
    >>
    >> 7.18.1.1 Exact-width integer types
    >>
    >> [#2] The typedef name uintN_t designates an unsigned integer
    >> type with width N. Thus, uint24_t denotes an unsigned
    >> integer type with a width of exactly 24 bits.
    >>
    >>
    >> An implementation is not required to provide them.

    >
    > It /is/ required to provide them for widths of 8, 16, 32 or 64 bits, if:
    >
    > - it is a C99 implementation, and
    > - it is actually capable of providing them.
    >
    > -Micah


    I was trying to think of a way that an implementation could prove that
    an implementation is capable of providing them if it doesn't, but i just
    thought of one:

    #include <limits.h>
    #include <inttypes.h>

    int main() {
    #ifndef INT16_MAX
    #if CHAR_BIT == 16 && SCHAR_MAX == 32767 && SCHAR_MIN == -32768
    signed char x;
    *(unsigned char *)&x = 0x80;
    if(x == SCHAR_MIN) puts("bad");
    #elif CHAR_BIT == 8 && SHRT_MAX == 32767 && SHRT_MIN == -32768
    if(sizeof(short) == 2) {
    *(unsigned short *)&x = 0x8000;
    if(x == SHRT_MIN) puts("bad");
    }
    #endif
    #endif/*no int16_t*/
    }

    On any conforming implementation, i believe the above program will have
    no output.
    Jordan Abel, Mar 4, 2006
    #16
  17. writes:
    > Default User wrote:
    >> yong wrote:
    >> > I'm using linux.And I found another variable type named uint64_t in
    >> > stdint.h which represents a 64bit integer.It's seems not standard but
    >> > very useful.

    >>
    >> Actually, that is standard as of the latest standard. From the C99
    >> draft standard:

    >
    > Right, but gcc does not implement C99. So its existence is actually an
    > extension to gcc (perhaps yong has some other compiler on Linux that
    > actually does support C99.)


    gcc doesn't *fully* support C99 (see <http://gcc.gnu.org/c99status.html>
    for details), but it does support some C99 features. But <stdint.h>,
    the header that defines uint64_t, is part of the library, not the
    compiler. gcc uses whatever library is provided by the system. On
    Linux, that's glibc, which does support <stdint.h>; on other systems,
    it's likely going to depend on the operating system.

    > Of course you can get this "extension" for
    > many more compilers than just gcc from here:
    >
    > http://www.pobox.com/~qed/pstdint.h


    Or here:

    http://www.lysator.liu.se/c/q8/

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Mar 4, 2006
    #17
  18. writes:
    > wrote:
    >> yong wrote:
    >> > I have an large integer in this format
    >> > x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
    >> > now I must convert it to this format
    >> > y1*900^4 + y2*900^3 + y3*900^2 + y4*900 + y5
    >> >
    >> > x1-x5 is given.I must get y1-y4 from it.
    >> >
    >> > How can I do this on my 32bit PC?
    >> >
    >> > Sorry for that my English is poor.

    >>
    >> You can try to be fancy about modulo arithmetic and get it done with
    >> 32-bit integers,

    >
    > I would actually endorse and recommend this method. Its the most
    > portable way to do it, and its just a little math.
    >
    >> [...] but since you are posting to comp.lang.c, your machine
    >> ought to implement "double." In IEEE floating point, doubles have a 52
    >> bit mantissa, which is big enough to hold both 256^6 and 900^5.

    >
    > Uhhh ... does ANSI C insist that double have sufficient range for
    > numbers of this size? Turbo C implements double's as 32-bit floats
    > (but Turbo C is not a fully compliant ANSI C compiler so that might not
    > prove anything.)


    The standard requires
    FLT_DIG >= 6
    DBL_DIG >= 10
    LDBL_DIG >= 10
    I don't think a 32-bit float would satisfy the requirement for DBL_DIG.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Mar 4, 2006
    #18
  19. yong

    CBFalconer Guest

    Default User wrote:
    > yong wrote:
    >
    >> I'm using linux.And I found another variable type named uint64_t
    >> in stdint.h which represents a 64bit integer.It's seems not
    >> standard but very useful.

    >
    > Actually, that is standard as of the latest standard. From the C99
    > draft standard:
    >
    > 7.18.1.1 Exact-width integer types
    >
    > [#2] The typedef name uintN_t designates an unsigned integer
    > type with width N. Thus, uint24_t denotes an unsigned
    > integer type with a width of exactly 24 bits.
    >
    > An implementation is not required to provide them.


    Actually, under C99, if the underlying hardware has such objects
    the implementation must then support them. Otherwise they can be
    omitted. #ifdef may be handy.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
    More details at: <http://cfaj.freeshell.org/google/>
    Also see <http://www.safalra.com/special/googlegroupsreply/>
    CBFalconer, Mar 5, 2006
    #19
  20. yong

    CBFalconer Guest

    Keith Thompson wrote:
    > "James Dow Allen" <> writes:
    > [...]
    > <OT>
    >> Note 2. Bill Gates was afriad to empower you by offering 'bc'?
    >> Download Linux.

    >
    > I have "bc" on my Windows systems, under Cygwin.


    under DJGPP here.
    +
    > </OT>


    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
    More details at: <http://cfaj.freeshell.org/google/>
    Also see <http://www.safalra.com/special/googlegroupsreply/>
    CBFalconer, Mar 5, 2006
    #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. Slain
    Replies:
    2
    Views:
    286
    Alf P. Steinbach
    Jul 12, 2007
  2. brzak
    Replies:
    5
    Views:
    1,522
    Boogie
    Dec 1, 2008
  3. Replies:
    1
    Views:
    341
    Martin v. Löwis
    Jan 22, 2009
  4. elitemx

    Dealing with ctype.h integer overflow

    elitemx, Jun 28, 2010, in forum: C Programming
    Replies:
    0
    Views:
    316
    elitemx
    Jun 28, 2010
  5. Saqib Ali
    Replies:
    2
    Views:
    202
    Saqib Ali
    Jan 14, 2011
Loading...

Share This Page