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

Groups > comp.lang.c > #23749 > unrolled thread

Comparing Arbitrary-Precision Integers

Back to article view | Back to comp.lang.c

Contents

  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

#23749 — Comparing Arbitrary-Precision Integers

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?

Code below.

Thanks, Dave A.

---------

//Signed 96-bit synthetic type, stored least significant words first
(similar to the
//way the GMP treats limbs).
//
//The dual representation is used because this way the compiler can be
coerced to
//choose appropriate instructions in different situations.
typedef union
{
   UNSIGNED32_T uw[3];
   SIGNED32_T   sw[3];
} APP_BIGINT_S96_T;


//----------------------------------------------------------------------------------------------------
//DESCRIPTION
//   Compares two signed 96-bit integers and returns -1 if a < b, 0 if
a == b, and 1 if a > b.
// 
//INPUTS
//   *in_a, *in_b:
//      Two signed 96-bit integers to compare.
// 
//OUTPUTS
//   <--
//      -1 if *in_a < *in_b, 0 if *in_a == *in_b, and 1 if *in_a >
*in_b.
// 
//EXCEPTION CONDITIONS
//   Passing a NULL or invalid pointer for in_a or in_b will result in
undefined behavior.
// 
//REENTRANCY
//   This function has not been evaluated for re-entrancy or thread
safety.  This function is
//   designed to be called from background (non-ISR) software only.
//
//UNIT TEST HISTORY
//   20120713:  Not yet unit tested.
//----------------------------------------------------------------------------------------------------
SIGNED32_T APP_S96_Cmp(const APP_BIGINT_S96_T *in_a, const
APP_BIGINT_S96_T *in_b)
{
   if (in_a->sw[2] < in_b->sw[2])
   {
      return(-1);
   }
   else if (in_a->sw[2] > in_b->sw[2])
   {
      return(1);
   }
   else if (in_a->uw[1] < in_b->uw[1])
   {
      return(-1);
   }
   else if (in_a->uw[1] > in_b->uw[1])
   {
      return(1);
   }
   else if (in_a->uw[0] < in_b->uw[0])
   {
      return(-1);
   }
   else if (in_a->uw[0] > in_b->uw[0])
   {
      return(1);
   }
   else
   {
      return(0);
   }
}

[toc] | [next] | [standalone]

#23761

On 7/26/2012 4:06 PM, David T. Ashley wrote:
> 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?

     Looks plausible.

> typedef union
> {
>     UNSIGNED32_T uw[3];
>     SIGNED32_T   sw[3];
> } APP_BIGINT_S96_T;

     You may need to be vigilant about the type-punning here.
I think you're all right as long as you deal in pointers to the
union type itself, but it'd be a good idea to avoid passing
around pointers to the uw and sw members independently.  Some
compiler might reason "Storing through this `unsigned int*'
cannot affect the value I've already loaded from this other
`signed int*' ..."  (Disclaimer: Aliasing rules are slipperier
than my grasp is firm, and I may be worrying about nothing.  But
if I were you I'd put a Bar-certified language lawyer on retainer.)

> //REENTRANCY
> //   This function has not been evaluated for re-entrancy or thread
> safety.  This function is
> //   designed to be called from background (non-ISR) software only.

     There cannot be reentrancy problems, since the function cannot
be re-entered.  I see no concurrency issues in the function itself;
you need only ensure that the bigints aren't being changed while
you're in the act of inspecting them.  The ISR restriction seems
irrelevant.

> //UNIT TEST HISTORY
> //   20120713:  Not yet unit tested.

     I trust you've remedied this in the last two weeks ...

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#26076

Eric Sosman <esosman@ieee-dot-org.invalid> writes:

> On 7/26/2012 4:06 PM, David T. Ashley wrote:
>> 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?
>
>     Looks plausible.
>
>> typedef union
>> {
>>     UNSIGNED32_T uw[3];
>>     SIGNED32_T   sw[3];
>> } APP_BIGINT_S96_T;
>
>     You may need to be vigilant about the type-punning here.
> I think you're all right as long as you deal in pointers to the
> union type itself, but it'd be a good idea to avoid passing
> around pointers to the uw and sw members independently.  Some
> compiler might reason "Storing through this `unsigned int*'
> cannot affect the value I've already loaded from this other
> `signed int*' ..."  (Disclaimer: Aliasing rules are slipperier
> than my grasp is firm, [snip elaboration]

The types signed/unsigned int are always allowed to alias, as are
all other corresponding pairs of signed/unsigned integer types.

However, it would be worth checking to see if gcc's 'strict-aliasing'
option may violate this rule (and possibly generate non-conforming
code as a result).

[toc] | [prev] | [next] | [standalone]

#23762

"David T. Ashley" <dashley@gmail.com> wrote in message
news:sj8318pmtqrjdlotfttuqji8mqndf8odms@4ax.com...
> 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 

[toc] | [prev] | [next] | [standalone]

#23766

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.

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.

[toc] | [prev] | [next] | [standalone]

#23768

"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 

[toc] | [prev] | [next] | [standalone]

#23819

On Thu, 26 Jul 2012 23:14:48 +0100, "BartC" <bc@freeuk.com> wrote:
>
>"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.

This is actually for an embedded system.  Perhaps perversely
humorously, I use the GMP under Cygwin to generate test cases for
embedded code.

Yeah, for addition and subtraction if you can bound the results (so
that overflow is not a concern), 2's complement representation is the
fastest.  But for multiplication and division, most code I've seen
first takes the absolute value of both operands and records the sign
(essentially creating a sign-magnitude representation), then performs
the operation, then restores the sign.

DTA

[toc] | [prev] | [next] | [standalone]

#23777

On Thursday, July 26, 2012 1:06:44 PM UTC-7, David T. Ashley wrote:
> 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?
> 
> Code below.
> 
> Thanks, Dave A.
> 
> ---------
> 
> //Signed 96-bit synthetic type, stored least significant words first
> (similar to the
> //way the GMP treats limbs).
> //
> //The dual representation is used because this way the compiler can be
> coerced to
> //choose appropriate instructions in different situations.
> typedef union
> {
>    UNSIGNED32_T uw[3];
>    SIGNED32_T   sw[3];
> } APP_BIGINT_S96_T;
> 
> 
> //----------------------------------------------------------------------------------------------------
> //DESCRIPTION
> //   Compares two signed 96-bit integers and returns -1 if a < b, 0 if
> a == b, and 1 if a > b.
> // 
> //INPUTS
> //   *in_a, *in_b:
> //      Two signed 96-bit integers to compare.
> // 
> //OUTPUTS
> //   <--
> //      -1 if *in_a < *in_b, 0 if *in_a == *in_b, and 1 if *in_a >
> *in_b.
> // 
> //EXCEPTION CONDITIONS
> //   Passing a NULL or invalid pointer for in_a or in_b will result in
> undefined behavior.
> // 
> //REENTRANCY
> //   This function has not been evaluated for re-entrancy or thread
> safety.  This function is
> //   designed to be called from background (non-ISR) software only.
> //
> //UNIT TEST HISTORY
> //   20120713:  Not yet unit tested.
> //----------------------------------------------------------------------------------------------------
> SIGNED32_T APP_S96_Cmp(const APP_BIGINT_S96_T *in_a, const
> APP_BIGINT_S96_T *in_b)
> {
>    if (in_a->sw[2] < in_b->sw[2])
>    {
>       return(-1);
>    }
>    else if (in_a->sw[2] > in_b->sw[2])
>    {
>       return(1);
>    }
>    else if (in_a->uw[1] < in_b->uw[1])
>    {
>       return(-1);
>    }
>    else if (in_a->uw[1] > in_b->uw[1])
>    {
>       return(1);
>    }
>    else if (in_a->uw[0] < in_b->uw[0])
>    {
>       return(-1);
>    }
>    else if (in_a->uw[0] > in_b->uw[0])
>    {
>       return(1);
>    }
>    else
>    {
>       return(0);
>    }
> }

Your code is reentrant because you aren't storing off any results in the middle of the calculation into static variables and you aren't making changes to the underlying code. Whether your code is thread safe or not depends upon the attributes applied to the various instances of APP_BIGINT_S96Ts that you declare. 

[toc] | [prev] | [next] | [standalone]

#23787

On 07/26/2012 10:06 PM, David T. Ashley wrote:
> 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?
> 
> Code below.
> 
> Thanks, Dave A.


you are reinventing the wheel and, frankly speaking, it appears to be a
bit square. use already available and well tested lib. my recommendation
is GMP:
http://gmplib.org
there are also bindings for many languages available (including C++).

-- 
pozdrawiam serdecznie / best regards,
bartek szurgot
/* http://www.baszerr.eu */

[toc] | [prev] | [next] | [standalone]

#23821

On Fri, 27 Jul 2012 08:53:45 +0200, bartek szurgot <basz@no.spam>
wrote:

>On 07/26/2012 10:06 PM, David T. Ashley wrote:
>> 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?
>> 
>> Code below.
>> 
>> Thanks, Dave A.
>
>
>you are reinventing the wheel and, frankly speaking, it appears to be a
>bit square.

Note to self:  beat myself repeatedly on head with tire iron and cry
myself to sleep because I invented a square wheel.

> use already available and well tested lib. my recommendation
>is GMP:
>http://gmplib.org
>there are also bindings for many languages available (including C++).

Thanks for your suggestion.

Unfortunately, the code I posted is for the ARM and part of an
embedded system.  Design rules for these systems usually prohibit
dynamic allocation, so the GMP is off the table.  The usual approach
is to bound the result of the calculation analytically then perform it
in the most efficient way.

For example, if I am adding together 25 signed 64-bit numbers, I might
determine analytically that this sum cannot overflow a 96-bit signed
number, and then I would perform the calculation without any overflow
checking.

The GMP is pretty cool.  I use it in fact under Cygwin or on a *nix
box  to generate test cases for embedded code that deals with large
integers.

And when I want to investigate the best integer algorithms, the GMP
source code and manual is usually the first place I go (as well as
TOACP).

DTA

[toc] | [prev] | [next] | [standalone]

#23824

On 2012-07-27, David T  Ashley <dashley@gmail.com> wrote:
> And when I want to investigate the best integer algorithms, the GMP
> source code and manual is usually the first place I go (as well as
> TOACP).

The Of Art Computer Programming?

[toc] | [prev] | [next] | [standalone]

#23832

Ike Naar <ike@iceland.freeshell.org> writes:
> On 2012-07-27, David T  Ashley <dashley@gmail.com> wrote:
>> And when I want to investigate the best integer algorithms, the GMP
>> source code and manual is usually the first place I go (as well as
>> TOACP).
>
> The Of Art Computer Programming?

Must be the Forth edition.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#23834

On Fri, 27 Jul 2012 16:53:02 -0700, Keith Thompson <kst-u@mib.org>
wrote:

>Ike Naar <ike@iceland.freeshell.org> writes:
>> On 2012-07-27, David T  Ashley <dashley@gmail.com> wrote:
>>> And when I want to investigate the best integer algorithms, the GMP
>>> source code and manual is usually the first place I go (as well as
>>> TOACP).
>>
>> The Of Art Computer Programming?
>
>Must be the Forth edition.

You guys are just plain mean!

Yes, I meant TAOCP.

DTA

[toc] | [prev] | [next] | [standalone]

#23950

David T. Ashley wrote:

> The GMP is pretty cool.  I use it in fact under Cygwin or on a *nix
> box  to generate test cases for embedded code that deals with large
> integers.
> 
> And when I want to investigate the best integer algorithms, the GMP
> source code and manual is usually the first place I go (as well as
> TAOCP).

I think you might enjoy fefe's article:
http://dl.fefe.de/bignum.pdf

You might also want to take a look at TomsFastMath:
http://libtom.org/?page=features&whatfile=tfm
(of interest to you: ARM-optimized asm, no heap usage)

cf. also the accompanying PDF:
https://github.com/libtom/tomsfastmath/raw/master/doc/tfm.pdf

Regards.

[toc] | [prev] | [next] | [standalone]

#23952

On Mon, 30 Jul 2012 14:29:10 +0200, Noob <root@127.0.0.1> wrote:

>David T. Ashley wrote:
>
>> The GMP is pretty cool.  I use it in fact under Cygwin or on a *nix
>> box  to generate test cases for embedded code that deals with large
>> integers.
>> 
>> And when I want to investigate the best integer algorithms, the GMP
>> source code and manual is usually the first place I go (as well as
>> TAOCP).
>
>I think you might enjoy fefe's article:
>http://dl.fefe.de/bignum.pdf
>
>You might also want to take a look at TomsFastMath:
>http://libtom.org/?page=features&whatfile=tfm
>(of interest to you: ARM-optimized asm, no heap usage)
>
>cf. also the accompanying PDF:
>https://github.com/libtom/tomsfastmath/raw/master/doc/tfm.pdf
>
>Regards.

Herr Leitner and I had a scrap years ago on the qmail list.  I don't
remember the details, but I believe (from memory, could be
inaccurate), it went like this:

a)I posted something on the list that violated Herr Leitner's sense of
technical decency (meaning that he thought I was an idiot).

b)He sent me an e-mail indicating, in a vulgar way, that I'm not of
suitable intelligence and it would be better for everyone if I don't
reproduce (or something like that).

c)I posted his e-mail on the qmail list to embarrass him.

d)His response was that his e-mail was private and I didn't have the
right to post it publicly.

e)I had a different opinion.

f)And so on.

That being said ...

Despite my personal impression of him as a raving lunatic, that first
link is quite interesting.  A lot of goodies there, and algorithms and
paradigms to explore.

Thanks, Dave A.

[toc] | [prev] | [next] | [standalone]

#23803

"David T. Ashley" <dashley@gmail.com> ha scritto nel messaggio
news:sj8318pmtqrjdlotfttuqji8mqndf8odms@4ax.com...
> Hi,

i follow your object: "Comparing Arbitrary-Precision Integers"
not yuor post that show one implementation in 3 words +
problem in machine int-unsigned i never understand
nor i want understand

i'm not sure about u32 i=0; if  --i == (u32)-1
i'm not sure about structure typedef definition too...

typedef struct
{u32   len;
 u32  *num;
}unum;

#define  R  return
#define  F  for
#define  G  goto

i32   compare(unum*   a,   unum*   b)
{u32   i;
 if(a==0||b==0)            R  -2;
 if(a->len==0||b->len==0)  R  -2;
      if(a->len > b->len)  R   1;
 else if(a->len < b->len)  R  -1;
 i=a->len-1;
qu:     if(a->num[i]>b->num[i]) R   1;
   else if(a->num[i]<b->num[i]) R  -1;
   --i;
   if(i!=(u32)-1) G  qu;
 R   0;
}

for 96 bit integers: they are 'odd' for me....
i prefer 2^i or better u32...
all the remain for me not exist...

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web