EmbDev.net

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


Author: Nikolaos Kavvadias (Company: http://www.nkavvadias.com) (nikolaos_k)
Posted on:

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
Nikolaos Kavvadias
http://www.nkavvadias.com
http://github.com/nkkav/

Author: Dussel (Guest)
Posted on:

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?)

Author: Nikolaos Kavvadias (Company: http://www.nkavvadias.com) (nikolaos_k)
Posted on:

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
Nikolaos Kavvadias
http://www.nkavvadias.com

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

: Edited by User
Author: Dussel (Guest)
Posted on:

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.

Author: Nikolaos Kavvadias (Company: http://www.nkavvadias.com) (nikolaos_k)
Posted on:

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
Nikolaos Kavvadias
http://www.nkavvadias.com

Author: Dussel (Guest)
Posted on:

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.

Author: Nikolaos Kavvadias (Company: http://www.nkavvadias.com) (nikolaos_k)
Posted on:

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.

Author: Lattice User (Guest)
Posted on:

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.

Author: Nikolaos Kavvadias (Company: http://www.nkavvadias.com) (nikolaos_k)
Posted on:

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:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* main:
 */
int main(void)
{
  int qapprox, qexact;
  int i, j, k;

  for (i = 2; i < 8; i++) {
//    for (j = 1; j < 4096; j++) {
    for (j = 1; j < ((1<<i)-1)*((1<<i)-1); j++) {
      k = (1<<i) - 1;
      qapprox = (((j>>i)+j+((1<<i)+1))>>i)-1;
      qexact  = j / k;
      if (qapprox != qexact) {
        fprintf(stderr, "qapprox = (%d/%d) = %d\tqexact = (%d/%d) = %d\n",
          j, k, qapprox, j, k, qexact);
      }
    }
  }
  return 0;
}

Best regards
Nikolaos Kavvadias
http://www.nkavvadias.com

Author: Nikolaos Kavvadias (Company: http://www.nkavvadias.com) (nikolaos_k)
Posted on:

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.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* main:
 */
int main(void)
{
  int qapprox, qexact;
  int i, j, k;

  for (i = 2; i < 8; i++) {
    for (j = 1; j < (1<<i)*(1<<i)-1; j++) {
      k = (1<<i) - 1;
      qapprox = (((j>>i)+j+((1<<i)+1))>>i)-1;
      qexact  = j / k;
      if (qapprox != qexact) {
        fprintf(stderr, "qapprox = (%d/%d) = %d\tqexact = (%d/%d) = %d\n",
          j, k, qapprox, j, k, qexact);
      }
    }
  }
  return 0;
}

Author: Lattice User (Guest)
Posted on:

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

Author: Dussel (Guest)
Posted on:

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 ;-)

Author: Jürgen S. (engineer)
Posted on:

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
Author: Hobbyorganist (Guest)
Posted on:

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.
Can you tell more about this, please?
Me I am searching for a simple way to create sine waves from y = (pi * 2 
* w) with variable w ("omega").

Reply

Entering an e-mail address is optional. If you want to receive reply notifications by e-mail, please log in.

Rules — please read before posting

  • Post long source code as attachment, not in the text
  • Posting advertisements is forbidden.

Formatting options

  • [c]C code[/c]
  • [avrasm]AVR assembler code[/avrasm]
  • [vhdl]VHDL code[/vhdl]
  • [code]code in other languages, ASCII drawings[/code]
  • [math]formula (LaTeX syntax)[/math]




Bild automatisch verkleinern, falls nötig
Note: the original post is older than 6 months. Please don't ask any new questions in this thread, but start a new one.