Bit fiddling calculating fraction

[dos.fishing]

Hello,

I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.
Anyone got any ideas? Table lookup?

[Barry]

<do*********@gm ail.comwrote in message
news:11******** **************@ v33g2000cwv.goo glegroups.com.. .

Hello,

I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.
Anyone got any ideas? Table lookup?

It isn't clear what you are doing. Based on the comments this
returns A or zero. Also, the parantheses do make a difference.

[dos.fishing]

Sorry for being unclear. This is maybe better?

ushort f ( ushort valueA, ushort valueB) {
float fraction = valueB / 31.0;
return (ushort)(valueA * fraction);
}

Only that I want to avoid using floating point operations and
division/multiplication.

[Ben Bacarisse]

do*********@gma il.com writes:

I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

C.l.c Guidelines suggest posting a complete program. We have to guess
what ushort is. This is not as easy as you probably think since what
you have written above makes no sense if we assume

typedef unsigned short ushort;

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.

If we believe the block comment about the possible values in valueB, then

return valueB == 31;

will do the same as the return statement you wrote. If you put the
parentheses in by mistake (thinking that it made no difference) then
a divide is probably the way.

Of course, it is more likely that you want to be dividing by 32. In
that case a shift will be faster but the compiler will probably do that
for you anyway.

Write the simples clearest code and optimise it for speed only if you
find it to be a problem.

--
Ben.

[jacob navia]

do*********@gma il.com a écrit :

Hello,

I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.
Anyone got any ideas? Table lookup?

Any division by a signed constant can be replaced by a
much cheaper multiplication and some shifts. For instance,
for the code above, the lcc-win32 compiler will not
generate a division by 31 but the following code:

movzwl 8(%ebp),%edi ; valueA-->edi
movzwl 12(%ebp),%eax ; valueB->eax
movl $-2078209981,%edx
movl %eax,%ecx ; save valueB for later
imull %edx ; multiply valueB * -2078209981
addl %ecx,%edx ; add valueA to high word
sarl $4,%edx ; shift right 4
sarl $31,%ecx ; shift left 31
subl %ecx,%edx ; subtract the result to valueB
movl %edx,%eax ; high word is result of division by 31
imull %eax,%edi ; multiply by valueA
movzwl %di,%eax ; cast to unsigned short and set return value

You see? No division. I would say you leave the optimization
to the compiler.

jacob

[David T. Ashley]

<do*********@gm ail.comwrote in message
news:11******** **************@ v33g2000cwv.goo glegroups.com.. .

Hello,

I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.

Etc.

If I'm understanding your problem correctly, it is the standard rational
approximation problem with the denominator fixed.

Generally, you seek to approximate f(x) = r * x by g(x) = (h * x) div k;
where r and x are real, and h and k are integers.

You generally seek to choose h/k as close as possible to r.

There are three basic strategies.

#1: You can choose k as a power of 2 so that the mapping is

g(x) = (h * x)/2^q

where of course the division is handled by shifting.

#2: You can use an arbitrary h and k, which normally doesn't work out badly
since most processors have efficient integer multiplication and division
instructions.

Choosing h/k as close as possible to an arbitrary r isn't as easy as it
sounds. There is an O(log N) technique using number theory and continued
fractions. I'll be glad to send you a technical paper if you e-mail me
directly at dt*@e3ft.com. For example, the best approximation to PI with 16
bit h,k is 65298 / 20785. Finding such an approximation in 32 or 64 bits is
very hard if you don't know how to do it O(log N).

#3: You can sometimes use addition to implement the multiplication. For
example, if h is 11 and k is 4:

two_times = x + x;
four_times = two_times + two_times;
eight_times = four_times + four_times;
eleven_times = x + two_times + eight_times;
result = eleven_times >2;

Those are the three basic techniques.

Any look attractive to you?

Dave.

[CBFalconer]

do*********@gma il.com wrote:

>
I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.
Anyone got any ideas? Table lookup?

Try the following:

/* Find best rational approximation to a double */
/* by C.B. Falconer, 2006-09-07. Released to public domain */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <limits.h>
#include <errno.h>

int main(int argc, char **argv)
{
int num, approx, bestnum, bestdenom;
int lastnum = 500;
double error, leasterr, value, criterion, tmp;
char *eptr;

value = 4 * atan(1.0);
if (argc 2) lastnum = strtol(argv[2], NULL, 10);
if (lastnum <= 0) lastnum = 500;
if (argc 1) {
tmp = strtod(argv[1], &eptr);
if ((0.0 >= tmp) || (tmp INT_MAX) || (ERANGE == errno)) {
puts("Invalid number, using PI");
}
else value = tmp;
}
criterion = 2 * value * DBL_EPSILON;
puts("Usage: ratvalue [number [maxnumerator]]\n"
"number defaults to PI, maxnumerator to 500");
printf("Rationa l approximation to %.*f\n", DBL_DIG, value);

for (leasterr = value, num = 1; num < lastnum; num++) {
approx = (int)(num / value + 0.5);
if (0 == (int)approx) continue;
error = fabs((double)nu m / approx - value);
if (error < leasterr) {
bestnum = num;
bestdenom = approx;
leasterr = error;
printf("%8d / %-8d = %.*f with error %.*f\n",
bestnum, bestdenom,
DBL_DIG, (double)bestnum / bestdenom,
DBL_DIG, leasterr);
if (leasterr <= criterion) break;
}
}
return 0;
} /* main, ratapprx */

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>

[Ben Bacarisse]

CBFalconer <cb********@yah oo.comwrites:

do*********@gma il.com wrote:

>>
I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.
Anyone got any ideas? Table lookup?

Try the following:

/* Find best rational approximation to a double */

If this comment is an accurate description, then I can't see how it
can help. The OP is starting with an exact, known, rational so getting
close is not the issue.

To the OP: Are you sure that simple integer arithmetic is not fast
enough? I.e.

return (valueA * valueB + 31/2) / 31;

(and I m still having trouble with 31 being the correct divisor!)

--
Ben.

[David T. Ashley]

"CBFalconer " <cb********@yah oo.comwrote in message
news:45******** *******@yahoo.c om...

do*********@gma il.com wrote:

>>
I'm writing a function that should do the following:

/**
* Calculate and return fraction of valueA where max fractions is 31.
* param valueA A five bit value, 0-31.
* param valueB The fraction, a five bit value, 0-31.
*
*/
ushort f ( ushort valueA, ushort valueB) {
return valueA * (valueB / 31); //the paranthesis are only here for
the looks of it.
}

I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance.
Anyone got any ideas? Table lookup?

Try the following:

/* Find best rational approximation to a double */
/* by C.B. Falconer, 2006-09-07. Released to public domain */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <limits.h>
#include <errno.h>

int main(int argc, char **argv)
{
int num, approx, bestnum, bestdenom;
int lastnum = 500;
double error, leasterr, value, criterion, tmp;
char *eptr;

value = 4 * atan(1.0);
if (argc 2) lastnum = strtol(argv[2], NULL, 10);
if (lastnum <= 0) lastnum = 500;
if (argc 1) {
tmp = strtod(argv[1], &eptr);
if ((0.0 >= tmp) || (tmp INT_MAX) || (ERANGE == errno)) {
puts("Invalid number, using PI");
}
else value = tmp;
}
criterion = 2 * value * DBL_EPSILON;
puts("Usage: ratvalue [number [maxnumerator]]\n"
"number defaults to PI, maxnumerator to 500");
printf("Rationa l approximation to %.*f\n", DBL_DIG, value);

for (leasterr = value, num = 1; num < lastnum; num++) {
approx = (int)(num / value + 0.5);
if (0 == (int)approx) continue;
error = fabs((double)nu m / approx - value);
if (error < leasterr) {
bestnum = num;
bestdenom = approx;
leasterr = error;
printf("%8d / %-8d = %.*f with error %.*f\n",
bestnum, bestdenom,
DBL_DIG, (double)bestnum / bestdenom,
DBL_DIG, leasterr);
if (leasterr <= criterion) break;
}
}
return 0;
} /* main, ratapprx */

I believe there is an O(log N) continued fraction algorithm to do this.

[David T. Ashley]

"Ben Bacarisse" <be********@bsb .me.ukwrote in message
news:87******** ****@bsb.me.uk. ..

CBFalconer <cb********@yah oo.comwrites:

>>>
I'm looking for a way to get approximatly the same result by doing some
bit fiddling with the bit patterns of the values optimizing
performance .
Anyone got any ideas? Table lookup?

If this comment is an accurate description, then I can't see how it
can help. The OP is starting with an exact, known, rational so getting
close is not the issue.

What part of the OP's words "approximat ely the same result" didn't make it
by your filter?