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.

[Igmar Palsenberg]

Re: Dealing with a large integer

[color=blue]
> 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.[/color]

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



Igmar

[gene.ressler@gmail.com]

Re: Dealing with a large integer

yong wrote:[color=blue]
> 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.[/color]

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[i];
for (i = 5; y >= 1; y--) {
y[i] = f % 900;
f /= 900;
}

[Suman]

Re: Dealing with a large integer

gene.ressler@gm ail.com wrote:
[...][color=blue]
> double f = ...[/color]
[ ... ][color=blue]
> y[i] = f % 900;[/color]

n869: 6.5.5 Multiplicative operators
[ ...]
Constraints
2 [...] The operands of the % operator shall have integer type.

[Keith Thompson]

Re: Dealing with a large integer

gene.ressler@gm ail.com writes:[color=blue]
> yong wrote:[color=green]
>> 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.[/color]
>
> 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.[/color]
[...]

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_Keit h) kst-u@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.

[James Dow Allen]

Re: Dealing with a large integer


yong wrote:[color=blue]
> I have an large integer ...
> How can I do this on my 32bit PC?[/color]

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

[Jordan Abel]

Re: Dealing with a large integer

On 2006-03-04, James Dow Allen <jdallen2000@ya hoo.com> wrote:[color=blue]
>
> yong wrote:[color=green]
>> I have an large integer ...
>> How can I do this on my 32bit PC?[/color]
>
> 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.[/color]

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.

[Richard Heathfield]

Re: Dealing with a large integer

James Dow Allen said:
[color=blue]
> 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.[/color]

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.
[color=blue]
> Note 2. Bill Gates was afriad to empower you by offering 'bc'?[/color]

Bill who?
[color=blue]
> Download Linux.[/color]

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)

[yong]

Re: Dealing with a large integer

James Dow Allen wrote:[color=blue]
> yong wrote:
>[color=green]
>>I have an large integer ...
>>How can I do this on my 32bit PC?[/color]
>
>
> 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
>[/color]

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

[Default User]

Re: Dealing with a large integer

yong wrote:

[color=blue]
> 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.[/color]

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

[websnarf@gmail.com]

Re: Dealing with a large integer

Default User wrote:[color=blue]
> yong wrote:[color=green]
> > 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.[/color]
>
> Actually, that is standard as of the latest standard. From the C99
> draft standard:[/color]

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@gmail.com]

Re: Dealing with a large integer

gene.ressler@gm ail.com wrote:[color=blue]
> yong wrote:[color=green]
> > 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.[/color]
>
> You can try to be fancy about modulo arithmetic and get it done with
> 32-bit integers,[/color]

I would actually endorse and recommend this method. Its the most
portable way to do it, and its just a little math.
[color=blue]
> [...] 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.[/color]

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.)
[color=blue]
> [...] 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;[/color]

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]

Re: Dealing with a large integer

"Default User" <defaultuserbr@ yahoo.com> writes:
[color=blue]
> yong wrote:
>
>[color=green]
> > 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.[/color]
>
> 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.[/color]

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]

Re: Dealing with a large integer

"James Dow Allen" <jdallen2000@ya hoo.com> writes:
[...]
<OT>[color=blue]
> Note 2. Bill Gates was afriad to empower you by offering 'bc'?
> Download Linux.[/color]

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

--
Keith Thompson (The_Other_Keit h) kst-u@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]

Re: Dealing with a large integer

websnarf@gmail. com writes:
[color=blue]
> gene.ressler@gm ail.com wrote:[color=green]
> > [...] 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.[/color]
>
> 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.)[/color]

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.