very large integers

[bob]

If you were designing a class to represent very large integers in C++,
what kind of internal representation would be best?

[Alf P. Steinbach]

* bo*@coolgroups. com:

If you were designing a class to represent very large integers in C++,
what kind of internal representation would be best?

Depends. But if you're wondering about that you're probably best off
using one of the existing, free large integer libraries.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Phlip]

bob wrote:

If you were designing a class to represent very large integers in C++,
what kind of internal representation would be best?

vector<int>?

Ooh, I can use http://www.google.com/codesearch for this one!

Searching for "bigint lang:c++ vector.int", without the quotes, I get this:

http://www.cs.hmc.edu/courses/mostRe...k/cs70ass2.tgz

class BigInt {
...
vector<intchunk s_; // Value of the BigInt.

So it looks like they used the vector, like I suggested, as a "counting"
algorithm, treating each int as a symbol, in base 2-billion.

Question: Is this optimal, per vector's guarantees on the speed of
traversal, vs speed pushing back and such? Would a std::list perform better
or worse?

--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!

[Pete Becker]

Phlip wrote:

bob wrote:

>If you were designing a class to represent very large integers in C++,
what kind of internal representation would be best?

vector<int>?

vector<unsigned is far better. Writing semi-numeric algorithms with
signed types produces major headaches. Just ask anyone who's implemented
big integers in Java.

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.

[Kai-Uwe Bux]

Phlip wrote:

bob wrote:

>If you were designing a class to represent very large integers in C++,
what kind of internal representation would be best?

vector<int>?

For a generic implementation, I would prefer vector< unsigned long or more
generally vector<Twhere T is the largest unsigned arithmetic type for
which you have fast arithmetic. I would prefer unsigned types if two
conditions are met: (a) they wrap around on overflow and (b) they use
two-complement representation.

If speed is of the utmost importance (and in this business, it usually is) I
would have a look at what types are best supported on the machine level and
supply some assembler routines for the core functions of the class. That
would then determine most of the internal representation.

Most important: I would use a library instead of thinking about this myself.

Ooh, I can use http://www.google.com/codesearch for this one!

Searching for "bigint lang:c++ vector.int", without the quotes, I get
this:

http://www.cs.hmc.edu/courses/mostRe...k/cs70ass2.tgz

class BigInt {
...
vector<intchunk s_; // Value of the BigInt.

So it looks like they used the vector, like I suggested, as a "counting"
algorithm, treating each int as a symbol, in base 2-billion.

Assuming ints in range [-2^31, 2^31), I would guess the basis is -2^32 and
not 2^31.

Question: Is this optimal, per vector's guarantees on the speed of
traversal, vs speed pushing back and such? Would a std::list perform
better or worse?

A list would perform much worse memory-wise. Very likely it would also be
much slower on almost any arithmetic algorithm. Memory locality is better
in a vector. Also, many of the fast arithmetic algorithms require random
access iterators over the string of digits.

A little bit on the wicked side: one could also try

class big_int {

unsigned long * digits;
long length;

};

where one uses the sign of length as the sign of the represented number.
Best

Kai-Uwe Bux

[Phlip]

Pete Becker wrote:

>vector<int>?

vector<unsigned is far better.

Yet note that Google agreed with me, because I included the search regex
vector.int! And note the result I found was clearly labeled "homework".

Writing semi-numeric algorithms with signed types produces major
headaches.

Agreed - I said as much myself when I pointed out that the underlying
algorithm was counting in "base 2 billion".

I did not think that thru to its logical conclusion, that the sign only
appears once in a BigInt, so it should not repeat in all the elements.

Just ask anyone who's implemented big integers in Java.

Could you limit each element manually to a managably small positive range?
Waste bits to make the code more maintainable?

And why are we agreeing on vector, if pushing and popping might need to be
faster, and random access is irrelevent, right?

--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!

[Pete Becker]

Phlip wrote:

Pete Becker wrote:

>Just ask anyone who's implemented big integers in Java.

Could you limit each element manually to a managably small positive range?
Waste bits to make the code more maintainable?

Yup. Half the bits, minus 1.

>
And why are we agreeing on vector, if pushing and popping might need to be
faster, and random access is irrelevent, right?

I wasn't agreeing, just replacing int with unsigned.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.

[Kai-Uwe Bux]

Phlip wrote:

Pete Becker wrote:

>>vector<int> ?

>vector<unsigne dis far better.

[snip]

And why are we agreeing on vector, if pushing and popping might need to be
faster, and random access is irrelevent, right?

For addition: yes. For multiplication: yes, if you do the quadratic
algorithm from elementary school. However, some of the faster algorithms
need random access for instance to split the numbers into upper and lower
halves.

Moreover, why would you need to push and pop? For every arithmetic operation
you can get a fairly accurate estimate for the length of the result by
looking at the lengths of the operands:

digits( a+b ) <= 1 + max( digits(a) , digits(b) )
digits( a*b ) <= digits(a) + digits(b)
Best

Kai-Uwe Bux

[Phlip]

Kai-Uwe Bux wrote:

>And why are we agreeing on vector, if pushing and popping might need to
be
faster, and random access is irrelevent, right?

For addition: yes. For multiplication: yes, if you do the quadratic
algorithm from elementary school. However, some of the faster algorithms
need random access for instance to split the numbers into upper and lower
halves.

Moreover, why would you need to push and pop?

From the back, not the front; for the quadratic equation from elementary
school, right?

--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!

[bob]

Phlip wrote:

Kai-Uwe Bux wrote:

And why are we agreeing on vector, if pushing and popping might need to
be
faster, and random access is irrelevent, right?

For addition: yes. For multiplication: yes, if you do the quadratic
algorithm from elementary school. However, some of the faster algorithms
need random access for instance to split the numbers into upper and lower
halves.

Moreover, why would you need to push and pop?

From the back, not the front; for the quadratic equation from elementary
school, right?

--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!

Any ideas how the division would work? Just use elementary school
style?