Thread: generic add with carry

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

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];
	}
}

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

Originally Posted by dwks

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

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.

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

Originally Posted by CornedBee

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

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.