Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > big integers

Reply
Thread Tools

big integers

 
 
adrin
Guest
Posts: n/a
 
      01-17-2005
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*
 
Reply With Quote
 
 
 
 
Alex Vinokur
Guest
Posts: n/a
 
      01-17-2005

"adrin" <(E-Mail Removed)> wrote in message news:csh4av$ofh$(E-Mail Removed)...
> 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/...61372dd0c1490c

--
Alex Vinokur
email: alex DOT vinokur AT gmail DOT com
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn




 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      01-17-2005
adrin wrote:
> 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
 
Reply With Quote
 
adrin
Guest
Posts: n/a
 
      01-17-2005
Alex Vinokur wrote:

>

http://groups-beta.google.com/group/...61372dd0c1490c
>


thank you very much ill study that code for sure

--
*a*
 
Reply With Quote
 
adrin
Guest
Posts: n/a
 
      01-17-2005
Victor Bazarov <(E-Mail Removed)> wrote in
news:SHUGd.36146$(E-Mail Removed)01.us.t o.verio.net:

> 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,
--
*a*
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      01-17-2005
adrin wrote:
> Victor Bazarov <(E-Mail Removed)> wrote in
> news:SHUGd.36146$(E-Mail Removed)01.us.t o.verio.net:
>
>
>>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 :-/
 
Reply With Quote
 
Axel
Guest
Posts: n/a
 
      01-18-2005
adrin wrote:
> 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.


 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      01-18-2005
Axel wrote:
> [...]
> 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
 
Reply With Quote
 
Flzw
Guest
Posts: n/a
 
      01-18-2005

"adrin" <(E-Mail Removed)> wrote in message
news:csh4av$ofh$(E-Mail Removed)...
> 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net 0 12-26-2008 09:29 AM
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net Web Controls 0 12-26-2008 06:11 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Python 0 12-24-2008 07:35 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Ruby 0 12-24-2008 05:07 AM
Too big integers hobbs C Programming 39 12-31-2003 03:54 PM



Advertisments