Re: Comparing Arbitrary-Precision Integers

Discussion in 'C Programming' started by BartC, Jul 26, 2012.

  1. BartC

    BartC Guest

    "David T. Ashley" <> wrote in message
    news:...
    > 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
    BartC, Jul 26, 2012
    #1
    1. Advertising

  2. BartC

    Ike Naar Guest

    On 2012-07-26, BartC <> 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.
    Ike Naar, Jul 26, 2012
    #2
    1. Advertising

  3. BartC

    BartC Guest

    "Ike Naar" <> wrote in message
    news:...
    > On 2012-07-26, BartC <> 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
    BartC, Jul 26, 2012
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. christopher diggins

    Diggins PDP #3 : arbitrary precision integers

    christopher diggins, May 24, 2005, in forum: C++
    Replies:
    0
    Views:
    366
    christopher diggins
    May 24, 2005
  2. Eric Sosman

    Re: Comparing Arbitrary-Precision Integers

    Eric Sosman, Jul 26, 2012, in forum: C Programming
    Replies:
    1
    Views:
    351
    Tim Rentsch
    Sep 7, 2012
  3. Michael Angelo Ravera

    Re: Comparing Arbitrary-Precision Integers

    Michael Angelo Ravera, Jul 27, 2012, in forum: C Programming
    Replies:
    0
    Views:
    357
    Michael Angelo Ravera
    Jul 27, 2012
  4. Ike Naar

    Re: Comparing Arbitrary-Precision Integers

    Ike Naar, Jul 27, 2012, in forum: C Programming
    Replies:
    1
    Views:
    343
    Keith Thompson
    Jul 28, 2012
  5. Noob
    Replies:
    0
    Views:
    341
Loading...

Share This Page