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.

[yong]

I rewrite my code but the uint64_t seems can't work well.

The code is here:
=============== =========
#include <stdio.h>
#include <stdint.h>
#include "compress.h "

int main()
{
struct code6 mycode6;
struct code5 mycode5;

mycode6.item1=1 ;
mycode6.item2=2 ;
mycode6.item3=3 ;
mycode6.item4=4 ;
mycode6.item5=5 ;
mycode6.item6=6 ;

mycode5=codecom press(mycode6);

printf("mycode5 .item1 is: %d\n",mycode5.i tem1);
printf("mycode5 .item2 is: %d\n",mycode5.i tem2);
printf("mycode5 .item3 is: %d\n",mycode5.i tem3);
printf("mycode5 .item4 is: %d\n",mycode5.i tem4);
printf("mycode5 .item5 is: %d\n",mycode5.i tem5);

return 0;
}
=============== =========

and the compress.h is here:

=============== =========
#include <stdint.h>

struct code6
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
unsigned long item6;
};

struct code5
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
};

struct code5 codecompress(st ruct code6 origcode)
{
struct code5 ret;
uint64_t math64;

math64=origcode .item1*(256^5)+ origcode.item2* (256^4)+origcod e.item3*(256^3) +origcode.item4 *(256^2)+origco de.item5*256+or igcode.item6;
printf("math64 is: %X\n",math64);

ret.item5=(math 64)%(uint64_t)9 00;
math64/=900;
ret.item4=(math 64)%900;
math64/=900;
ret.item3=(math 64)%900;
math64/=900;
ret.item2=(math 64)%900;
math64/=900;
ret.item1=(math 64)%900;

return ret;
}

=============== =========

After the code runs it displays that

------------------------
math64 is: F24
mycode5.item1 is: 0
mycode5.item2 is: 0
mycode5.item3 is: 0
mycode5.item4 is: 4
mycode5.item5 is: 276
------------------------

That's incorret.Is there something wrong with my code?

Thanks.

[Walter Roberson]

In article <du**********@n ews.yaako.com>,
yong <lu********@eno rth.com.cn> wrote:

I rewrite my code but the uint64_t seems can't work well.
Unfortunately you did not quote any of the original task.

The code is here: math64=origcode .item1*(256^5)+ origcode.item2* (256^4)+origcod e.item3*(256^3) +origcode.item4 *(256^2)+origco de.item5*256+or igcode.item6;

In C, the ^ operator is "Exclusive OR". In your description of
the original task, I would be surprised if your use of ^
did not indicate exponentiation there.

In C, 256 to the power
of 0 is 1
of 1 is 1<<8
of 2 is 1<<16
of 3 is 1<<24
of 4 is 1<<32
of 5 is 1<<40

On most systems, 1<<32 is bigger than an unsigned long will hold.
C89 does not promise that anything from 1<<32 upwards is available.
C99 does provide unsigned long long for that purpose, but you
must be careful to avoid accidently working in narrower types
in an intermediate stage.

You do not actually need to use the multiplications or additions
in your calculation of math64. Presuming C99, your code could instead be

math64 = (unsigned long long) origcode.item1 << 40 |
(unsigned long long) origcode.item2 << 32 |
(unsigned long long) origcode.item3 << 24 |
(unsigned long long) origcode.item4 << 16 |
(unsigned long long) origcode.item5 << 8 |
(unsigned long long) origcode.item6;

--
"law -- it's a commodity"
-- Andrew Ryan (The Globe and Mail, 2005/11/26)

[yong]

Walter Roberson wrote:

In article <du**********@n ews.yaako.com>,
yong <lu********@eno rth.com.cn> wrote:

I rewrite my code but the uint64_t seems can't work well.

Unfortunately you did not quote any of the original task.

The code is here:

math64=origcode .item1*(256^5)+ origcode.item2* (256^4)+origcod e.item3*(256^3) +origcode.item4 *(256^2)+origco de.item5*256+or igcode.item6;

In C, the ^ operator is "Exclusive OR". In your description of
the original task, I would be surprised if your use of ^
did not indicate exponentiation there.

In C, 256 to the power
of 0 is 1
of 1 is 1<<8
of 2 is 1<<16
of 3 is 1<<24
of 4 is 1<<32
of 5 is 1<<40

On most systems, 1<<32 is bigger than an unsigned long will hold.
C89 does not promise that anything from 1<<32 upwards is available.
C99 does provide unsigned long long for that purpose, but you
must be careful to avoid accidently working in narrower types
in an intermediate stage.

You do not actually need to use the multiplications or additions
in your calculation of math64. Presuming C99, your code could instead be

math64 = (unsigned long long) origcode.item1 << 40 |
(unsigned long long) origcode.item2 << 32 |
(unsigned long long) origcode.item3 << 24 |
(unsigned long long) origcode.item4 << 16 |
(unsigned long long) origcode.item5 << 8 |
(unsigned long long) origcode.item6;

I rewrite my code and it seems run correctly now.

main.c
=============== ====
#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include "compress.h "

int main()
{
struct code6 mycode6;
struct code5 mycode5;

mycode6.item1=1 ;
mycode6.item2=2 ;
mycode6.item3=3 ;
mycode6.item4=4 ;
mycode6.item5=5 ;
mycode6.item6=6 ;

mycode5=codecom press(mycode6);

printf("mycode5 .item1 is: %d\n",mycode5.i tem1);
printf("mycode5 .item2 is: %d\n",mycode5.i tem2);
printf("mycode5 .item3 is: %d\n",mycode5.i tem3);
printf("mycode5 .item4 is: %d\n",mycode5.i tem4);
printf("mycode5 .item5 is: %d\n",mycode5.i tem5);

return 0;
}
=============== ====

compress.h
=============== ====
#include <stdint.h>

struct code6
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
unsigned long item6;
};

struct code5
{
unsigned long item1;
unsigned long item2;
unsigned long item3;
unsigned long item4;
unsigned long item5;
};

struct code5 codecompress(st ruct code6 origcode)
{
struct code5 ret;
uint64_t math64;

math64=origcode .item1*((uint64 _t)pow(256,5))+ origcode.item2* ((uint64_t)pow( 256,4))+origcod e.item3*((uint6 4_t)pow(256,3)) +origcode.item4 *((uint64_t)pow (256,2))+origco de.item5*256+or igcode.item6;

ret.item5=(math 64)%(uint64_t)9 00;
math64/=900;
ret.item4=(math 64)%900;
math64/=900;
ret.item3=(math 64)%900;
math64/=900;
ret.item2=(math 64)%900;
math64/=900;
ret.item1=(math 64)%900;

return ret;
}
=============== ====
Thank you all. :]

--
My Personal Weblog:
http://spaces.msn.com/cyberisblue

[ena8t8si]

CBFalconer wrote:

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.

If you read the relevant paragraph in the standard,
you'll see that it doesn't say anything about the
underlying hardware. It's perfectly legal for an
implementation to have 8 bit chars, 16 bit shorts,
and 64 bit ints, longs and long longs, and not define
int32_t, regardless of what hardware it's running on.

[Jordan Abel]

On 2006-03-05, en******@yahoo. com <en******@yahoo .com> wrote:

CBFalconer wrote:

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.

If you read the relevant paragraph in the standard,
you'll see that it doesn't say anything about the
underlying hardware. It's perfectly legal for an
implementation to have 8 bit chars, 16 bit shorts,
and 64 bit ints, longs and long longs, and not define
int32_t, regardless of what hardware it's running on.

I think his claim is that the types have to be available if the relevant
standard types are twos-complement and have no padding. I don't know if
that's true or not. "hardware" is just a shorthand for "whatever the
'native' types are implemented on."

*wonders why int24_t isn't required if there is a type with 24 bits, no
padding bits, and twos complement representation*

[Me]

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

It looks like you're trying to convert a base-256 number to a base-900
number (i.e. all the the xN's are in the range [0, 255]). If this is
the case, then you can do this:

unsigned long long x = x1;
x = x<<8 | x2;
x = x<<8 | x3;
x = x<<8 | x4;
x = x<<8 | x5;

And then to get y1..y5:

y5 = x % 900; x /= 900;
y4 = x % 900; x /= 900;
y3 = x % 900; x /= 900;
y2 = x % 900; x /= 900;
y1 = x;

[russell kym horsell]

yong <yo************ ****@gmail.com> wrote:

Hi all
I have an large integer in this format [lemm call this X:] x1*256^5 + x2*256^4 + x3*256^3 + x4*256^2 + x5*256 + x6
now I must convert it to this format [Y:] 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.

Some kind of pdf encoder, eh?
There's probably a lot of literature on smart tricks, but
the basic idea (beside simply using 64-bit integers and brute force --
BTW even 32-bit PC's can do h/w 64-bit arith these days) is to note that

X % 900 = Y % 900 = y4.

Then we see that
256^5 % 900 = 376
256^4 % 900 = 796
256^3 % 900 = 316
256^2 % 900 = 736
256^1 % 900 = 256

So we must have y4 = (376*x1 + 796*x2 + 316*x3 + 736*x4 + 256*x5 + x6) % 900 .
(Look, maw, only 16-bit arithmetic!)

Similiarly for the other y_i.

[James Dow Allen]

Jordan Abel wrote:

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.

Sigh. It sounds like we need to beat the dead horse one more time.

The gets() which I defended gots'ed a string which my own software
had printf'ed. Got it?

James

[Jordan Abel]

On 2006-03-06, James Dow Allen <jd*********@ya hoo.com> wrote:

Jordan Abel wrote:

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.

Sigh. It sounds like we need to beat the dead horse one more time.

The gets() which I defended gots'ed a string which my own software
had printf'ed. Got it?

How did you guarantee this? There is no mechanism in the standard to
ensure that this happens. If gets is removed from the standard, systems
which _do_ provide such a mechanism may provide gets as an extension.

[ena8t8si]

Jordan Abel wrote:

On 2006-03-05, en******@yahoo. com <en******@yahoo .com> wrote:

CBFalconer wrote:

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.

If you read the relevant paragraph in the standard,
you'll see that it doesn't say anything about the
underlying hardware. It's perfectly legal for an
implementation to have 8 bit chars, 16 bit shorts,
and 64 bit ints, longs and long longs, and not define
int32_t, regardless of what hardware it's running on.

I think his claim is that the types have to be available if the relevant
standard types are twos-complement and have no padding. I don't know if
that's true or not. "hardware" is just a shorthand for "whatever the
'native' types are implemented on."

If that's the claim that was intended then someone needs
a lesson in writing for clarity.

I find it more likely that your reading is simply overly
charitable. There was no mention, for example, of twos
complement in the original message.