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<intchunks_; // 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<unsignedis 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<intchunks_; // 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<unsignedis 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<unsignedis 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?

[Kai-Uwe Bux]

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?

The classical methods for addition and subtraction give you the digits of,
say, the sum one by one in order (from least significant to most
significant).

The multiplication algorithm from elementary school (which has quadratic
complexity) does not yield the digits of the product in any nice particular
order. It gives you a bunch of partial products that you need to shift and
add. However, there is a variation of that algorithm that can be
implemented using just push as the access primitive:

345
x175
------
032825 // ones x ones tens x tens hundreds x hundreds
2120 // tens x ones hundreds x tens
0435 // ones x tens tens x hundreds
15 // hundreds x ones
05 // ones x hundreds
========
060375

Each of the combined partial products can be effectively computed in
two-digit chunks that do not overlap. You still have to add, but addition
can be done just using push.

On the other hand, even if you can formulate these algorithms so that push
is the only primitive they use, it still does not make list a good
container for this purpose: in all cases, you know in advance how many
digits to expect and hence you can reserve enough memory from the get go.
In that case, push and pop in a vector are presumably not slower but faster
than push and pop in a list.
Best

Kai-Uwe Bux

[Phlip]

bob wrote:

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

How did the homework I cited do it?

Here's a better Google search:

http://www.google.com/codesearch
vector.unsigned lang:"c++" file:bigint

The second hit has a big working example with this comment:

/* the division operator is based on the algorithm D in Knuth The Art of
Computer Programing
Vol 2 (third edition), page 272 (Algorithm D). */

I detest all the if(DEBUG) stuff, though!

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

[Kai-Uwe Bux]

bo*@coolgroups.com wrote:

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

D.E. Knuth describes an intersting division algorithm using Newtons method.
It reduces division to multiplication so that division is in the same
run-time complexity class as the underlying multiplication algorithm. For
details see TAOCP, Vol. 2, 4.3.3/D, pages 311ff.
Best

Kai-Uwe Bux

[Ivan Vecerina]

"Phlip" <ph******@yahoo.comwrote in message
news:fC*******************@newssvr13.news.prodigy. com...
: 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".
....
: Could you limit each element manually to a managably small positive
range?
: Waste bits to make the code more maintainable?

Of course.
Actually, if printing out the number (in base-10 representation) is
a key operation, using e.g. base-10000 (for a 16-bit short, 32-bit
long), might be a good choice.
That's what I would do if I needed a quick-and-dirty bigint class to
print Fibonacci numbers or factorials as a homework assignment...

hth-Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <http://www.brainbench.com