On Nov 23, 3:02 pm, "Alf P. Steinbach" <al...@start.no> wrote:
<snip>
Why do you have the length arguments?
A std::vector has a length, accessible via size() and resize().
I thought resize() is to do just that, resize the vector,
not get it's length. Also, I have then length arguments
so I can use lengths different from those of the vector
if one needs to do that for some reason.
{
/* Set up temporary digit buffer */
Digit tmpbuf[2*MAX_PRECISION]; // use array instead of vector
to
// maximize performance. Vector
// takes forever to constantly
de/
// reallocate.
Have you measured this?
Sure did. Took ~34 secs, for 100,000,000 calls, with all
compiler optimizations turned on.
I just reduced the routine to this:
FG3DError FG3DDigitVector_Mul(std::vector<Digit> &vec0,
const std::vector<Digit> &vec1,
const std::vector<Digit> &vec2,
int length1, int length2)
{
std::vector<Digit> tmpbuf(length1 + length2);
return(FG3DError(FG3D_SUCCESS));
}
and just ran it over and over 100,000,000 times to
see how long that allocate/free takes and I was
stunned to find it wastes 34 seconds, more time than
the entire multiplication loop!
Anyway, reserve ALL UPPERCASE for macros.
If MAX_PRECISION is a macro, make it a typed constant.
It's a macro, #defined as some number equal to the maximum
amount of "Digit"s that we want to allow (right now, it's
set at 128).
/* Safety */
if(length1 > MAX_PRECISION)
return(FG3DError(FG3D_INVALID_PRECISION, length1));
if(length2 > MAX_PRECISION)
return(FG3DError(FG3D_INVALID_PRECISION, length2));
Ensure class invariants in operations so that you don't have to pepper
the code with checks all over the place.
In other words,
class Bignum
{
private:
std::vector<Digit> myDigits;
public:
// Whatever, all operations assume a max length
// and ensure that max length.
};
The problem is I need to be able to work on pieces of the
digit string as well as the entire string with some
operations (addition, subtraction). And if the operations
ensure the max length does not that require those if()
checks in them to make sure the length parameter passed
does not exceed the limit?
/* Clear buffer */
std::fill(tmpbuf, tmpbuf + length1 + length2, 0);
Just zero-initialize the array if you're using an array,
Digit tmpbuf[whatever] = {0};
Alright.
/* Set up iterators */
std::vector<Digit>::iterator v0i(vec0.begin());
std::vector<Digit>::const_iterator v1i(vec1.begin());
std::vector<Digit>::const_iterator v2i(vec2.begin());
std::vector<Digit>::const_iterator v2init(v2i);
/* Do the multiplication */
for(int i(0);i<length1;i++,++v1i)
{
TwoDigit carry;
carry = 0;
v2i = v2init;
for(int j(0);j<length2;j++,++v2i)
{
TwoDigit
tmp((static_cast<TwoDigit>(*v1i)*static_cast<TwoDigit>(*v2i))
+static_cast<TwoDigit>(tmpbuf[i+j])+carry);
This looks rather suspicious.
However, you don't provide definitions of Digit and TwoDigit, so
difficult to say.
TwoDigit can be any unsigned type that has twice the bitlength
of Digit. You could use unsigned int (32 bit) for TwoDigit,
unsigned short (16 bit) for Digit, for example.
carry = tmp>>DIGIT_SIZE;
tmp &= MAX_DIGIT;
tmpbuf[i+j] = tmp;
}
tmpbuf[i+length2] = carry;
}
/* Copy result back */
vec0.reserve(length1 + length2);
std::copy(tmpbuf, tmpbuf + length1 + length2, vec0.begin());
Don't modify out-arguments directly.
Create the result in a local variable, then at the end swap().
For exception safety.
The result is already being built in the temp buffer, that's the
point. And does this mean one cannot resize the output vector if
it cannot hold the full size product? Or will swap() do that
automatically? Is swap() slower than the above?
2. array buf ; fill ; result.reserve ; copy ;