Re: Can I avoid the use of arrays in this situation or do I have
to use them?
* mike3:
I've been reworking a bignum package I made a bit. I've got this thing
here that multiplies two strings of digits using a simple "grade
school" algorithm, and it seems I can't help but use an array in there
for a temporary buffer, as reallocating an std::vector<> over and over
again takes lots of time, and storing a global buffer would be a
problem since my program will have multithreading. (Although I suppose
one could allocate a certain amount of global buffers equal to the
maximum amount of threads one could run and then pass an index
parameter to each routine but that seems kind of silly. And how do you
keep track of all these buffers especially with overloaded operators
where you can't pass a parameter?! Eww.) Can I avoid the use of the
array and still get maximum performance? Or is this the case when
arrays are appropriate? The point of the temporary buffer is to allow
for this to be used as an "in-place" multiplication procedure as well
as out-of-place. There are other places in the bignum package where
similar array-vs-vector performance considerations arise involving
temporary buffers (there's a floating point addition/subtraction
routine that requires shifting the bits in one of the operands and to
avoid messing up the original it creates a temporary buffer... Also,
that buffer needs to be able to be passed to routines similar to this
one which accept vectors... Should I just give up and use arrays
everywhere for this?! (sucks a lot)).
Also, are the typecasts in there necessary or could they be removed
and the full-width product of the two digits still be obtained?
This is the code:
---
/* Multiply two digit vectors.
* Parameters:
* vec0: Reference to destination vector.
* vec1: Reference to vector to multiply.
* vec2: Reference to vector to multiply by.
* length1: Length of vec1
* length2: Length of vec2
*
* Returns: Error code
*
* Operation: vec0 = vec1 * vec2.
*
* Note: vec0 must be able to hold length1 + length2 worth of
* elements.
*/
FG3DError FG3DDigitVector_Mul(std::vector<Digit> &vec0,
const std::vector<Digit> &vec1,
const std::vector<Digit> &vec2,
int length1, int length2)
Why do you have the length arguments?
A std::vector has a length, accessible via size() and resize().
{
/* 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?
Anyway, reserve ALL UPPERCASE for macros.
If MAX_PRECISION is a macro, make it a typed constant.
/* 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.
};
/* Clear buffer */
std::fill(tmpbuf, tmpbuf + length1 + length2, 0);
Just zero-initialize the array if you're using an array,
Digit tmpbuf[whatever] = {0};
/* 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.
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.
}---
Cheers, & hth.,
- Alf
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?