|
|
 | | From: | adrin | | Subject: | big integers | | Date: | Mon, 17 Jan 2005 20:40:01 +0100 |
|
|
 | 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*
|
|
| | From: | David Fisher | | Subject: | Re: big integers | | Date: | Tue, 18 Jan 2005 11:51:02 +1100 |
|
|
| Adrin wrote:
> I have to write a simple class to represent big integer numbers and
> implement basic arithmetical operations such as + - * / modulo, etc.
There are some existing libraries to do this in C++, if that's any help:
* http://www.csd.uwo.ca/~jamie/BitVectors/BIGNUMS.TXT
* http://www.swox.com/gmp/
*
http://www.cco.caltech.edu/cco/texinfo/libgplusplus/libgplusplus_toc.html#SEC40
(the Integer class)
Also try searching for "arbitrary precision" and "bignum" using
http://www.google.com ...
David Fisher
Sydney, Australia
|
|
| | From: | Bryan Hoover | | Subject: | Re: big integers | | Date: | Mon, 17 Jan 2005 21:23:52 -0500 |
|
|
| David Fisher wrote:
> Adrin wrote:
>
> > I have to write a simple class to represent big integer numbers and
> > implement basic arithmetical operations such as + - * / modulo, etc.
>
> There are some existing libraries to do this in C++, if that's any help:
I think he's doing this for a class. From the description he gave, he's on the
right track. I went through a computer science program, and this standard fare.
It's not all that difficult, but for a beginner, a student, it's a gratifying
challenge.
Bryan
> * http://www.csd.uwo.ca/~jamie/BitVectors/BIGNUMS.TXT
> * http://www.swox.com/gmp/
> *
> http://www.cco.caltech.edu/cco/texinfo/libgplusplus/libgplusplus_toc.html#SEC40
> (the Integer class)
>
> Also try searching for "arbitrary precision" and "bignum" using
> http://www.google.com ...
>
> David Fisher
> Sydney, Australia
|
|
| | From: | adrin | | Subject: | Re: big integers | | Date: | Tue, 18 Jan 2005 09:34:39 +0100 |
|
|
| Bryan Hoover wrote:
> I think he's doing this for a class. From the description he gave, he's
> on the
> right track. I went through a computer science program, and this standard
> fare. It's not all that difficult, but for a beginner, a student, it's a
> gratifying challenge.
yes you are right that's quite a challenge for me :)
in fact i just want some hints so that i could understand the basic idea
standing behind construction of big integer numbers
thanks for help,
--
*a*
|
|
| | From: | Michael Jørgensen | | Subject: | Re: big integers | | Date: | Tue, 18 Jan 2005 11:20:45 +0100 |
|
|
|
"adrin" wrote in message
news:csihmf$c45$1@opal.futuro.pl...
> Bryan Hoover wrote:
>
>
> > I think he's doing this for a class. From the description he gave, he's
> > on the
> > right track. I went through a computer science program, and this
standard
> > fare. It's not all that difficult, but for a beginner, a student, it's a
> > gratifying challenge.
>
> yes you are right that's quite a challenge for me :)
> in fact i just want some hints so that i could understand the basic idea
> standing behind construction of big integer numbers
Well, think about how you would do the calculation by hand, i.e. using
pencil and paper.
Multiplication is pretty straight-forward (but still challenging) if you use
that approach.
Division is more difficult. I would skip that at first, and get the other
stuff right first.
-Michael.
|
|
| | From: | David Fisher | | Subject: | Re: big integers | | Date: | Tue, 18 Jan 2005 14:25:22 +1100 |
|
|
| Adrin wrote:
>>> I have to write a simple class to represent big integer numbers and
>>> implement basic arithmetical operations such as + - * / modulo, etc.
I replied:
>> There are some existing libraries to do this in C++, if that's any help:
>> ...
Bryan wrote:
> I think he's doing this for a class. From the description he gave, he's
> on the
> right track. I went through a computer science program, and this standard
> fare.
> It's not all that difficult, but for a beginner, a student, it's a
> gratifying
> challenge.
Probably right ...
A couple of random thoughts:
* If you are converting to / from base 10 (eg. reading a 100 digit number),
then it might be easier to store numbers in base 100 (8 bits) or 10000 (32
bits) than in base 256 ...
* Storing the least significant part of the number at the lowest index in
the array might be easier than using the highest index. For example, if you
are using base 100, store 12345 as:
x[0] = 45
x[1] = 23
x[2] = 1
If you want to find x + y, where y = 981 ...
y[0] = 81
y[1] = 9
.... you can just add values with the same index, and keep track of the
"carry":
xy[0] = 45 + 81 = 126 = 26 carry 1
xy[1] = 23 + 9 + carry (1) = 33 carry 0
xy[2] = 1 + nothing for y + carry (0) = 1
So the result of 12345 + 981 is 13326
Hope this is helpful for you,
David Fisher
Sydney, Australia
|
|
| | From: | adrin | | Subject: | Re: big integers | | Date: | Tue, 18 Jan 2005 09:35:50 +0100 |
|
|
| David Fisher wrote:
> A couple of random thoughts:
>
> * If you are converting to / from base 10 (eg. reading a 100 digit
> number), then it might be easier to store numbers in base 100 (8 bits) or
> 10000 (32 bits) than in base 256 ...
> * Storing the least significant part of the number at the lowest index in
> the array might be easier than using the highest index. For example, if
> you are using base 100, store 12345 as:
>
> x[0] = 45
> x[1] = 23
> x[2] = 1
>
> If you want to find x + y, where y = 981 ...
>
> y[0] = 81
> y[1] = 9
>
> ... you can just add values with the same index, and keep track of the
> "carry":
>
> xy[0] = 45 + 81 = 126 = 26 carry 1
> xy[1] = 23 + 9 + carry (1) = 33 carry 0
> xy[2] = 1 + nothing for y + carry (0) = 1
>
> So the result of 12345 + 981 is 13326
>
> Hope this is helpful for you,
Yes it is, thanks for help.
i'll think about such implementation
--
*a*
|
|
|
