modulo of any number

Discussion in 'VHDL' started by Tim, Jan 5, 2007.

  1. Tim

    Tim Guest

    I want to do the following

    addr mod 320

    but because the base is not a factor of 2^x, it's not synthesizable.
    What's the optimum way of performing this calculation? The easiest but
    computationally expensive way would be

    while temp>=320 loop
    temp <= input - 100;
    end loop;
    output <= temp;

    but I'm certain there's a better way but just don't know what.


    Thanks,

    Tim
     
    Tim, Jan 5, 2007
    #1
    1. Advertising

  2. Tim

    Tim Guest

    > while temp>=320 loop
    > temp <= input - 100;
    > end loop;
    > output <= temp;


    This is what i meant:

    while temp>=320 loop
    temp <= input - 320;
    end loop;
    output <= temp;

    I'm still pulling my hair out trying to find some solutions. So far,
    I've uncovered some ideas,

    http://groups.google.com/group/comp...39?lnk=gst&q=modulus &rnum=4#197c317b3263e139

    In particular, Allan Heriman's post on Mon, Feb 14 2005 11:28 pm. It
    seems that if you require a mod N function, you can split it up such
    that mod N = mod a * mod b, where a is 2^n and b is 2^n-1? In which
    case, could I use mod 320 = mod 64 * mod 5 or have I completely
    misunderstood the posters intention? If someone could clarify that or
    come up with any other ideas, I'd be grateful.

    I should also mention that addr is a signal ranging from 0 to 76799, a
    17 bit slv. The divisor, 320 is a constant.
     
    Tim, Jan 5, 2007
    #2
    1. Advertising

  3. Tim

    Ben Jones Guest

    Hi Tim,

    "Tim" <> wrote in message
    news:...
    >> while temp>=320 loop
    >> temp <= input - 100;
    >> end loop;
    >> output <= temp;

    >
    > This is what i meant:
    >
    > while temp>=320 loop
    > temp <= input - 320;
    > end loop;
    > output <= temp;
    >
    > I should also mention that addr is a signal ranging from 0 to 76799, a
    > 17 bit slv. The divisor, 320 is a constant.


    In general there is no one right answer to this. The simplest way is just a
    step up from the method you identified above. Start by comparing the input
    against in your case 128x320 = 40960, subtracting 40960 if it is greater.
    Then compare the result of that to 40960/2 = 20480, subtracting 20480 if it
    is greater. Carry on dividing down and comparing against 10240, 5120, 2560,
    1280, 640 and finally 320. That way it will take you exactly 8
    compare-subtract operations to reduce the address down to the range 0-319.

    This method is fairly cheap in terms of circuitry, but has relatively high
    latency. It has the advantage that it's pretty easy to implement, in either
    an iterative (resource-shared) circuit or a pipelined version (for maximum
    throughput).

    What are your latency and throughput requirements for this operation?

    Cheers,

    -Ben-
     
    Ben Jones, Jan 5, 2007
    #3
  4. Tim

    jens Guest

    A slightly different way (no iteration, requires two multiplications
    and a subtraction):

    addr mod 320 = addr - 320 * ( ( addr * const1 ) / const2 )

    where
    const1 = round( 2^N / 320 )
    const2 = 2^N
    N needs to be large enough to handle the largest possible value of
    addr,
    const1 can probably be tweaked a little bit to reduce the value of N.
     
    jens, Jan 5, 2007
    #4
  5. Tim

    Arnim Guest


    > I want to do the following
    >
    > addr mod 320
    >
    > but because the base is not a factor of 2^x, it's not synthesizable.


    I once started a design for Cyclone chips using QuartusII and the tool
    happily synthesized a '<signed> mod 6' expression, fooling me into
    thinking that this is common with modern tools. As the design was ported
    to Spartan3 lateron, I was in deep sh*t when XST choked at the same code.

    The following function is my contribution to this topic. Just a looped
    generation of a look-up table. Might be easily parametrized to accept
    other mods than 6.
    QuartusII even yielded lower LUT count with this code than with the
    original 'mod 6'.

    -- Function mod_6_f
    --
    -- Purpose:
    -- Calculate the modulo of 6.
    -- Only the positive part is considered.
    --
    function mod_6_f(val : in hv_t) return hv_t is
    variable mod_v : natural;
    variable result_v : hv_t;
    begin
    if val(hv_t'left) = '0' then
    result_v := (others => '0');
    mod_v := 0;
    for idx in 0 to 255 loop
    if val = idx then
    result_v := to_signed(mod_v, hv_t'length);
    end if;

    if mod_v < 5 then
    mod_v := mod_v + 1;
    else
    mod_v := 0;
    end if;
    end loop;
    else
    result_v := (others => '-');
    end if;

    return result_v;
    end;
     
    Arnim, Jan 5, 2007
    #5
  6. Tim wrote:
    > I want to do the following
    >
    > addr mod 320
    >
    > but because the base is not a factor of 2^x, it's not synthesizable.
    > What's the optimum way of performing this calculation? The easiest but
    > computationally expensive way would be
    >
    > while temp>=320 loop
    > temp <= input - 100;
    > end loop;
    > output <= temp;
    >
    > but I'm certain there's a better way but just don't know what.
    >

    From Wikipedia (art. "multiplicative inverse"):
    > In modular arithmetic, the multiplicative inverse of x is also defined: it is the number a such that (a·x) mod n = 1. However, this multiplicative inverse exists only if a and n are relatively prime. For example, the inverse of 3 modulo 11 is 4 because it is the solution to (3x) mod 11 = 1. The extended Euclidean algorithm may be used to compute the multiplicative inverse modulo of a number.
    >

    Since (2^17 - 1) is prime, it follows that (2^17 -1) and 320 are
    relatively prime. Hence a multiplicative inverse is defined in this case.
    Given that, you can multiply by that inverse (many FPGAs feature a
    hardware multiplier) to implement the division. You then multiply the
    quotient by 320 (same multiplier?) & subtract from the original number
    to get the remainder.
    This method has the advantage (may not be relevant in your case) of a
    constant execution time.
     
    David R Brooks, Jan 5, 2007
    #6
  7. In article <>, Tim
    <> wrote:

    > I want to do the following
    >
    > addr mod 320
    >
    > but because the base is not a factor of 2^x, it's not synthesizable.
    > What's the optimum way of performing this calculation? The easiest but
    > computationally expensive way would be
    >
    > while temp>=320 loop
    > temp <= input - 100;
    > end loop;
    > output <= temp;
    >
    > but I'm certain there's a better way but just don't know what.


    As you pointed out :

    addr mod 320 = 64 * (addr/64 mod 5) + (addr mod 64)

    The only hard part is mod 5

    --
    David M. Palmer (formerly @clark.net, @ematic.com)
     
    David M. Palmer, Jan 6, 2007
    #7
  8. Tim

    Tim Guest

    Thanks for all the ideas! After reading through your responses, I've
    decided to go with jens algorithm. I have no idea why it works but
    following D. Brooks post, I'll look it up on wikipedia.

    > What are your latency and throughput requirements for this operation?


    I don't have performance requirements per se as I am trying to get it
    working for starters. Obviously, the faster the better though.
     
    Tim, Jan 7, 2007
    #8
  9. Tim

    Tim Guest

    jens wrote:
    > A slightly different way (no iteration, requires two multiplications
    > and a subtraction):
    >
    > addr mod 320 = addr - 320 * ( ( addr * const1 ) / const2 )
    >
    > where
    > const1 = round( 2^N / 320 )
    > const2 = 2^N
    > N needs to be large enough to handle the largest possible value of
    > addr,
    > const1 can probably be tweaked a little bit to reduce the value of N.


    I must be doing something wrong becuase my calculations are not
    yielding the right remainder!
    This is my working:

    const1 = round(2^17/320) = 409.6 ~= 410
    const1 = 2^17 = 131 072

    Now, if I substitute the address 321, the remainder should be 1 as 321
    mod 320 = 1.
    But,
    addr - 320 * ( ( addr * const1 ) / const2 ) = 321 - 320 * ( ( 321 * 410
    ) / 131 072 )
    = 0.313 which is not remainder 1...

    Can someone tell me what's wrong?
     
    Tim, Jan 8, 2007
    #9
  10. Tim

    jens Guest

    > Now, if I substitute the address 321, the remainder should be 1 as 321
    > mod 320 = 1.
    > But,
    > addr - 320 * ( ( addr * const1 ) / const2 ) = 321 - 320 * ( ( 321 * 410
    > ) / 131 072 )
    > = 0.313 which is not remainder 1...
    >
    > Can someone tell me what's wrong?


    Sorry, I was a little vague on the divide operation- it's actually a
    shift right by N, so you would lose the fraction, and the result of the
    "divide" is 1, then 321 mod 320 = 1.

    A spreadsheet is a good way to simulate this, optimize N and tweak the
    constants, and verify every required value.
     
    jens, Jan 8, 2007
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Christian Kruggel

    General modulo-question

    Christian Kruggel, Jul 7, 2003, in forum: Java
    Replies:
    1
    Views:
    451
    Brad BARCLAY
    Jul 7, 2003
  2. Replies:
    1
    Views:
    667
    Darryl L. Pierce
    May 20, 2004
  3. Tjerk Wolterink

    [xsl] sort & modulo

    Tjerk Wolterink, Apr 21, 2005, in forum: XML
    Replies:
    3
    Views:
    573
    Dimitre Novatchev
    Apr 22, 2005
  4. silentlights

    Fast Division/Modulo Operation

    silentlights, Apr 16, 2004, in forum: C Programming
    Replies:
    8
    Views:
    997
    Dik T. Winter
    Apr 23, 2004
  5. Griff

    Problems using modulo

    Griff, Apr 19, 2004, in forum: Python
    Replies:
    5
    Views:
    396
    Diez B. Roggisch
    Apr 20, 2004
Loading...

Share This Page