Adding and multiplying two unsigned integers

E

Edith Gross

I'd like to add to unsigned integers and find out whether a carry occurs.
Can I do that in a simple and fast way?

A similar problem is subtracting with borrow and the multiplication of two
unsigned integers where the result may not fit?

Can anybody give me a hint of how to wolve these problems?

TIA,

EG
 
D

daniel.w.gelder

Hmm...

total = first + second;
if (total < first) { /*then there was a carry*/ }
 
I

Ivan Vecerina

Edith Gross said:
I'd like to add to unsigned integers and find out whether a carry occurs.
Can I do that in a simple and fast way?
In a portable way, I think the best you can do is:
unsigned c = a + b;
bool carryOccurred = ( c<a || c<b );
A similar problem is subtracting with borrow and the multiplication of two
unsigned integers where the result may not fit?

For subtraction, you can pre-test which number is larger:
bool carryWillOccur = (b>a);
unsigned c = a-b;

For multiplication, you need to split each operand in two halfs,
or rely on the availability of a longer integer number.
Alternatively, using bit-shifts and additions for each bit
of one of the operands is often a good approach.
Can anybody give me a hint of how to wolve these problems?

It looks like you might be looking to implement a "big integer"
library. A number of such libraries exist already, so a web
search might be worth your time ;)

HTH -Ivan
 
I

Ivan Vecerina

Ivan Vecerina said:
In a portable way, I think the best you can do is:
unsigned c = a + b;
bool carryOccurred = ( c<a || c<b );
Of course, it is redundant to perform both tests.
You could use:
bool carryOccurred = ( c<b );
or:
bool carryOccurred = ( c<a );
no need for both.
 
E

Edith Gross

It looks like you might be looking to implement a "big integer"
library. A number of such libraries exist already, so a web
search might be worth your time ;)

Thx. It may be funny, but it seems to me, that there is no such library
(or they are not free). I looked around and googled, but found nothing. Of
course there are a lot of candidates but at some place they do not work.
For example CLN does not work, as it is made for Linux. I tried another
one which was said to have a Windows version but I could not compile it,
etc.

Now I use something like this:

inline unsigned int add(unsigned int a,unsigned int b)
{
__asm {
clc
cmp overflow,0
je nulla
setc
nulla:
mov eax,a
adc eax,b
mov overflow,0
jnc nooverflow
mov overflow,1
nooverflow:
}
}

but I am not even sure that it works. But this is a specific
implementation and is OT in this group.
EG
 
J

Jerry Coffin

Edith Gross wrote:

[ ... arbitrary precision math ]
Thx. It may be funny, but it seems to me, that there is no such
library (or they are not free).

There are quite a few that are free in one fashion or another. Some
that I've used include:

MIRACL: http://indigo.ie/~mscott/
Not quite the speed demon they claim it to be, but easy to use.
Free for non-commercial types of uses.

NTL: http://www.shoup.net/ntl/
Big integer capability is more or less a side-item here, but it's
quite fast and works nicely nonetheless. Distributed under GPL.

GMP: ftp://ftp.gnu.org/gnu/gmp/ (and many others)
Quite fast. Builds easily on Linux, with some difficulty with
MinGW, and AFAIK, not at all with any non-GNU compiler.
Distributed under GPL.

apfloat: http://www.apfloat.org/apfloat/
I've used it only a little, but so far it's been the fastest I've
tried. Both portable and compiler-specific versions for Borland,
VC++ and GNU are available. The version specifically for VC++ also
requires MASM (which you may already have). Freeware.

Both NTL and apfloat provide high-precision floating point in addition
to the usual large integers. MIRACL doesn't provide floating point but
does support rational numbers (i.e. ratios of two large integers) which
give many of the same capabilities. If you require it to be completely
free, apfloat is the obvious choice here. If you can live with its
licensing, I'd probably go for NTL instead -- I find it easier to use
(though that may be partly because I've used it a lot more).
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top