generic add with carry

This is a discussion on generic add with carry within the C++ Programming forums, part of the General Programming Boards category; >> You're dismissing it because it sounds too simple, without trying any example. well, to be fair, your original solution ...

  1. #16
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> You're dismissing it because it sounds too simple, without trying any example.

    well, to be fair, your original solution was incomplete. but I can see how the algorithm works, now. quite ingenious.

    on a side note, I really wasn't sure if I would get many useful or intelligent responses from this thread. luckily, I was wrong!

    many thanks to everyone that posted.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #17
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Sorry to resurrect the thread, but I just thought this should be said:
    Code:
    for (int i = 0; i < BIGINTSIZE; ++i) {
    	data[i] += q.data[i] + carry;
    	if (!carry) {
    		carry = (data[i] <  q.data[i]) ? 1U : 0U;
    	} else {
    		carry = (data[i] <= q.data[i]) ? 1U : 0U;
    	}
    }
    Note that you could use this instead, because of what Dave_Sinkula posted:
    Code:
    for (int i = 0; i < BIGINTSIZE; ++i) {
    	data[i] += q.data[i] + carry;
    	if (!carry) {
    		carry = data[i] <  q.data[i];
    	} else {
    		carry = data[i] <= q.data[i];
    	}
    }
    Quote Originally Posted by Dave_Sinkula
    I was trying to avoid branching, I've heard that affects pipelines and such (but it's not my usual arena).
    Not my arena either, but it seems like you might be right:
    The downside of a long pipeline is when a program branches, the entire pipeline must be flushed, a problem that branch predicting helps to alleviate.
    (From http://en.wikipedia.org/wiki/Instruction_pipeline.)

    I'm assuming that flushing a pipeline is a bad thing . . .
    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.

  3. #18
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by dwks View Post
    Sorry to resurrect the thread, but I just thought this should be said:
    Code:
    for (int i = 0; i < BIGINTSIZE; ++i) {
    	data[i] += q.data[i] + carry;
    	if (!carry) {
    		carry = (data[i] <  q.data[i]) ? 1U : 0U;
    	} else {
    		carry = (data[i] <= q.data[i]) ? 1U : 0U;
    	}
    }
    Note that you could use this instead, because of what Dave_Sinkula posted:
    Code:
    for (int i = 0; i < BIGINTSIZE; ++i) {
    	data[i] += q.data[i] + carry;
    	if (!carry) {
    		carry = data[i] <  q.data[i];
    	} else {
    		carry = data[i] <= q.data[i];
    	}
    }

    Not my arena either, but it seems like you might be right:

    (From http://en.wikipedia.org/wiki/Instruction_pipeline.)

    I'm assuming that flushing a pipeline is a bad thing . . .
    Flushing the pipeline is indeed bad.

    However, I doubt that the compiler will actually generate noticably different code for the two pieces of source given.

    --
    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.

  4. #19
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Be extremely careful when judging programs for things like cache coherency, branch efficiency, and similar hardware-level performance issues. Your guess which of two given pieces of code is faster will typically be right 50&#37; of the time. It's extremely hard to predict what will happen, given modern compilers and CPUs.

    In the course about efficient programming I'm taking right now, the teacher is showing us techniques for refactoring code and tools for measuring efficiency. The goal is to use the tools and figure out where and what the problem is, then make an informed guess at a transformation that would alleviate the problem, measure again, make another guess, and so on, until you've found the best way to do it.
    Don't worry, the next generation of CPUs will invalidate all your experiments
    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

  5. #20
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by CornedBee View Post
    Be extremely careful when judging programs for things like cache coherency, branch efficiency, and similar hardware-level performance issues. Your guess which of two given pieces of code is faster will typically be right 50% of the time. It's extremely hard to predict what will happen, given modern compilers and CPUs.
    Yes. My statement about the equivalence of the two last statements was based on experience with both Visual Studio C++ .Net and gcc 3 and 4. Both of those will use "SETcc" to produce truth-values from "a = x < y" or similar, so no branch there.

    In the course about efficient programming I'm taking right now, the teacher is showing us techniques for refactoring code and tools for measuring efficiency. The goal is to use the tools and figure out where and what the problem is, then make an informed guess at a transformation that would alleviate the problem, measure again, make another guess, and so on, until you've found the best way to do it.
    Don't worry, the next generation of CPUs will invalidate all your experiments
    Sounds like an interesting class - I wish I had known about that one some 12-15 years ago when I started working on performance analyzis.

    If you have something that is anything but real trivial, it's definitely necessary to "find the bottleneck" with the right type of tools, sampling profiler or some such is a good tool here.

    Not only do different CPU variants change the behaviour, but also changing from one compiler to another will change the behaviour - because the next generation compiler will "know" how to do more efficient code for the latest generation processors.


    --
    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.

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Yeah I always thought that using the ? operator there might have been unnecessary. It's an old habbit since I learnt Pascal before C++. More strongly typed lauanges don't allow implicit conversion from bool to int.

    The branch wouldn't be so bad if it was predictable, but it's probably mostly random, depending on what you're using the code for of course.

    btw, I found the original code I built my version from, see here:
    http://www.google.com/search?hl=en&q...2+bigint&meta=
    Beware though as that code is rather buggy. I fixed hopefully all of the bugs in my version, optimised a lot of the functions (especially the bitshifts), and added a lot of missing stuff, like signed big integers.
    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"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. Vector vs. array.
    By matsp in forum C++ Programming
    Replies: 37
    Last Post: 06-23-2008, 01:41 PM
  3. Help needed Please
    By jereland in forum C Programming
    Replies: 9
    Last Post: 03-18-2004, 05:30 AM
  4. Can somebody test this code please
    By andy bee in forum C Programming
    Replies: 6
    Last Post: 10-09-2001, 04:08 PM

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