# Forum: FPGA, VHDL & Verilog divide by 3 in vhdl

Rate this post
 -1 ▲ useful ▼ not useful
hi
i want to know how to divide by 3 in vhdl

:

Rate this post
 1 ▲ useful ▼ not useful
Divide what exactly?

Time? A clock? An integer? signed/unsigned? Some wierd float? Some
standard float? Divide bread? Designs in functions?

I think you got the point.

Rate this post
 0 ▲ useful ▼ not useful
lelo wrote:
> hi
> i want to know how to divide by 3 in vhdl

I suppose you will do that using integer numbers. A divide by three is
nothing more than a multiplication by 0.33333. Therefore you increase
0.33333 by 2**n and multiply your operand by this factor. From your
product you have to use the the digits product'high downto n.

Tom

Rate this post
 0 ▲ useful ▼ not useful
Thomas Reinemann wrote:
> Therefore you increase 0.33333 by 2**n and multiply your operand by
> this factor. From your product you have to use the the digits
> product'high downto n.
In other words for a 16 bit integer:
  result <= (value*(2**16/3))/2**16; 

Rate this post
 0 ▲ useful ▼ not useful
I once found this cyclic definition:

x/4 + x/16 + x/64 + ...

= 0,333333333 x X

Rate this post
 0 ▲ useful ▼ not useful
Or use this from

http://graphics.stanford.edu/~seander/bithacks.html#ModulusDivisionEasy

Compute modulus division by (1 << s) - 1 without a division operator
 unsigned int n; // numerator const unsigned int s; // s > 0 const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...). unsigned int m; // n % d goes here. for (m = n; n > d; n = m) { for (m = 0; n; n >>= s) { m += n & d; } } // Now m is a value from 0 to d, but since with modulus division // we want m to be 0 when it is d. m = m == d ? 0 : m; 

This method of modulus division by an integer that is one less than a
power of 2 takes at most 5 + (4 + 5 * ceil(N / s)) * ceil(lg(N / s))
operations, where N is the number of bits in the numerator. In other
words, it takes at most O(N * lg(N)) time.

: Edited by Moderator

Rate this post
 0 ▲ useful ▼ not useful
Detlef _a wrote:
> for (m = n; n > d; n = m)
> {
>     for (m = 0; n; n >>= s)
Hopefulley lelo (Guest) doesn't try to do this in real hardware. The
variable end of the first loop will not even work in VHDL...

: Edited by Moderator

Rate this post
 0 ▲ useful ▼ not useful
Lothar Miller wrote:
> Detlef _a wrote:
>> for (m = n; n > d; n = m)
>> {
>>     for (m = 0; n; n >>= s)
> Hopefulley lelo (Guest) doesn't try to do this in real hardware. The
> variable end of the first loop will not even work in VHDL...

No, not in this form. I quoted a C-program, you can transfer the algo to
VHDL, for ex. with a state machine.

Is there anything you cant do with VHDL? I'm not an expert in VHDL, but

Cheers
Detlef

: Edited by User

Rate this post
 0 ▲ useful ▼ not useful
Detlef _a wrote:
> Is there anything you cant do with VHDL? I'm not an expert in VHDL, but
> the answer must be 'No'.

The question is not, can you do it or not. The question is the cost.

When you write software, your costs are: code size, requried memory and
execution time.

When you describe hardware, your costs are: required logic elements,
power consumption and latency.

A solution that is cheap in software could be expensive in hardware and
vice versa.

Rate this post
 0 ▲ useful ▼ not useful
Detlef _a wrote:
> Is there anything you cant do with VHDL?
> I'm not an expert in VHDL, but the answer must be 'No'.
Why must the answer be 'No'?

Rate this post
 0 ▲ useful ▼ not useful
Ok, messed up this one. lelo wanted a division by 3, my post was about
modulus division :-(

http://www.hackersdelight.org/divcMore.pdf

and comes with only shifts and addition and without variable count loops
;-)

That comes in handy, you VHDL gurus, right? (but still its C language
though)

Cheers
Detlef

PS:
>> Is there anything you cant do with VHDL?
>> I'm not an expert in VHDL, but the answer must be 'No'.
>Why must the answer be 'No'?

Because VHDL is turing-complet, hopefully.

unsigned int n=33333;                      // numerator
unsigned q, r;

q = (n >> 2) + (n >> 4); // q = n*0.0101 (approx).
q = q + (q >> 4); // q = n*0.01010101.
q = q + (q >> 8);
q = q + (q >> 16);
//printf("%d \n",q ); // Returning q + r/3.
//r = n - q*3; // 0 <= r <= 15.
r = n-(q<<1)-q; // 0 <= r <= 15.
//r=q + ((11*r) >> 5);
r=q + (((r<<3)+(r<<1)+r) >> 5);
printf("%d \n",r); // Returning q + r/3.
// return q + (5*(r + 1) >> 4); // Alternative 1.
// return q + ((r + 5 + (r << 2)) >> 4);// Alternative 2.
return;

: Edited by User

Rate this post
 0 ▲ useful ▼ not useful
you#re mixing up things. If you can write it in VHDL it does not mean
you can built a efficent FPGA design from it.

Of course you can write an SOFT-CPU in VHDL, implement an FPGA with it
and programm the core in C - but thats rather inefficient.

Best regards,

Rate this post
 0 ▲ useful ▼ not useful
Detlef _a wrote:
> PS:
>>> Is there anything you cant do with VHDL?
>>> I'm not an expert in VHDL, but the answer must be 'No'.
>> Why must the answer be 'No'?
> Because VHDL is turing-complet, hopefully.
Of course you can do anything in VHDL. You also can drive in a screw
with a hammer. Its a fairly inefficient way, not always leading to the
best result, but of course you can...

To get good results (=small and fast) you must use algorithms that can
be implemented on Hardware in an efficient way (try google translator,
its german):
http://www.lothar-miller.de/s9y/archives/67-Vektor-nach-BCD-kombinatorisch.html
http://www.lothar-miller.de/s9y/archives/34-Vektor-nach-BCD.html
http://www.lothar-miller.de/s9y/archives/78-Bubblesort.html
http://www.lothar-miller.de/s9y/archives/89-BCD-nach-Binaer-wandeln.html

: Edited by Moderator

Rate this post
 0 ▲ useful ▼ not useful
Lothar Miller wrote:
> Thomas Reinemann wrote:
>> Therefore you increase 0.33333 by 2**n and multiply your operand by
>> this factor. From your product you have to use the the digits
>> product'high downto n.
> In other words for a 16 bit integer:     result <=
> (value*(2**16/3))/2**16;

it can be implemented also