Thread: Problem with modulo calculation

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    60

    Problem with modulo calculation

    Right, am having a problem when using a modulo calculation in my program.

    Trying to do the calculation below,

    N = 1073741827
    R = 4294967296

    N' = (1/N) (mod R) = 1789569707

    The code I was trying to use is below however it just gives 0 as the result, i'm guessing its something to do with the type but not sure what.
    Code:
    typedef unsigned long long bigint;
    
    void method()
    {
    bigint N, R, invN;
    
    N = 1073741827;
    R = 4294967296;
    invN = (1/N) % R;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > (1/N)
    Integer arithmetic, anything other than 1 here will give you zero
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    60
    Quote Originally Posted by Salem View Post
    > (1/N)
    Integer arithmetic, anything other than 1 here will give you zero
    Yeh I guessed this was the problem, how would I go about anything other type of arithmetic to get the required result.

  4. #4
    Work in Progress..... Jaken Veina's Avatar
    Join Date
    Mar 2005
    Location
    Missouri. Go Imos Pizza!
    Posts
    256
    Not to mention that the solution to that equation is N' = 1/N, not 1789569707...

    N' = (1 / N) % R
    N' = (1 / 1073741827) % R
    N' = (0.00000000093132257201) % R
    N' = (0.00000000093132257201) % 4294967296

    0.00000000093132257201 / 4294967296 = 0 Remainder 0.00000000093132257201

    So, N' = 0.00000000093132257201 = 1 / N

    Somehow, I don't think that's the equation you want...However, for education's sake, a correct implementation of that equation would look something like this...

    Code:
    void method(void)
    {
    double N, R, invN;
    
    N = 1073741827;
    R = 4294967296;
    invN = ((double)1/N) % R;
    }
    Although, there may be problems with precision. I'm not sure off-hand how well a double will be able to deal with such large (and small) numbers.
    Last edited by Jaken Veina; 01-12-2009 at 01:34 PM.
    Code:
    void function(void)
     {
      function();
     }

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I take it you're looking for an inverse mod R? That is, 1073etc * 1789etc is equal to 1 mod 4294etc? That has nothing to do with %. (% is remainder; it does not do artihmetic mod whatever). You will have to actually compute it yourself, using an algorithm of some kind.

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    60
    Quote Originally Posted by tabstop View Post
    I take it you're looking for an inverse mod R? That is, 1073etc * 1789etc is equal to 1 mod 4294etc? That has nothing to do with %. (% is remainder; it does not do artihmetic mod whatever). You will have to actually compute it yourself, using an algorithm of some kind.

    Yes sorry I was so unclear, that was what I wanted to do. In maple you can just type 1/N mod R and it gives the correct answer 1089etc however wasn't sure how to do this in C.

    Does the extended euclidean algorithm do this? and do I enter N and R as the two variables for the function to take?

    thanks for the help

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The extended Euclidean algorithm does indeed do this. N and R are the only two variables you've got, so I suppose those are the two.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  3. Calculation problem....
    By badran in forum C++ Programming
    Replies: 6
    Last Post: 10-17-2006, 04:07 AM
  4. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  5. Trigonometry Sin rule calculation problem
    By Harry in forum C++ Programming
    Replies: 3
    Last Post: 02-06-2006, 12:14 PM