Re: Binary Fuzzy Calculations...

jhughes (jhughes@SPAM-WHACKERretrostudios.com)
Wed, 7 Jul 1999 12:52:34 +0200 (MET DST)

Thorbjoern List wrote in message <3781cb3d@news5.newsfeeds.com>...
>Hi There,
>
>We are in the pursuit of creating a very fast piece of code to calculate
>
> (x*y)/(base-1) where x, y E {0..base}
>
>In essence, x and y are n-base binary numbers representing a fuzzy number
>between 0 and 1. Hence, the result should also be between 0 and 1...
>
>We would like the above calculation done with only
>
> AND, OR, XOR, NOT, SHIFT right and left
>
>to make the calculations very fast.

For a general solution, you'll need the conditional IF, ADD, SUB and looping
constructions as well. Maybe there is a way to boil it down to just logical
operations, but I wouldn't want to do that myself. :-) If you have lots of
memory, make a big lookup table of your results from each operation and just
hash into it for the answer (works for base 16 and under, but not feasible
for more than that).

However, I have to believe that you're using an embedded system or small
instruction set microcontroller without fast floating point multiplies. If
this isn't the case and you're working on modern PC or workstation
equipment, I'd venture that any integer version of this equation will be
much slower, by a tremendous amount. A great deal of work has gone into
making floating point arithmetic practical for solving problems on PCs.

Now, working with that assumption you can pretty easily define
multiplication and division for binary digits. I sat down with scratch
paper and did it in just a minute or two. Here's a brief synopsis of how I
worked it out:

Multiply(operand X,operand Y)
{
result Z=0; // needs at least numbits(X)+numbits(Y)+1 (maybe more? not
sure)
loopCounter=numbits(Y);

while (loopCounter)
{
Shift Y right 1;
if Shifted out a 1 bit then
{
Z+= Shift X left (numbits(Y)-loopCounter);
}
loopCounter--;
}

return Z;
}

(there's probably an easier way to do division... this is just the human
long division process I followed on paper)
Divide(operand X,operand D)
{
result Z=0;
loopCounter=numbits(X)-numbits(D)+1; // we're dividing X by D
accum=Shift Z right (numbits(D)-1);

while (loopCounter)
{
Z=(Shift Z left 1);
if (D>=accum)
{
Z+=1;
accum-=D; // in division, you subtract off a multiple of the
divisor, but these multiples are always by 1
}
accum=(Shift accum left 1); // now, we rotate another bit into the
accumulator
accum+=(Shift X right (loopCounter-1)) AND 1; // this is either
zero or one
loopCounter--;
}
return Z;
}

By the way, you can remove the loop conditional and jump by unrolling the
loop N times, knowing a max of N iterations through each loop given a
specific base, test the number iterations required (R) at the start of the
function and jump to the unrolled iteration that corresponds to N-R, so it
will run exactly R unrolled iterations.

>We would like a set of AND, OR, etc. to
>
> 110 and 100 -> 011
>
>
>
>And we would like this for any base (8, 16, 24, etc.).
>
>Of course, in 8 bit or better representation, this becomes more
>interesting...:-)

Using straightforward multiply and divide, you can use any power of 2.
Maybe any base will work, but I haven't verified that.

I hope this helps you some. (I hope my pseudo code is marginally
intelligible, too!)

JH

############################################################################
This message was posted through the fuzzy mailing list.
(1) To subscribe to this mailing list, send a message body of
"SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at
(2) To unsubscribe from this mailing list, send a message body of
"UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com"
to listproc@dbai.tuwien.ac.at
(3) To reach the human who maintains the list, send mail to
fuzzy-owner@dbai.tuwien.ac.at
(4) WWW access and other information on Fuzzy Sets and Logic see
http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info
(5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html