Constant Time Execution Equivalents

    In what follows are presented some constant time equivalents for relative operators. The Boolean operators ^,! and % are used for that purpose. The operator ^ is the Ex-OR operator and ! is the Not operator and % is the modulus operator.

Here follows some if statements and their constant time equivalents.

Even and Odd Number validation:

The following table summarizes the constant time equivalents and their general expressions for some of the common program statement blocks that we encounter in our daily life.

Program Statement Block

Constant Time Equivalent

 x++; 

if(x >= MAX_SIZE) x = 0;

 

 

x =  ( x + 1 ) % MAX_SIZE; 

 

 

 x--; 

if(x < 0) x = MAX_SIZE - 1;

 

 

x = (x + MAX_SIZE 1) % MAX_SIZE; 

 x = x + increment; 

if(x >= MAX_SIZE) x = 0;

 

x =  (x + increment) % MAX_SIZE;

 

 

 x = x - decrement; 

if(x < 0) x = MAX_SIZE - 1;

 

x = (x + MAX_SIZE decrement) % MAX_SIZE;

 x = x + increment; 

if(x >=MAX_SIZE) x = UPPER LIMIT;

 

x = x + increment; 

x = (x * (!((x/MAX_SIZE)^0))) + (UPPER LIMIT * (!!((x/MAX_SIZE)^0)));

 

 x = x - decrement; 

if(x < MIN_SIZE) x = LOWER LIMIT;

 

x = x - decrement; 

x = (LOWER LIMIT * (!(x / MIN_SIZE)^0))) + (x * (!!(( x / MIN_SIZE)^0)));

 

if(x % 2) x--;

 

x  &= ~0x01 ;

 

if(x % 2) x++;

 

x = (x & (~0x01)) + ((x - (x & (~0x01))) << 1) ;

 

if(!(x % 2)) x++;

 

x |= 0x01 ;

 

if(!(x % 2)) x--;

 

x = (x | 0x01) - ((x - (x | 0x01)) << 1) ;

 

Few Boolean Tips:

Converting Arithmetic and Relational expressions to Propositional Logic CNF Equations

In the below table are presented few CNF expressions and their equivalent arithmetic expression.

Symbols such as x, y, z, a, b, c etc... each denote a single boolean value that can take either true or false value.

We use ≠ to represent inequality, and ! to denote logical Not. The sign = is used to denote equality (and not assignment). Thus it is same as == of C/C++; For example, the expression if x then y=1 means whenever x is true, y also should be true, which is same as if x then assert(y==1) in C++.

For CNF expressions we use to represent logical AND, to represent logical OR, and - to represent complement. Thus x and -(-(x)) should essentially mean the same.

Expression CNF Equation
if x then y=1 (-xy)
if x then y=0 (-x-y)
xy (x-y)
xy (-xy)
x = y (-xy) ∧ (x-y)
xy (xy) ∧ (-x-y)
x > y (xy) ∧ (x-y) ∧ (-x -y)
x < y (xy) ∧ (-xy) ∧ (-x -y)
(x & y) = z (-x-yz) ∧ (x-z) ∧ (y-z)
if(x) then (a = b) (-xa-b) ∧ (-x-ab)
if(x) then (ab) (-xab) ∧ (-x-a-b)
if(!x) then (a = b) (xa-b) ∧ (x-ab)
if(!x) then (ab) (xab) ∧ (x-a-b)
if(x & y) then (a = b) (-x-ya-b) ∧ (-x-y-ab)
if(!x & !y) then (a = b) (xya-b) ∧ (xy-ab)
if(x = y) then (a = b) (-x-y-ab) ∧ (-x-ya-b) ∧ (xya-b) ∧ (xy-ab)

CNF Expression for Full-Adder

          |i (Carry-in)
          |
        |‾‾‾‾‾|
  x-----|     |----S (Sum)
        | F A |
  y-----|_____|----C (Carry-out)

In the above full-adder, inputs are x, y and i, while the outputs are s and c. Equations are as below:

S ≡ (x + y + i) % 2 ≡ x ⊕ y ⊕ i;

C ≡ (x + y + i) / 2 ≡ x.y + x.i + y.i;

CNF for the Carry-out is:

(x ∨ y ∨ -c) ∧ (x ∨ i ∨ -c) ∧ (y ∨ i ∨ -c) ∧ (-x ∨ -y ∨ c) ∧ (-x ∨ -i ∨ c) ∧ (-y ∨ -i ∨ c)

CNF for the Sum is:

(x ∨ y ∨ i ∨ -s) ∧ (x ∨ -y ∨ -i ∨ -s) ∧ (-x ∨ y ∨ -i ∨ -s) ∧ (-x ∨ -y ∨ i ∨ -s) ∧ (-x ∨ -y ∨ -i ∨ s) ∧ (-x ∨ y ∨ i ∨ s) ∧ (x ∨ -y ∨ i ∨ s) ∧ (x ∨ y ∨ -i ∨ s)

By

P.GopalaKrishna

Other Articles   Home Page