Alloy Community

User login

What is the difference between primitive int and sig Int?

 
Posted on: Fri, 01/25/2008 - 11:34
Joined: 2008-05-15
Points: 334
User is offline
What is the difference between primitive int and sig Int?
Answer:

There are several reasons, but the practical engineering reason
is that in some situations, we need non-logarithmic encoding,
and in other situations, we need the logarithmic encoding.
So for practical efficiency sake, we include both.

1. We need the atom presentation when we talk about a set
   of numbers, or when we include a number as part of a tuple.

   Eg. a relation from {A,B,C}->{-1,0} has 6 possible tuples:
   {(A,-1), (A,0), (B,-1), (B,0), (C,-1), (C,0)}.
   Each tuple can independently be in or not in the relation.
   So we need 6 boolean variables to represent
   whether EACH tuple is in or not.

2. We need the logarithmic encoding when we want to
   perform addition, subtraction, multiplication,
   division... efficiently.

   Eg. the boolean circuit for integer addition using the Atom
   representation is quadratic in the number of possible integers.
   ("if a=0 and b=0, then ans=0" "if a=0 and b=1, then ans=1"...
   if a=1 and b=0, then ans=1" "if a=1 and b=1, then ans=2"......)
   But the boolean circuit for integer addition using 2's complement
   representation is linear in the number of bits.

So if integer bitwidth is N, then doing addition using atom representation
is O(2^N * 2^N), but using logarithmic encoding it is only O(N).
That's a very drastic difference.

In summary, the user sometimes must use the first, and sometimes must use
the second. So we provide both forms, and we provide the operator for
converting a value between the 2 representations, and we rely on the user
to try to minimize unnecessary translation back-and-forth.

Syndicate content  

The development of this site is supported by the National Science Foundation under Computing Research Infrastructure Grant No. 0707612.

Theme originally designed by Chris Herberte