Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #23768

Re: Comparing Arbitrary-Precision Integers

Show all headers | View raw

"Ike Naar" <ike@sverige.freeshell.org> wrote in message 
news:slrn3vfsk13ekv.o5l.ike@sverige.freeshell.org...
> On 2012-07-26, BartC <bc@freeuk.com> 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 

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Comparing Arbitrary-Precision Integers David T. Ashley <dashley@gmail.com> - 2012-07-26 16:06 -0400
  Re: Comparing Arbitrary-Precision Integers Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-07-26 17:01 -0400
    Re: Comparing Arbitrary-Precision Integers Tim Rentsch <txr@alumni.caltech.edu> - 2012-09-07 11:49 -0700
  Re: Comparing Arbitrary-Precision Integers "BartC" <bc@freeuk.com> - 2012-07-26 22:20 +0100
    Re: Comparing Arbitrary-Precision Integers Ike Naar <ike@sverige.freeshell.org> - 2012-07-26 21:46 +0000
      Re: Comparing Arbitrary-Precision Integers "BartC" <bc@freeuk.com> - 2012-07-26 23:14 +0100
        Re: Comparing Arbitrary-Precision Integers David T. Ashley <dashley@gmail.com> - 2012-07-27 17:55 -0400
  Re: Comparing Arbitrary-Precision Integers Michael Angelo Ravera <maravera@prodigy.net> - 2012-07-26 17:51 -0700
  Re: Comparing Arbitrary-Precision Integers bartek szurgot <basz@no.spam> - 2012-07-27 08:53 +0200
    Re: Comparing Arbitrary-Precision Integers David T. Ashley <dashley@gmail.com> - 2012-07-27 18:02 -0400
      Re: Comparing Arbitrary-Precision Integers Ike Naar <ike@iceland.freeshell.org> - 2012-07-27 22:23 +0000
        Re: Comparing Arbitrary-Precision Integers Keith Thompson <kst-u@mib.org> - 2012-07-27 16:53 -0700
          Re: Comparing Arbitrary-Precision Integers David T. Ashley <dashley@gmail.com> - 2012-07-27 21:25 -0400
      Re: Comparing Arbitrary-Precision Integers Noob <root@127.0.0.1> - 2012-07-30 14:29 +0200
        Re: Comparing Arbitrary-Precision Integers David T. Ashley <dashley@gmail.com> - 2012-07-30 09:28 -0400
  Re: Comparing Arbitrary-Precision Integers "io_x" <a@b.c.invalid> - 2012-07-27 20:46 +0200

csiph-web