Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: Comparing Arbitrary-Precision Integers

Reply
Thread Tools

Re: Comparing Arbitrary-Precision Integers

 
 
BartC
Guest
Posts: n/a
 
      07-26-2012
"David T. Ashley" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Hi,
>
> I'm using a 2's complement machine (and I'm comfortable baking this
> assumption into the code). I've implemented a large number of
> functions on signed integers that are longer than the machine
> supports.
>
> Does the code below for comparison look correct?
>
> I think the right approach is to compare the most significant limb in
> a signed sense then to compare the least significant limbs in an
> unsigned sense. Is that right?


Does your code work? Test with a reasonable mix of positive and negative
numbers (some of which must be equal in the most significant words) to see
if it gives the expected results.

However I might just subtract one number from the other; the sign of the
result will tell you if the relation is < or >=. But you need to check for
all words zero to distinguish > and =.

That assumes you have a reasonably efficient subtract function. (Having
dedicated functions to check each of =,!=,<,<=,>=,>, when a specific
comparison is in mind, might also help to streamline things. Equals/not
equals are particularly easy.)

--
Bartc

 
Reply With Quote
 
 
 
 
Ike Naar
Guest
Posts: n/a
 
      07-26-2012
On 2012-07-26, BartC <(E-Mail Removed)> wrote:
> [about comparisons]
> However I might just subtract one number from the other; the sign of the
> result will tell you if the relation is < or >=. But you need to check for
> all words zero to distinguish > and =.


This is less efficient than direct comparison.
Direct comparison can stop at the most significant
limb that differs. Subtraction has to process all
limbs of both numbers.

Here's an example in decimal notation:

A : 178359374328607427026709270970624
B : 413327689277727826782971200987096

Just by looking at the first digit one can see that A < B,
whereas performing the subtraction

A-B : -234968314949120399756261930016472

requires processing every digit of A and B.
 
Reply With Quote
 
 
 
 
BartC
Guest
Posts: n/a
 
      07-26-2012


"Ike Naar" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed). ..
> On 2012-07-26, BartC <(E-Mail Removed)> wrote:
>> [about comparisons]
>> However I might just subtract one number from the other; the sign of the
>> result will tell you if the relation is < or >=. But you need to check
>> for
>> all words zero to distinguish > and =.

>
> This is less efficient than direct comparison.
> Direct comparison can stop at the most significant
> limb that differs. Subtraction has to process all
> limbs of both numbers.


That's quite likely.

However the OP's example suggested he was using 96-bits, which can be
subtracted neatly in 32-bit assembly (the result doesn't need to be written
to memory), without needing multiple branches. It might be more fiddly in C
though.

> Here's an example in decimal notation:
>
> A : 178359374328607427026709270970624
> B : 413327689277727826782971200987096
>
> Just by looking at the first digit one can see that A < B,
> whereas performing the subtraction
>
> A-B : -234968314949120399756261930016472
>
> requires processing every digit of A and B.


For arbitrary precision, probably signed magnitude would be used, then I'd
be more confident about using incremental compare without worrying about all
those possible leading '1' bits.

--
Bartc

 
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
comparing two arrays of integers. Nag Java 3 06-23-2005 06:16 PM
comparing strings and integers beliavsky@aol.com Python 5 05-20-2004 03:55 PM
comparing long integers Elijah Bailey C++ 12 01-23-2004 03:47 PM
comparing long integers Elijah Bailey C Programming 11 01-23-2004 03:47 PM
Comparing char* with integers and characters Nicholas C Programming 13 09-09-2003 03:04 PM



Advertisments