Division by ten with magic numbers

This is a discussion on Division by ten with magic numbers within the C Programming forums, part of the General Programming Boards category; Hi everybody. While I was experimenting a little with magic number to perform a division with the method Malcom explained ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    182

    Division by ten with magic numbers

    Hi everybody.

    While I was experimenting a little with magic number to perform
    a division with the method Malcom explained in another post ===> Look Here
    and that I quote here for your convenience:
    In case anyone wants more information on how I've performed divisions using multiply and shift. The theory is that instead of doing answer = x / y you are doing answer = ((x << n) / y) >> n (the shifts logically cancel out). Rewritting the shift as a multiply by a power of two answer = (x * 2^n / y) >> n and all I'm doing is pre-calculating 2^n / y. From there it's simply a matter of picking a large enough n whilst avoiding overflow, and making sure you round up.
    Take this (num2*5243)>>19 it performs a divide by 100 for any number up to 10000...

    To pick those magic numbers I first picked a power of two that was large enough that when divided by the divisor it was at least half as big as the number I want to support and that when multiplied by answer, doesn't exceed 2^32
    2^19 = 524288
    divide by divisor -> 524288 / 100 = 5242.88 -> 5243 (rounding up) (at least half as big as 10000 - check)
    multiplied by quotient -> 5243 * 10000 = 52430000 (less than 2^32 - check)

    I could instead have picked 2^20 giving (num2*10486)>>20
    2^20 = 1048576
    divide by divisor -> 1048576/ 100 = 10485.76 -> 10486 (rounding up) (at least half as big as 10000 - check)
    multiplied by quotient -> 10486 * 10000 = 104860000 (less than 2^32 - check)
    I was wondering about the use of C99 long long unsigned and the possibility to use
    this data type to perform division by multiplication of bigger numbers than those we can
    handle with 32 bit integers.

    Anybody has some experience about this matter?

    If we use long long integers or unsigned the following code to perform
    a division by ten can handle bigger numbers providing a bigger magic number and
    the relative shift?

    Code:
          div = (num1 * 6554UL) >> 16;
          remain = num1 - div * ten;
    The above code can handle division by multiplication of numbers not bigger than 99,999.

    Any help would be very appreciated.
    Last edited by frktons; 07-16-2010 at 05:43 AM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    I think that code only worked up to around 16384 for the divisor, so I was using it for up to 9999. I'm pretty sure it doesn't work correctly for 99999.

    The main difference between using a 64-bit data type and letting the compiler perform the same optimisation itself, is for an x86 program the assembly code can perform the multiplication one two 32-bit numbers to produce the 64-bit result. Whereas to get a 64-bit result from C or C++, you have to start with a 64-bit data type, so in effect it becomes a 64-bit x 64-bit multiplication, which isn't so easily handled by the 32-bit processor.

    This is just one of those cases where the higher-level lanaguage doesn't allow you to specifiy things that map directly to the relevant assembly. Another example is performing a bit-rotate. Processors have an instruction for that, but to do it in C requires two shifts and an or.
    It's one of those things that's really best left for assembly language coding, but you can do it in C if you make some compromise.
    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"

  3. #3
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by iMalc View Post
    I think that code only worked up to around 16384 for the divisor, so I was using it for up to 9999. I'm pretty sure it doesn't work correctly for 99999.

    The main difference between using a 64-bit data type and letting the compiler perform the same optimisation itself, is for an x86 program the assembly code can perform the multiplication one two 32-bit numbers to produce the 64-bit result. Whereas to get a 64-bit result from C or C++, you have to start with a 64-bit data type, so in effect it becomes a 64-bit x 64-bit multiplication, which isn't so easily handled by the 32-bit processor.

    This is just one of those cases where the higher-level lanaguage doesn't allow you to specifiy things that map directly to the relevant assembly. Another example is performing a bit-rotate. Processors have an instruction for that, but to do it in C requires two shifts and an or.
    It's one of those things that's really best left for assembly language coding, but you can do it in C if you make some compromise.
    Yeah, you are right. In this case it is even easier to do in Assembly than in C.
    We are coding in standard C99, so let's Assembly stay away from the thread.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 02-19-2009, 06:19 PM
  2. Random number + guessing game trouble
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-08-2007, 03:33 AM
  3. Stone Age Rumble
    By KONI in forum Contests Board
    Replies: 30
    Last Post: 04-02-2007, 09:53 PM
  4. Perfect number...
    By Argo_Jeude in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 01:53 PM
  5. magic number
    By andygales in forum C++ Programming
    Replies: 8
    Last Post: 04-05-2005, 04:15 AM

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