module without using %

This is a discussion on module without using % within the C++ Programming forums, part of the General Programming Boards category; I remember there is a way to calculate the remainder without using the % operator but cant seem to find ...

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    330

    module without using %

    I remember there is a way to calculate the remainder without using the % operator but cant seem to find it. Anyone knows what it was?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Divide, and subtract (quotient*divisor)?

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    40
    In what situation do you need any other means of getting the remainder than using the "%" ?

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    When you are asked to implement modulus without using %?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    Jan 2007
    Posts
    330
    I just read an implementation of the standard function div() and remembered there was a way without division and % to get the remainder. Was just curious what it was again

  6. #6
    Registered User
    Join Date
    Nov 2007
    Posts
    40
    Without division? I don't see how that's possible, but if it is I'd like to see :P.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    This page shows a way for powers of 2.

    In addition, div() seems to calculate both a/b and a%b. If you have done the first, the modulo can be found without doing the same division again. That is, div() is probably meant for optimizing cases where you need both results.
    Last edited by anon; 01-16-2008 at 10:19 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    int a = 10 ;
    int b = 3 ;
    int remainder = a - ((a/b)*b) ;

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    You can always emulate integer division with subtraction and counting.
    By doing so, you'll get the modulus automatically.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by KIBO View Post
    I just read an implementation of the standard function div() and remembered there was a way without division and % to get the remainder. Was just curious what it was again
    If the number you're dividing by is small enough and is known at compile time, and the number being divided is no larger than half your register size, then to do fast division you can:
    Multiply by the fixed-point inverse of the divisor, and then convert back to an integer. That's a multiply and a shift, instead of a division, making it definitely faster. You wouldn't do this for powers of two though as then you can just use a single shift.
    e.g.
    Code:
    template <unsigned char n>
    unsigned short div(unsigned short x)
    {
        return (int)x * ((0x10000+n-1)/n) >> 16;
    }
    Mod can then be trivially based on this, though there may be a faster way also.
    Code:
    template <unsigned char n>
    unsigned short mod(unsigned short x)
    {
        return x - div<n>(x) * n;
    }
    Note that I'm also assuming that x is positive as I can't be bothered checking the bahviour of negatives, hence use of unsigned to make sure.

    Repeated subtraction until the number is less than the divisior will also work, not that you'd want to do that of course.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Find Injected DLLs In A Process?
    By pobri19 in forum Windows Programming
    Replies: 35
    Last Post: 02-06-2010, 09:53 AM
  2. Touchkit xorg module error
    By thesourcehim in forum Linux Programming
    Replies: 0
    Last Post: 10-06-2008, 07:54 AM
  3. Merge Module Problems
    By mercury529 in forum Windows Programming
    Replies: 0
    Last Post: 11-29-2006, 03:30 PM
  4. Function basics
    By sjleonard in forum C++ Programming
    Replies: 15
    Last Post: 11-21-2001, 12:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21