Re: Strength reduction of constant multipliers

davidm@voltaire.rational.com (David Moore) writes:
>Although it is undoubtably obvious, no-one to my knowledge has remarked
>that you can use Booth's algorithm for run's of ones of length>2. This
>just uses the fact that 1...1 = 10...0 - 1 (Eg 111 = 1000-1) So you need
>an add and a subtract per run, rather than an add per bit.


The first paper I mentioned, includes the above trick plus Cliff
Click's approach, plus additional improvements. Again, the reference
is


    title="Multiplication by Integer Constants",
    author="Robert Bernstein",
    journal="Software -- Practice and Experience",
    volume=16,
    number=7,
    month=jul,
    year=1986,
    pages="641--652"


It even has code (unfortunately incorrect, due in part to typesetting
errors).


Preston Briggs
------------------------------------------------------------------------------
Here's a version in C that I built for illustration purposes.




/*
  *
  * See -- Multiplication by Integer Constants
  * Robert Bernstein
  * Software -- Practice and Experience
  * Volume 16(7), July 1986
  *
  * corrected and enhanced, supposedly, by Preston Briggs
  * October 7, 1991
  *
  */




#include <stdio.h>


typedef
    enum {
        ErrorOp, NegOp, OneOp,
        ShiftAdd, ShiftSub, ShiftRev,
        FactorAdd, FactorSub, FactorRev
        } OpType;




typedef
    struct node {
        struct node *next;
        struct node * parent;
        int value;
        OpType op;
        char cost;
        char valid;
    } Node, *Nodes;




/*
  * HASH should be prime.
  * Can be made fairly large if it turns out
  * that find() is consuming a lot of time.
  */


#define HASH 97


Nodes *mhash;


Nodes find(n)
          int n;
{
    int absn = n < 0 ? -n : n;
    int h = absn % HASH;
    Nodes p = mhash[h];
    while (p && p->value != n)
        p = p->next;
    if (!p) {
        p = (Nodes) malloc(sizeof(Node));
        p->next = mhash[h];
        mhash[h] = p;
        p->value = n;
        p->valid = 0;
        p->cost = 1;
    }
    return p;
}




int make_odd(n)
          int n;
{
    do {
        n >>= 1;
    } while (!(n & 1));
    return n;
}




void try(op, cost, n, lower, upper, p)
          OpType op;
          int *cost;
          int n;
          int lower;
          int *upper;
          Nodes p;
{
    Nodes parent = find(n);
    int k = odd_cost(parent, n, lower+2, *upper);
    if (k < *cost) { /* must beat a previous cost to go here */
        *cost = k; /* if < cost, then should be valid */
        *upper = k;
        p->parent = parent;
        p->op = op;
        p->cost = parent->cost + 2;
        p->valid = 1;
    }
    else if (!p->valid) {
        if (k < *upper) {
            p->parent = parent;
            p->op = op;
            p->cost = parent->cost + 2;
            p->valid = 1;
        }
        else if (!p->parent) { /* initialize */
            p->parent = parent;
            p->op = op;
            p->cost = parent->cost + 2;
        }
        *cost = k;
        *upper = k;
    }
}




int odd_cost(p, n, lower, upper)
          Nodes p;
          int n;
          int lower;
          int upper;
{
    int cost = p->cost + lower;
    if (cost >= upper)
        return cost;
    else if (p->valid)
        return cost;
    else {
        if (n > 0) {
            int i = 4;
            int nn = n >> 1;
            while (i < nn) {
if (n % (i-1) == 0) try(FactorSub, &cost, n/(i-1), lower, &upper, p);
if (n % (i+1) == 0) try(FactorAdd, &cost, n/(i+1), lower, &upper, p);
i <<= 1;
            }
            try(ShiftAdd, &cost, make_odd(n-1), lower, &upper, p);
        }
        else {
            int i = 4;
            int nn = (-n) >> 1;
            while (i < nn) {
if (n % (1-i) == 0) try(FactorRev, &cost, n/(1-i), lower, &upper, p);
if (n % (i+1) == 0) try(FactorAdd, &cost, n/(i+1), lower, &upper, p);
i <<= 1;
            }
            try(ShiftRev, &cost, make_odd(1-n), lower, &upper, p);
        }
        try(ShiftSub, &cost, make_odd(n+1), lower, &upper, p);
        return cost;
    }
}




int shift(x, y)
          int x, y;
{
    int i = 0;
    do {
        y <<= 1;
        i++;
    } while (x != y);
    return i;
}




int emit(p, r)
          Nodes p;
          int r;
{
    switch (p->op) {
    case OneOp:
        return r;
    case NegOp:
        printf("r%d = r0 - r%d\n", -r, r);
        return -r;
    case ShiftAdd:
        {
            int i = emit(p->parent, r);
            int s = shift(p->value - 1, p->parent->value);
            int t = i << s;
            printf("r%d = r%d << %d\n", t, i, s);
            printf("r%d = r%d + r%d\n", t + r, t, r);
            return t + r;
        }
    case ShiftRev:
        {
            int i = emit(p->parent, r);
            int s = shift(1 - p->value, p->parent->value);
            int t = i << s;
            printf("r%d = r%d << %d\n", t, i, s);
            printf("r%d = r%d - r%d\n", r - t, r, t);
            return r - t;
        }
    case ShiftSub:
        {
            int i = emit(p->parent, r);
            int s = shift(p->value + 1, p->parent->value);
            int t = i << s;
            printf("r%d = r%d << %d\n", t, i, s);
            printf("r%d = r%d - r%d\n", t - r, t, r);
            return t - r;
        }
    case FactorAdd:
        {
            int i = emit(p->parent, r);
            int s = shift(p->value - p->parent->value, p->parent->value);
            int t = i << s;
            printf("r%d = r%d << %d\n", t, i, s);
            printf("r%d = r%d + r%d\n", t + i, t, i);
            return t + i;
        }
    case FactorSub:
        {
            int i = emit(p->parent, r);
            int s = shift(p->value + p->parent->value, p->parent->value);
            int t = i << s;
            printf("r%d = r%d << %d\n", t, i, s);
            printf("r%d = r%d - r%d\n", t-i, t, i);
            return t - i;
        }
    case FactorRev:
        {
            int i = emit(p->parent, r);
            int s = shift(p->parent->value - p->value, p->parent->value);
            int t = i << s;
            printf("r%d = r%d << %d\n", t, i, s);
            printf("r%d = r%d - r%d\n", i-t, i, t);
            return i - t;
        }
    case ErrorOp:
        fprintf(stderr, "ErrorOp encountered\n");
        exit(-1);
    }
}




int estimate(n)
          int n;
{
    int i = -1;
    if (n < 0) {
        n = -n;
        i++;
    }
    do {
        if (n & 1) i += 2;
        n >>= 1;
    } while (n);
    return i;
}




int multiply_even(r, i)
          int r;
          int i;
{
    Nodes p1 = find(i+1);
    int c1 = odd_cost(p1, i+1, 0, estimate(i+1));
    int n = make_odd(i);
    Nodes p2 = find(n);
    int c2 = odd_cost(p2, n, 0, c1);
    int delta = i > 0 ? i - 1 : 1 - i;
    Nodes p3 = find(delta);
    int c3 = odd_cost(p3, delta, 0, c2);
    int c23 = c3 < c2 ? c3 : c2;
    if (c1 <= c23) {
        int t = emit(p1, r);
        printf("r%d = r%d - r%d\n", t-r, t, r);
        return t-r;
    }
    else if (c2 <= c3) {
        int s = shift(i, n);
        int res = emit(p2, r);
        int final = res << s;
        printf("r%d = r%d << %d\n", final, res, s);
        return final;
    }
    else {
        int t = emit(p3, r);
        if (i > 0) {
            printf("r%d = r%d + r%d\n", t+r, t, r);
            return t+r;
        }
        else {
            printf("r%d = r%d - r%d\n", r-t, r, t);
            return r-t;
        }
    }
}






/*
  * Multiply 'r' by the immediate value 'i'
  *
  */


int multiply(r, i)
          int r;
          int i;
{
    if (i) {
        if (i & 1) {
            Nodes p = find(i);
            odd_cost(p, i, 0, estimate(i));
            return emit(p, r);
        }
        else return multiply_even(r, i);
    }
    return i;
}




void init_multiply()
{
    Nodes p;
    mhash = (Nodes *) calloc(HASH, sizeof(Nodes));


    p = find(-1);
    p->valid = 1;
    p->op = NegOp;
    p->cost = 1;
    p->parent = 0;


    p = find(1);
    p->valid = 1;
    p->op = OneOp;
    p->cost = 0;
    p->parent = 0;
}




void main()
{
    int i;
    init_multiply();
    while (EOF != scanf("%d", &i))
        multiply(1, i);
}
--

Return to the comp.compilers page.
Search the comp.compilers archives again.