+ Post New Thread
Results 1 to 11 of 11
  1. #1
    Member level 4
    Points: 1,715, Level: 9
    Achievements:
    7 years registered

    Join Date
    Dec 2011
    Posts
    79
    Helped
    0 / 0
    Points
    1,715
    Level
    9

    rem and mod operators

    Hi
    There is a question about synthesizing mod/rem operators.

    X mod N where N is positive:
    This can be synthesized by taking the least log2(N) bits of X.
    X can be positive of negative (2's complement).

    How about negative N numbers?
    For example, 1 mod -4 = -3
    How this is synthesized?

    The same question exists for rem.
    -1 rem 4 = -1
    -1 rem -4 = -1

    •   AltAdvertisement

        
       

  2. #2
    Super Moderator
    Points: 256,712, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    44,787
    Helped
    13620 / 13620
    Points
    256,712
    Level
    100

    Re: rem and mod operators

    Presume you are asking about VHDL. You can review ieee.numeric_std library how mod and rem are evaluated. Both are finally referring to unsigned division DIVMOD(). With power of two denominator, it reduces to shift and mask operation and can be implemented without actual division operation.

    Non power-of-two right hand operand may infer a parallel divider, depending on the tool capabilities.



  3. #3
    Advanced Member level 1
    Points: 2,463, Level: 11

    Join Date
    Aug 2016
    Posts
    425
    Helped
    69 / 69
    Points
    2,463
    Level
    11

    Re: rem and mod operators

    Hi,

    Although it is not clear what you are asking for but I'll just give it a shot.

    A rem B = C:
    in this case C is the remainder after dividing the absolute value of A by the absolute value of B.
    C has the same sign as A irrespective of the sign of B.

    A mod B = C:
    In this case, C is the remainder after dividing the absolute value of A by the absolute value of B.
    C has the same sign as B irrespective of the sign of A.

    I hope that's what you asked for. If not, you may have to rephrase your question for better understanding.
    Last edited by Akanimo; 18th May 2019 at 10:18.
    -------------
    --Akanimo.



  4. #4
    Member level 4
    Points: 1,715, Level: 9
    Achievements:
    7 years registered

    Join Date
    Dec 2011
    Posts
    79
    Helped
    0 / 0
    Points
    1,715
    Level
    9

    Re: rem and mod operators

    Lets say in VHDL we have written while assuming that A and B are bit_vector(7 downto 0)

    A := B mod 4;

    How that is synthesized? Simply mask B with a pattern which is (B AND 000000011). So it is an AND gate.

    Now, I want to know how to synthesize (1 mod -4)? The right hand operand is power of 2.
    If we use an AND gate with absolute value of the negative right operand and then find the 2's complement of the result, then the result is invalid. For example, first we have (1 mod 4) which is (00000001 AND 00000011) which is (00000001) and then complement it to get (11111110) which is (-1) and not -3.

    Can you explain that?



  5. #5
    Super Moderator
    Points: 256,712, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    44,787
    Helped
    13620 / 13620
    Points
    256,712
    Level
    100

    Re: rem and mod operators

    Near. You calculate 1 MOD -4 = (1 MOD 4) - 4 = -3.



    •   AltAdvertisement

        
       

  6. #6
    Advanced Member level 1
    Points: 2,463, Level: 11

    Join Date
    Aug 2016
    Posts
    425
    Helped
    69 / 69
    Points
    2,463
    Level
    11

    Re: rem and mod operators

    Why do you think that 1 mod 4 is synthesised using an AND gate? Try 6 MOD 3 with an AND gate and you won't get 0.

    This is the analytical implication
    MOD:
    A = B*N + (A mod B) where N is a integer and A mod B is as described in pots #3.

    REM:
    A = (A/B)*B + (A rem B); where A rem B is as described in post #3.

    If you are always going to perform (1 mod -4) then leave the operation and take the answer which is -3. Operators are for arbitrary values so all test cases must yield their correct answer with a certain method before you adopt the method.

    - - - Updated - - -

    The best bet would be to use a for loop.
    Last edited by Akanimo; 18th May 2019 at 17:48.
    -------------
    --Akanimo.



  7. #7
    Super Moderator
    Points: 256,712, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    44,787
    Helped
    13620 / 13620
    Points
    256,712
    Level
    100

    Re: rem and mod operators

    As far as I understand, the OP wants to implement MOD operation for power of two denominator. That's of course possible without a divider.



  8. #8
    Advanced Member level 1
    Points: 2,463, Level: 11

    Join Date
    Aug 2016
    Posts
    425
    Helped
    69 / 69
    Points
    2,463
    Level
    11

    Re: rem and mod operators

    Quote Originally Posted by mahmood.n View Post
    Lets say in VHDL we have written while assuming that A and B are bit_vector(7 downto 0)

    A := B mod 4;

    How that is synthesized? Simply mask B with a pattern which is (B AND 000000011). So it is an AND gate.

    Now, I want to know how to synthesize (1 mod -4)? The right hand operand is power of 2.
    If we use an AND gate with absolute value of the negative right operand and then find the 2's complement of the result, then the result is invalid. For example, first we have (1 mod 4) which is (00000001 AND 00000011) which is (00000001) and then complement it to get (11111110) which is (-1) and not -3.

    Can you explain that?
    (1 mod -4) is -1 -------not -3
    (1 mod 4) is 0 remainder 1
    giving that result of 1 the sign of -4 results in -1
    Your method if masking with 00000011 is correct because (1 mod 4) = (00000001 AND 00000011) = (00000001).
    If we take the MSB as the sign bit, then Taking the 2's compement of (00000001) gives (11111110 + 00000001) = (10000001) which is -1.
    -------------
    --Akanimo.



    •   AltAdvertisement

        
       

  9. #9
    Super Moderator
    Points: 256,712, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    44,787
    Helped
    13620 / 13620
    Points
    256,712
    Level
    100

    Re: rem and mod operators

    (1 mod -4) is -1 -------not -3
    My VHDL tool says it's -3, no reason to doubt about. Please review numeric_std.vhd how it's calculated.

    Code VHDL - [expand]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    
    if XL(XL'LEFT)='1' then
          XNUM := UNSIGNED(-XL);
        else
          XNUM := UNSIGNED(XL);
        end if;
        if XR(XR'LEFT)='1' then
          XDENOM := UNSIGNED(-XR);
          RNEG := TRUE;
        else
          XDENOM := UNSIGNED(XR);
        end if;
        DIVMOD(XNUM, XDENOM, FQUOT, FREMAIN);
        if RNEG and L(L'LEFT)='1' then
          FREMAIN := "0"-FREMAIN;
        elsif RNEG and FREMAIN/="0" then
          FREMAIN := FREMAIN-XDENOM;
        elsif L(L'LEFT)='1' and FREMAIN/="0" then
          FREMAIN := XDENOM-FREMAIN;
        end if;
        return SIGNED(FREMAIN);


    Result -3 also fulfills the identity given in post #6:

    A = B*N + (A MOD B)
    1 = -4*-1 + -3



  10. #10
    Advanced Member level 1
    Points: 2,463, Level: 11

    Join Date
    Aug 2016
    Posts
    425
    Helped
    69 / 69
    Points
    2,463
    Level
    11

    Re: rem and mod operators

    Quote Originally Posted by FvM View Post
    My VHDL tool says it's -3, no reason to doubt about. Please review numeric_std.vhd how it's calculated.

    Code VHDL - [expand]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    
    if XL(XL'LEFT)='1' then
          XNUM := UNSIGNED(-XL);
        else
          XNUM := UNSIGNED(XL);
        end if;
        if XR(XR'LEFT)='1' then
          XDENOM := UNSIGNED(-XR);
          RNEG := TRUE;
        else
          XDENOM := UNSIGNED(XR);
        end if;
        DIVMOD(XNUM, XDENOM, FQUOT, FREMAIN);
        if RNEG and L(L'LEFT)='1' then
          FREMAIN := "0"-FREMAIN;
        elsif RNEG and FREMAIN/="0" then
          FREMAIN := FREMAIN-XDENOM;
        elsif L(L'LEFT)='1' and FREMAIN/="0" then
          FREMAIN := XDENOM-FREMAIN;
        end if;
        return SIGNED(FREMAIN);


    Result -3 also fulfills the identity given in post #6:

    A = B*N + (A MOD B)
    1 = -4*-1 + -3
    Yes, you're right. That was me and my blunder. Apologies.

    I noticed something that I'd like you to confirm:
    If A and B bear the same sign, then (A mod B) = (A rem B).
    -------------
    --Akanimo.



  11. #11
    Super Moderator
    Points: 256,712, Level: 100
    Awards:
    1st Helpful Member

    Join Date
    Jan 2008
    Location
    Bochum, Germany
    Posts
    44,787
    Helped
    13620 / 13620
    Points
    256,712
    Level
    100

    Re: rem and mod operators

    If A and B bear the same sign, then (A mod B) = (A rem B).
    Yes, that's true.



--[[ ]]--