# Forum: FPGA, VHDL & Verilog Algorithm for x/63 and x/127

Rate this post
 0 ▲ useful ▼ not useful
Dear all,

I believe I have invented a formula for quotient calculation that works
for x/63 and x/127.

The formula is as follows and it is divisionless and multiplierless:

y = (((x>>n)+x+((1<<n)+1))>>n)-1;

Use n=6 for 63, and n=7 for 127. 1<<n is the strength-reduced form for
calculating 2^n.

It does not require any double-word arithmetic (like with multiplying by
the multiplicative inverse and then performing adjustment steps). It
does not seem to work for other dividers, but a systematic fix may be
possible.

Are there any known references to this?

Best regards
http://github.com/nkkav/

Rate this post
 0 ▲ useful ▼ not useful
Nikolaos Kavvadias wrote:
> Use n=6 for 63, and n=7 for 127.

> It does not seem to work for other dividers

Have you tried n=5 for 31, n=4 for 15 and so on?
I try to figure out if your formula works.

(For native speakers: Is it 'Have you tried…' or 'Did you try…' in this
case?)

Rate this post
 0 ▲ useful ▼ not useful
Hi,

>> It does not seem to work for other dividers
>
> Have you tried n=5 for 31, n=4 for 15 and so on?
> I try to figure out if your formula works.

Yes, it seems that it does not work with other dividers. There exist
"one-off" errors. I might give it a shot for (hopefully branchless)
fix/correction for all dividers of the 2^n-1 form. Not sure if this is
possible.

Best regards

> (For native speakers: Is it 'Have you tried…' or 'Did you try…' in this
> case?)

: Edited by User

Rate this post
 0 ▲ useful ▼ not useful
I just tried it, but I think I have to disappoint you. For example just
try to divide 126 by 63 which is exactly 2. Your formula gives 2.01514
as result, which is 0.76% error. Dividing 126 by 64, which is much
faster than the calculation of your formula, gives 1.96875 which is
1.56% error.

I think either one needs a fast calculation, then he can divide by 64
and accept the error or he needs a exact calculation, then your formula
is not accurate enough.
For higher x-values, the error of dividing by 64 instead of 63 stays
constant, but the error of your formula grows. Dividing 504(=8*63) gives
an error of 1.79%.
So one can say, your formula has better accuracy for smaller numbers,
but since it only works for integers or fixed point arithmetics, the
rounding-erros are much higher.

Rate this post
 0 ▲ useful ▼ not useful
Hi

> I just tried it, but I think I have to disappoint you. For example just
> try to divide 126 by 63 which is exactly 2. Your formula gives 2.01514
> as result, which is 0.76% error. Dividing 126 by 64, which is much
> faster than the calculation of your formula, gives 1.96875 which is
> 1.56% error.

there is nothing to be disappointed about. This is an intentional
formula for software integer division, i.e. truncating division. So it
does int->int mappings for the quotient.

I am not targeting calculations where the fractional part plays a
significant part.

Best regards
http://www.nkavvadias.com

Rate this post
 0 ▲ useful ▼ not useful
I know, but dividing by 64 (and adding 1 for correct rounding) is still
much faster and not less accurate.

Rate this post
 0 ▲ useful ▼ not useful
>> I just tried it, but I think I have to disappoint you. For example just
>> try to divide 126 by 63 which is exactly 2. Your formula gives 2.01514
>> as result, which is 0.76% error.

I agree that there are unoptimized calculations such as this one but for
truncated division, any calculation is correct for the 63 and 127
divisors.

x=126 happens to be n<<1 for n=6=>k=2^n-1=63. x is anyway treated as the
variable/unknown: only n is known and I what I want to do is calculate
in a divisionless and multiplierless way.

Was scavenging some old notes of mine and recovered this algo. Seems I
can claim it as back as May 16, 2011.

Rate this post
 0 ▲ useful ▼ not useful
Dussel wrote:
> I know, but dividing by 64 (and adding 1 for correct rounding) is still
> much faster and not less accurate.

But only for x in the range from 63 to 8000.

Without formal proof im am also skeptical about Nikolaos formala. At
least he should provide a range for x values it has been testet.

Rate this post
 0 ▲ useful ▼ not useful
Dear Lattice User wrote:

> Without formal proof im am also skeptical about Nikolaos formala. At
> least he should provide a range for x values it has been testet.

Thank you for your skeptical view.

Indeed my formula works only for dividends x that are: x <= (2^(2*n)) -
1.

However, it seems to work for any divisor!!! I've tested all divisors
from 2 to 8.

E.g. for n = 6, the divisor is 2^n - 1 = 63. The formula will work for x
<= 4095 = (2^(2*n)) - 1. It will produce one-off errors for certain x >=
4096. But it will be correct for the "small" x values.

I had devised the hack via "algorithmic sketching". I mean that I had
started from a basic formula with some "holes" in it. The holes where
small constants or operators. There exist such techniques in academia,
put more nicely; sometimes called algorithmic sketching, combinatorial
sketching, etc. Essentially is about devising algorithmic sketches
(incomplete algorithms with wildcards) and then use a mechanism to fill
the gaps.

I don't seem to find my step-by-step notes.

My test program is here:

 1 #include  2 #include  3 #include  4 5 /* main:  6  */  7 int main(void)  8 {  9  int qapprox, qexact;  10  int i, j, k;  11 12  for (i = 2; i < 8; i++) {  13 // for (j = 1; j < 4096; j++) {  14  for (j = 1; j < ((1<>i)+j+((1<>i)-1;  17  qexact = j / k;  18  if (qapprox != qexact) {  19  fprintf(stderr, "qapprox = (%d/%d) = %d\tqexact = (%d/%d) = %d\n",  20  j, k, qapprox, j, k, qexact);  21  }  22  }  23  }  24  return 0;  25 } 

Best regards
http://www.nkavvadias.com

Rate this post
 0 ▲ useful ▼ not useful
I am sorry, please find attached correct version of the test program and
correct range for x.

Also, the range for x is [0,2^(2*n)-2], i.e. for n = 6, the range is
0:4094.

 1 #include  2 #include  3 #include  4 5 /* main:  6  */  7 int main(void)  8 {  9  int qapprox, qexact;  10  int i, j, k;  11 12  for (i = 2; i < 8; i++) {  13  for (j = 1; j < (1<>i)+j+((1<>i)-1;  16  qexact = j / k;  17  if (qapprox != qexact) {  18  fprintf(stderr, "qapprox = (%d/%d) = %d\tqexact = (%d/%d) = %d\n",  19  j, k, qapprox, j, k, qexact);  20  }  21  }  22  }  23  return 0;  24 } 

Rate this post
 0 ▲ useful ▼ not useful
Lattice User wrote:
> Dussel wrote:
>> I know, but dividing by 64 (and adding 1 for correct rounding) is still
>> much faster and not less accurate.
>
> But only for x in the range from 63 to 8000.
>
BTW This is wrong, Dussels formula gives 2015 wrong results in the range
0 .. 4095

Rate this post
 0 ▲ useful ▼ not useful
Lattice User wrote:
> Dussels formula gives 2015 wrong results in the range
> 0 .. 4095
You are right. I tested it.
But I'll try to find a better solution ;-)

Rate this post
 0 ▲ useful ▼ not useful
Did anybody notice that this is in C-language and has been posted in the
VHDL area?

Anyway I do not see any advantage in this equations especially not since
both dividers are close to a binary number and the given transformation
of a binary division is simple, like e.g.

x/127  =  x/128 * 128/127  =  x/128 + x/128/127 ....

= x/128 + x/16256 ....
= x/128 + x/128/128 + x/128/128/128

and so on, and so on

> I believe I have invented a formula for quotient calculation that works
Me too :-)

When I started computer game programming in 1980, I realized I did not
have any divider at all in my poor 6502 and also no time with the only
2MHz to perform divisions. Therefore I sat down and wrote a document
covering most of the required divisions for gaming (like 10,60,3600 for
times and 100,1000, for lengths and also some values for conversion of
american fahrenheit temperatures to german degrees. I even found a
simple definition for PI and the irrational relation of music note
distances of 185/196.

All worked with such sequences of adders and shift divisions.

They where found intuitively by try and error method, because I was 12
years of age and did not have enough maths in school so far. Later they
told me about Restklassen (modulo), Taylor Sequences and similar things.

Once you understood the story behind this, it is easy to find tons of
abstractions of division and indirect division, and with vhdl they are
sometimes incredibly fast.

: Edited by User

Rate this post
 0 ▲ useful ▼ not useful
Jürgen Schuhmacher wrote:
> I even found a simple definition for PI and the irrational
> relation of music note distances of 185/196.
Me I am searching for a simple way to create sine waves from y = (pi * 2
* w) with variable w ("omega").

• $formula (LaTeX syntax)$