Thread: Faster bitwise operator

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by iMalc View Post
    That at first seemed like a great idea, and would work for people who have implemented something where each decimal digit is stored in an int or something wasteful like that, but it wont work for a "wasteless" implementation where the bigint is an array of unsigned longs. The reason being that the result of the subtraction would have to range from 0xFFFFFFFFU - 0 to 0 - 0xFFFFFFFFU. So that's -0xFFFFFFFF to +0xFFFFFFFF, requring an extra bit, as well as casting to a signed datatype. Of course it will work if you cast both to a larger datatype first, however I imagine the efficiency will then come out about the same as the original way I posted. Well, maybe still a little ahead if you're lucky.
    Ah, ok. I still think you can optimize the bad [many same bytes before the first difference] case by using a technique similar to strcmp - compare for equality, and once you found a difference, compare for greater/lesser. The good case is probably not that bad either way (and of course, if the compiler is clever, it will only do ONE compare and three different jump instructions).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #17
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    That 'splains it, thanks.
    Yeah, iMalc is right on about how my bignum class was preforming the comparisons.

    So I understand that for all intents and purposes, they're the same.
    But... the reason the computer can only process at a certain speed in the first place is due to the speed limit of electrical conduction. So... in theory, one may be zetascopicly faster than the other within the logic gates that the processor uses. Now, I know this is very irrelevent at this point, But I'm just really curious now.

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Yarin View Post
    That 'splains it, thanks.
    So... in theory, one may be zetascopicly faster than the other within the logic gates that the processor uses.
    Well yeah except that all modern CPUs are synchronous which means that the reading of data from anything is timed with the CPU clock signal, so even if the right transistors are on or off a fraction faster, the value isn't read out until the clock pulse comes along. Thus the two will actually take the same amount of time.

    In an asychronous CPU the two cases could actually take different amounts of time, but you're unlikely to be programming for such a device anytime soon.
    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"

  4. #19
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    2,158
    Understood - thanks for the info.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Smart pointer class
    By Elysia in forum C++ Programming
    Replies: 63
    Last Post: 11-03-2007, 07:05 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. C bitwise operator exercise - more like newb killer
    By shdwsclan in forum C Programming
    Replies: 3
    Last Post: 02-22-2006, 07:02 AM
  4. operator overloading and dynamic memory program
    By jlmac2001 in forum C++ Programming
    Replies: 3
    Last Post: 04-06-2003, 11:51 PM
  5. Replies: 5
    Last Post: 10-30-2002, 10:23 PM