big integers

[adrin]

hello,

i have to write a simple class to represent big integer numbers and
implement basic arithmetical operations such as + - * / modulo, etc.
all will be written in c++ under linux OS on x86 architecture (however
that's not that important)

could you tell me what is an idea behind such construction?
i think about creating an dynamic array in which single digits in 255 base
will be stored(one byte). it is a common solution way when dealing with
BigIntegers isnt it?

adding would be implemented by adding digits, bit by bit, but how can i
solve the problem with a carry? maybe writing accessing carry flag using
asm code is a good solution? is there a better way?

and what about multiplication? is it made by adding the number repeatedly?

maybe you have a relevant tutorial or howto ?

 

[Alex Vinokur]

hello,

i have to write a simple class to represent big integer numbers and
implement basic arithmetical operations such as + - * / modulo, etc.
all will be written in c++ under linux OS on x86 architecture (however
that's not that important)

could you tell me what is an idea behind such construction?
i think about creating an dynamic array in which single digits in 255 base
will be stored(one byte). it is a common solution way when dealing with
BigIntegers isnt it?

adding would be implemented by adding digits, bit by bit, but how can i
solve the problem with a carry? maybe writing accessing carry flag using
asm code is a good solution? is there a better way?

and what about multiplication? is it made by adding the number repeatedly?

maybe you have a relevant tutorial or howto ?

[snip]

Look at C++ BigInt class at
http://groups-beta.google.com/group/alt.sources/browse_frm/thread/e578379447411268/0761372dd0c1490c

 

[Victor Bazarov]

i have to write a simple class to represent big integer numbers and
implement basic arithmetical operations such as + - * / modulo, etc.
all will be written in c++ under linux OS on x86 architecture (however
that's not that important)

could you tell me what is an idea behind such construction?

The idea is to store numbers that your architecture doesn't allow to
store using normal ways.

i think about creating an dynamic array in which single digits in 255 base
will be stored(one byte). it is a common solution way when dealing with
BigIntegers isnt it?

To know about what's common, you need to set the sampling parameters.

adding would be implemented by adding digits, bit by bit,

Why bit by bit? Couldn't you simply add two 255-base digits using normal
[unsigned] octet rules? Especially if your platform has 8-bit bytes, it
would be really simple, no?

but how can i
solve the problem with a carry?

You keep the carry flag and add it to the next pair. Just like any other
long addition/subtraction/multiplication/division...

maybe writing accessing carry flag using
asm code is a good solution? is there a better way?

You don't need asm to write C++. If I were your instructor, I would
fail you for using asm, actually.

and what about multiplication? is it made by adding the number repeatedly?

Well, sort of. For every multidigit numbers A and B you can define the
pairs of single-digit multiplications which need to be added to each other
later.

maybe you have a relevant tutorial or howto ?

www.google.com

And come back when you have a C++ language question.

V

 

[adrin]

http://groups-beta.google.com/group/alt.sources/browse_frm/thread/e578379447411268/0761372dd0c1490c

thank you very much ill study that code for sure

 

[adrin]

Why bit by bit? Couldn't you simply add two 255-base digits using normal
[unsigned] octet rules? Especially if your platform has 8-bit bytes, it
would be really simple, no?

maybe it'll sound stupid, but what do you mean by octet rules?


thanks for help,

 

[Victor Bazarov]

Why bit by bit? Couldn't you simply add two 255-base digits using normal
[unsigned] octet rules? Especially if your platform has 8-bit bytes, it
would be really simple, no?

maybe it'll sound stupid, but what do you mean by octet rules?

The rules your compiler is likely to follow.

Your compiler is likely to have a type for unsigned char that has 8 bits.
Those are octets. Add two together in an unsigned short or an unsigned
int, or multiply them, or whatever, and your compiler will happily do it
for you (using its own rules for those operations). If your compiler does
not support 8-bit bytes, you can still use the 8 bits out of your [larger]
char and perform those operations inside some larger types.

Perhaps I used the wrong word to state the obvious :-/

 

[Axel]

hello,

i have to write a simple class to represent big integer numbers and
implement basic arithmetical operations such as + - * / modulo, etc.
all will be written in c++ under linux OS on x86 architecture (however
that's not that important)

could you tell me what is an idea behind such construction?
i think about creating an dynamic array in which single digits in 255 base
will be stored(one byte). it is a common solution way when dealing with
BigIntegers isnt it?

adding would be implemented by adding digits, bit by bit, but how can i
solve the problem with a carry? maybe writing accessing carry flag using
asm code is a good solution? is there a better way?

and what about multiplication? is it made by adding the number repeatedly?

maybe you have a relevant tutorial or howto ?

Another advice: Use gmp
(http://www.swox.com/gmp/), which is a
big number library for c, coming along
with comfortable c++ wrapper classes
(i.e., overloaded operators etc.).

Answering your question whether
multiplication is done by adding numbers
repeatedly: for large numbers there are
much more clever ways of multiplication
(karatsuba and fft-based algorithms).
gmp also supports such fast arithmetic,
which is a good reason not do implement
things yourself - algorithms for fast
arithmetic are _very_ complicated to
implements.

 

[Victor Bazarov]

[...]
Answering your question whether multiplication is done by adding numbers
repeatedly: for large numbers there are much more clever ways of
multiplication (karatsuba and fft-based algorithms). gmp also supports
such fast arithmetic, which is a good reason not do implement things
yourself - algorithms for fast arithmetic are _very_ complicated to
implements.

Which may actually defeat the purpose. I think that the original query
was because of the homework. Nobody has to (or would) "write a simple
class" when there are industrial-strength libraries lying around on the
'Net *unless* that was the actual task: to implement things yourself.

V

 

[Flzw]

hello,

i have to write a simple class to represent big integer numbers and
implement basic arithmetical operations such as + - * / modulo, etc.
all will be written in c++ under linux OS on x86 architecture (however
that's not that important)

could you tell me what is an idea behind such construction?
i think about creating an dynamic array in which single digits in 255 base
will be stored(one byte). it is a common solution way when dealing with
BigIntegers isnt it?

adding would be implemented by adding digits, bit by bit, but how can i
solve the problem with a carry? maybe writing accessing carry flag using
asm code is a good solution? is there a better way?

and what about multiplication? is it made by adding the number repeatedly?

maybe you have a relevant tutorial or howto ?

A better way of doing so is to use the fact that every integer can be
decomposed in a factorial sum (don't know if that is the good english term)
meaning any integer can be written like this : x1*y1! + x2*y2! + x3*y3! +
.....xn*yn!

You can then "'easily" (depends on your maths skills actually) do addition,
multiplication can be a little trickier though