Velocity Reviews > C++ > Adding and multiplying two unsigned integers

# Adding and multiplying two unsigned integers

Edith Gross
Guest
Posts: n/a

 05-01-2005
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

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

daniel.w.gelder@gmail.com
Guest
Posts: n/a

 05-01-2005
Hmm...

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

Ivan Vecerina
Guest
Posts: n/a

 05-01-2005
"Edith Gross" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
> 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

> TIA,

HTH -Ivan

--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

Ivan Vecerina
Guest
Posts: n/a

 05-01-2005
"Ivan Vecerina" <(E-Mail Removed)> wrote in message
news:d51v9v\$q0o\$(E-Mail Removed)...
> "Edith Gross" <(E-Mail Removed)> wrote in message
> news(E-Mail Removed)...
>> 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 );

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.

Edith Gross
Guest
Posts: n/a

 05-01-2005
On Sun, 01 May 2005 09:08:43 +0200, Ivan Vecerina wrote:

> 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

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Jerry Coffin
Guest
Posts: n/a

 05-01-2005
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).

--
Later,
Jerry.

The universe is a figment of its own imagination.

 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 OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post pozz C Programming 12 03-20-2011 11:32 PM Haris Bogdanović Ruby 5 06-07-2009 09:36 PM John Cho C++ 4 06-14-2006 07:57 PM David Harmon C++ 2 06-14-2006 07:56 PM Tenacious C++ 4 06-03-2006 02:03 AM

Advertisments