Velocity Reviews > Re: Comparing Arbitrary-Precision Integers

# 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

Ike Naar
Guest
Posts: n/a

 07-26-2012
On 2012-07-26, BartC <(E-Mail Removed)> wrote:
> 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.

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