Dealing with a large integer

[yong]

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.

[websnarf]

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/

[websnarf]

ge**********@gm ail.com 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[i];
for (i = 5; y >= 1; y--) {
y[i] = f % 900;

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

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Micah Cowan]

"Default User" <de***********@ yahoo.com> 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

[Keith Thompson]

"James Dow Allen" <jd*********@ya hoo.com> 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_Keit h) ks***@mib.org <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.

[Micah Cowan]

we******@gmail. com writes:

ge**********@gm ail.com 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.

[Jordan Abel]

On 2006-03-04, Micah Cowan <mi***@cowan.na me> wrote:

"Default User" <de***********@ yahoo.com> 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.

[Keith Thompson]

we******@gmail. com 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_Keit h) ks***@mib.org <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]

we******@gmail. com writes:

ge**********@gm ail.com 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_Keit h) ks***@mib.org <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.

[CBFalconer]

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.c om, 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/googlegroupsrep ly/>

[CBFalconer]

Keith Thompson wrote:

"James Dow Allen" <jd*********@ya hoo.com> 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.c om, 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/googlegroupsrep ly/>