Thread: modulo 2 modulus

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    7

    modulo 2 modulus

    I'm having trouble writing a modulo 2 modulus function. I need to divide a 260 byte unsigned integer by a 4 byte unsigned integer without carrying bits (modulo 2) and return the remainder. Currently I'm using loops to perform bitshift and logical operations and I'm thinking it might be cleaner if I wrote separate functions for performing binary operations on arbitrarily large amounts of data. The reason why I know my function isn't currently working is that if I divide a dividend by a divisor, then add the remainder to the dividend and divide again, the second remainder is not zero. I would appreciate some help getting this function working.

    My current function is:
    Code:
    char *divide(char *message, char *divisor, char *remainder)
    {
            unsigned int *poly=divisor;
            unsigned int *result=remainder;
            int i, j;
    
            for (i=0; i<260; i++)
            {
                    for (j=7; j>=0; j--)
                    {
                            int action=(*result>>31)&1;
                            *result<<=1;
                            *result|=(*(message+i)>>j)&1;
                            *result^=action*i;
                    }
            }
    
            for (i=0; i<32; i++)
            {
                    int action=(*result>>31)&1;
                    *result<<=1;
                    *result^=action*i;
            }
    
            unsigned int temp=(1<<31)-1;
    
            return (*result & temp);
    
    }
    In case it helps, I uploaded my whole source to show some context.

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    7
    I changed it to cpp so that I could use booleans and wrote this:
    Code:
    char *divide(char *message, char *divisor, char *remainder)
    {
            unsigned int result=*((unsigned int*)message);
            const unsigned int div=*((unsigned int*)divisor);
            bool *p=(bool*)(message+32);
            int i=2048;
    
            while (i--)
            {
                    if (result>div)
                    {
                            result^=div;
                    }
    
                    result<<1;
                    result+=*(p++);
            }
    
            *((unsigned int*)remainder)=result;
    
            return remainder;
    }
    but it still isn't comming out with a zero remainder.

  3. #3
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    Could I have some comments?
    Also is char *message the dividend?

    If you want I could slap together some pseudo-code to work with numbers as strings and a basic algorithm some hardware uses to divide numbers.

    Finally what do you mean by carry? Do you mean you can't save the msb of a string you are shifting left?

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I changed it to cpp so that I could use booleans
    You can do that in C (C99), too. Just use _Bool instead of bool or include <stdbool.h> and use bool as before.

    In C89, you can use this code:
    Code:
    typedef enum {false, true} bool;
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    7

    binary arithmatic

    Thanks for the thing about stdbool.h, I hadn't heard of it before. I think my problem is that I'm not understanding how to properly do modulo 2 division. The idea is that since we are concerned about bits, we do not carry when we do arithmatic. So instead of addition or subtraction, we use XOR. I want to be able to check for errors in a message that I send so I want to divide the bits of the message (*message is the dividend), add the remainder and divide again. If the remainder is 0 then I know the message sent without errors. I am having trouble writing a function that can divide the message by a divisor using binary arithmatic (modulo 2). If anyone knows some sort of sudo-code for this type of function, to divide a message by a divisor, it would help a lot.

    Currently running the program looks like this:
    message: 61736466000000000000000000.....
    divisor: 37000000
    remainder: ffffff9a506566
    message: 61736466000000000000000000.....ffffff9a506566
    remainder: ffffffc14b6566

    if this were working properly, the second remainder should have been 0.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    *((unsigned int*)remainder)=result;
    Why not pass remainder as an unsigned int * instead of casting it? My compiler gives a warning about that, something like "use of casts in lvalues is deprecated".
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 06-01-2008, 07:47 AM
  2. modulus operator with double operands?
    By chickenandfries in forum C Programming
    Replies: 7
    Last Post: 03-28-2008, 07:21 AM
  3. modulo 2 division question help
    By shaq8u in forum C Programming
    Replies: 9
    Last Post: 08-20-2003, 08:37 AM
  4. Floating-point modulus
    By Sang-drax in forum C++ Programming
    Replies: 3
    Last Post: 10-01-2002, 08:20 PM
  5. using modulus & weighting factors
    By task in forum C Programming
    Replies: 4
    Last Post: 09-11-2002, 05:52 PM