Search Results

Search found 5 results on 1 pages for 'user168715'.

Page 1/1 | 1 

• efficiently determining if a polynomial has a root in the interval [0,T]

  - by user168715

  I have polynomials of nontrivial degree (4+) and need to robustly and efficiently determine whether or not they have a root in the interval [0,T]. The precise location or number of roots don't concern me, I just need to know if there is at least one. Right now I'm using interval arithmetic as a quick check to see if I can prove that no roots can exist. If I can't, I'm using Jenkins-Traub to solve for all of the polynomial roots. This is obviously inefficient since it's checking for all real roots and finding their exact positions, information I don't end up needing. Is there a standard algorithm I should be using? If not, are there any other efficient checks I could do before doing a full Jenkins-Traub solve for all roots? For example, one optimization I could do is to check if my polynomial f(t) has the same sign at 0 and T. If not, there is obviously a root in the interval. If so, I can solve for the roots of f'(t) and evaluate f at all roots of f' in the interval [0,T]. f(t) has no root in that interval if and only if all of these evaluations have the same sign as f(0) and f(T). This reduces the degree of the polynomial I have to root-find by one. Not a huge optimization, but perhaps better than nothing.

  Read the article

• Copy constructor bug

  - by user168715

  I'm writing a simple nD-vector class, but am encountering a strange bug. I've stripped out the class to the bare minimum that still reproduces the bug: #include <iostream> using namespace std; template<unsigned int size> class nvector { public: nvector() {data_ = new double[size];} ~nvector() {delete[] data_;} template<unsigned int size2> nvector(const nvector<size2> &other) { data_ = new double[size]; int i=0; for(; i<size && i < size2; i++) data_[i] = other[i]; for(; i<size; i++) data_[i] = 0; } double &operator[](int i) {return data_[i];} const double&operator[](int i) const {return data_[i];} private: const nvector<size> &operator=(const nvector<size> &other); //Intentionally unimplemented for now double *data_; }; int main() { nvector<2> vector2d; vector2d[0] = 1; vector2d[1] = 2; nvector<3> vector3d(vector2d); for(int i=0; i<3; i++) cout << vector3d[i] << " "; cout << endl; //Prints 1 2 0 nvector<3> other3d(vector3d); for(int i=0; i<3; i++) cout << other3d[i] << " "; cout << endl; //Prints 1 2 0 } //Segfault??? On the surface this seems to work fine, and both tests print out the correct values. However, at the end of main the program crashes with a segfault, which I've traced to nvector's destructor. At first I thought the (incorrect) default assignment operator was somehow being called, which is why I added the (currently) unimplemented explicit assignment operator to rule this possibility out. So my copy constructor must be buggy, but I'm having one of those days where I'm staring at extremely simple code and just can't see it. Do you guys have any ideas?

  Read the article

• efficient thread-safe singleton in C++

  - by user168715

  The usual pattern for a singleton class is something like static Foo &getInst() { static Foo *inst = NULL; if(inst == NULL) inst = new Foo(...); return *inst; } However, it's my understanding that this solution is not thread-safe, since 1) Foo's constructor might be called more than once (which may or may not matter) and 2) inst may not be fully constructed before it is returned to a different thread. One solution is to wrap a mutex around the whole method, but then I'm paying for synchronization overhead long after I actually need it. An alternative is something like static Foo &getInst() { static Foo *inst = NULL; if(inst == NULL) { pthread_mutex_lock(&mutex); if(inst == NULL) inst = new Foo(...); pthread_mutex_unlock(&mutex); } return *inst; } Is this the right way to do it, or are there any pitfalls I should be aware of? For instance, are there any static initialization order problems that might occur, i.e. is inst always guaranteed to be NULL the first time getInst is called?

  Read the article

• Effective optimization strategies on modern C++ compilers

  - by user168715

  I'm working on scientific code that is very performance-critical. An initial version of the code has been written and tested, and now, with profiler in hand, it's time to start shaving cycles from the hot spots. It's well-known that some optimizations, e.g. loop unrolling, are handled these days much more effectively by the compiler than by a programmer meddling by hand. Which techniques are still worthwhile? Obviously, I'll run everything I try through a profiler, but if there's conventional wisdom as to what tends to work and what doesn't, it would save me significant time. I know that optimization is very compiler- and architecture- dependent. I'm using Intel's C++ compiler targeting the Core 2 Duo, but I'm also interested in what works well for gcc, or for "any modern compiler." Here are some concrete ideas I'm considering: Is there any benefit to replacing STL containers/algorithms with hand-rolled ones? In particular, my program includes a very large priority queue (currently a std::priority_queue) whose manipulation is taking a lot of total time. Is this something worth looking into, or is the STL implementation already likely the fastest possible? Along similar lines, for std::vectors whose needed sizes are unknown but have a reasonably small upper bound, is it profitable to replace them with statically-allocated arrays? I've found that dynamic memory allocation is often a severe bottleneck, and that eliminating it can lead to significant speedups. As a consequence I'm interesting in the performance tradeoffs of returning large temporary data structures by value vs. returning by pointer vs. passing the result in by reference. Is there a way to reliably determine whether or not the compiler will use RVO for a given method (assuming the caller doesn't need to modify the result, of course)? How cache-aware do compilers tend to be? For example, is it worth looking into reordering nested loops? Given the scientific nature of the program, floating-point numbers are used everywhere. A significant bottleneck in my code used to be conversions from floating point to integers: the compiler would emit code to save the current rounding mode, change it, perform the conversion, then restore the old rounding mode --- even though nothing in the program ever changed the rounding mode! Disabling this behavior significantly sped up my code. Are there any similar floating-point-related gotchas I should be aware of? One consequence of C++ being compiled and linked separately is that the compiler is unable to do what would seem to be very simple optimizations, such as move method calls like strlen() out of the termination conditions of loop. Are there any optimization like this one that I should look out for because they can't be done by the compiler and must be done by hand? On the flip side, are there any techniques I should avoid because they are likely to interfere with the compiler's ability to automatically optimize code? Lastly, to nip certain kinds of answers in the bud: I understand that optimization has a cost in terms of complexity, reliability, and maintainability. For this particular application, increased performance is worth these costs. I understand that the best optimizations are often to improve the high-level algorithms, and this has already been done.

  Read the article

• operator overloading and inheritance

  - by user168715

  I was given the following code: class FibHeapNode { //... // These all have trivial implementation virtual void operator =(FibHeapNode& RHS); virtual int operator ==(FibHeapNode& RHS); virtual int operator <(FibHeapNode& RHS); }; class Event : public FibHeapNode { // These have nontrivial implementation virtual void operator=(FibHeapNode& RHS); virtual int operator==(FibHeapNode& RHS); virtual int operator<(FibHeapNode& RHS); }; class FibHeap { //... int DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey) { FibHeapNode *theParent; // Some code if (theParent != NULL && *theNode < *theParent) { //... } //... return 1; } }; Much of FibHeap's implementation is similar: FibHeapNode pointers are dereferenced and then compared. Why does this code work? (or is it buggy?) I would think that the virtuals here would have no effect: since *theNode and *theParent aren't pointer or reference types, no dynamic dispatch occurs and FibHeapNode::operator< gets called no matter what's written in Event.

  Read the article

1