Thread: Static vs. Dynamic Arrays, Getting Undefined Behavior

  1. #1
    Registered User
    Join Date
    Jan 2012
    Location
    Michigan
    Posts
    7

    Static vs. Dynamic Arrays, Getting Undefined Behavior

    Hello everyone! First post, and pretty new to C++, so I apologize for any blatantly dumb questions that I may ask. Just trying to learn!

    I'm working on a Project Euler problem that has me looking for the largest prime factor of a number. (Specifically, a very large number.) My main programming background is in MATLAB, and I have 3 different versions of code to solve the problem there, but MATLAB is just incapable of handling the value I am trying to evaluate. (~600 billion.) Hence, here's me, trying to learn C++, hoping that it will be efficient enough to handle the problem set forth, as well as furthering my goal of learning C++! hahaha

    My question is regarding static vs. dynamic memory allocation for arrays. My code is running as expected, but before it was, I was getting some strange errors, and it brought up something I was confused about. At this point, I'm shying away from dynamic arrays just because they seem to be a hair too complicated for my noobishness. I'm trying to get my foundation set in C++ first, then I'll start to tackle some more of the finer points of the language.

    In my code, I declare an array "factors" with "halfVal" cells. "halfVal" is defined beforehand, and I don't need it to change later on, so static should be fine, but I'm not sure how to declare it statically by using the value of halfVal. Is it possible to use the value of a variable, in this case halfVal, to statically define the number of cells in an array? If so, how would I do that?

    Code:
    #include <iostream>
    #include <cmath>
    
    
    using namespace std;
    
    
    int main (int argc, const char * argv[])
    {
        
        //Declare variables. Initialization may or may not be necessary?
        int halfVal = 1, counter = 0;
        
        double value = 0, quotient = 0;
        
        //Decalre value to find the largest prime value of
        value = 30; //Goal Value is 600851475143
        
        //Calculate halfVal for efficiency of following for loop
        halfVal = (value / 2) + 1;
    
    
        //Declare array. Can I make this a static array while still using the value of halfVal somehow? I don't need a dynamic allocation of memory.
        int factors[halfVal];
        
        //Determine the quotient of the value divided by num (from 2 to halfVal) for logical test
        for( int num = 2; num < halfVal ; num++ ){
            
            quotient = (value / num);
            
            
            //Logical test to determine whether or not num is a factor. If so, store in factors array and update counter
            if( quotient == ceil( quotient ) ) {
    
                factors [counter] = num;
    
                counter = counter + 1;
            }
        }
        
        for( int i = 0; i < counter; i++ ) { 
            //If counter is replaced with halfVal, then I get undefined behavior. Something to do with dynamic array?
            
            cout << "Factor: " << factors[i] <<"\n";
        }
    }
    Also, another question I have is if I try to access a value in the factors array that is declared, but not redefined in the first for-if loop, then I get undefined behavior when I try to print those values. For example, the factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30. That is 8 total values. If halfVal is set to 16, (and therefore the declaration of the factors array should be 16 total cells) and then I try to print factors[0] through factors[15], after I pass the first 8 cells that have been redefined in the first for-if loop, I get undefined behavior. My output gives me something like:

    Factors: 2
    Factors: 3
    Factors: 5
    Factors: 6
    Factors: 10
    Factors: 15
    Factors: 1510532867
    Factors: 5937525205
    etc.
    etc.

    (The last several values are obviously the undefined behavior.)

    My hunch is that since I have a dynamically allocated array, the values aren't initially defined, so when I try to access them, I get undefined behavior. Is it possible to initialize those values when the array is declared to avoid this type of problem (still keeping it a dynamic array)? If so, how does one go about that. If not, any tips on where I can start to look for a function to clear out the unused cells? No explanation needed, just a point in the right direction for that one. I think figuring this out will help me in starting to understand dynamic allocation more. Any insight on this issue would be wonderful!

    Thanks so much, and sorry for the long post!

  2. #2
    Registered User
    Join Date
    Apr 2008
    Posts
    396
    As factors is an automatic variable (on stack), it's not reset and contains garbage when you declare it. It does contains halfVal items (the size is correct). If you add an output in your program when you assign factors[counter], you'll see you only setup the first 6 items (from 0 to 5) so everything else is just random values.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    factors is a variable length array, which is a non-standard language feature. You could either create a fixed size array that is as large as you will ever need, or use a container like std::vector:
    Code:
    std::vector<int> factors(halfVal);
    This should also zero initialise the elements of factors.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Jan 2012
    Location
    Michigan
    Posts
    7
    Quote Originally Posted by root4 View Post
    As factors is an automatic variable (on stack), it's not reset and contains garbage when you declare it. It does contains halfVal items (the size is correct). If you add an output in your program when you assign factors[counter], you'll see you only setup the first 6 items (from 0 to 5) so everything else is just random values.
    So if I understand correctly, when a variable length array is declared, the initialized "values" of the array are just garbage until I reassign them with something useful. Is that correct?

    Quote Originally Posted by laserlight View Post
    factors is a variable length array, which is a non-standard language feature. You could either create a fixed size array that is as large as you will ever need, or use a container like std::vector:
    Code:
    std::vector<int> factors(halfVal);
    This should also zero initialise the elements of factors.
    I haven't worked with containers like the one mentioned before, so I am unsure how. Any tutorials you could direct me towards so I can start learning them? The standard vs. non-standard language features concept is still a confusing one for me.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by StefPrez
    So if I understand correctly, when a variable length array is declared, the initialized "values" of the array are just garbage until I reassign them with something useful. Is that correct?
    You should check your compiler's documentation, but yes

    Quote Originally Posted by StefPrez
    I haven't worked with containers like the one mentioned before, so I am unsure how. Any tutorials you could direct me towards so I can start learning them?
    Borrow Josuttis' The C++ Standard Library - A Tutorial and Reference from your local library. It is slightly outdated but still useful.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    For example, the factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30.
    Euler problem 3 is about prime factors, otherwise finding the largest divisor would be a bit too trivial. The problem might look intimidating, but I suppose it can be solved with simple trial division. You definitely don't need an array that large, and whatever programming language, the memory usage would be too large.

    (Tried at ideone.com, Python with trial division by odd integers yields the answer in 0.03 seconds without any array. It only comes down to getting the algorithm right.)
    Last edited by anon; 01-17-2012 at 12:18 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Registered User
    Join Date
    Apr 2010
    Posts
    88
    Quote Originally Posted by anon View Post
    Euler problem 3 is about prime factors, otherwise finding the largest divisor would be a bit too trivial. The problem might look intimidating, but I suppose it can be solved with simple trial division. You definitely don't need an array that large, and whatever programming language, the memory usage would be too large.

    (Tried at ideone.com, Python with trial division by odd integers yields the answer in 0.03 seconds without any array. It only comes down to getting the algorithm right.)
    When I finished this problem on the Project Euler site, a PDF became available describing the best way to tackle this problem. There are a few constraints you can place on the loops which drastically cut down computation time.

    I won't give you the answer, but links to good methods should come up if you just google "testing for primeness" "finding prime factors"

    Edit: I posted as a reply to this post because there IS an element of trial division, but you can do it in a clever way which cuts down on iterations. Also, I don't think I used an array (I don't have the files on this comp). To the OP, if you like math, and I assume you do since you're doing PE problems, there are a few properties of prime and composite numbers that help you out. There are fancy sounding names for the theorems or methods, but it's something you could likely come up with on your own in the pencil and paper realm, by messing around with some (not complicated) algebra.
    Last edited by Ocifer; 01-17-2012 at 12:49 PM.
    W7, Ubuntu -- mingw, gcc, g++, code::blocks, emacs, notepad++

  8. #8
    Registered User
    Join Date
    Jan 2012
    Location
    Michigan
    Posts
    7
    Quote Originally Posted by anon View Post
    Euler problem 3 is about prime factors, otherwise finding the largest divisor would be a bit too trivial.
    I know, I said that in the beginning of my post. I was merely just determining factors first, then sorting prime factors from that list. I don't doubt there is a more efficient way to do it, however with C++ still being very new to me, I decided to go with the "easy approach" and then trim the fat or rework the code for efficiency.

    Quote Originally Posted by Ocifer View Post
    When I finished this problem on the Project Euler site, a PDF became available describing the best way to tackle this problem. There are a few constraints you can place on the loops which drastically cut down computation time.

    I won't give you the answer, but links to good methods should come up if you just google "testing for primeness" "finding prime factors"

    Edit: I posted as a reply to this post because there IS an element of trial division, but you can do it in a clever way which cuts down on iterations. Also, I don't think I used an array (I don't have the files on this comp). To the OP, if you like math, and I assume you do since you're doing PE problems, there are a few properties of prime and composite numbers that help you out. There are fancy sounding names for the theorems or methods, but it's something you could likely come up with on your own in the pencil and paper realm, by messing around with some (not complicated) algebra.
    Thanks! I started to optimize slightly in my MATLAB prototypes, however in MATLAB, the factor function returns prime factors of a number, yet the value used in PE was too large for it. (Max value is 2^32.) At that point, I was pretty confident I had to do it in another language, and C++ was my choice. I will optimize soon, as soon as I have a properly functions version.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I'm not sure this is a matter of optimization, but rather using a rather unsuitable algorithm to begin with. 300 billion trial divisions is way too much work, even if you sort out the memory problems (the large value in question has just a few prime factors, and hence rather few divisors). You could cut it down a little by taking into account that the largest prime factor of composite n can't be larger than sqrt(n).

    I would also doubt the floating point math. C++11 has 64-bit integers that is enough for this problem.
    Last edited by anon; 01-18-2012 at 03:13 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    But if you insist on finding the divisors, you can add them to a std::vector, which is a dynamically growing array. The reason is that you don't know how many divisors there's going to be (you'd know that after finding how many prime factors there are ), could be 10, could be 1000, could be a million.
    Last edited by anon; 01-18-2012 at 04:23 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    Registered User
    Join Date
    Apr 2010
    Posts
    88
    Yes I'm sorry. I wasn't sure if I would ruin the learning process, but data overflow is one of the intended stumbling blocks of this problem. However, I would be shocked to learn that MATLAB doesn't support long integers (I don't have experience). You should be able to accommodate larger integers in MATLAB, it's serious software. Look for datatype documentation before you change languages just to solve this problem...though I do like c++

    Also, consider your own mental processes when you try to factorize smaller (more humane ) numbers.

    Consider 700

    What's the first prime? 2.

    2 divides 700 leaving a quotient of 350
    2 divides 350 leaving a quotient of 175

    2 DOES NOT divide 175

    What's the next prime? 3

    3 DOES NOT divide 175

    What's the next prime? 5

    5 divides 175 leaving a quotient of 35
    5 divides 35 leaving a quotient of 7

    5 doesn't divide 7

    next prime: 7

    7/7 = 1 and you are done

    -----------------------------------

    700 = 2^2 * 5^2 * 7

    ---------------------------------

    The way I presented is highly suggestive of how one might program a machine to do it, as a hint. Most people would divide out the 7 first and the 100 falls apart into 25 * 4 = 5^2 * 2^2, but you don't want to complicate this by trying to program intuition. Note I'm not considering even numbers after 2 -- the reason why is not too hard to see.

    There are further tweaks which can be done to this basic idea, but this should give you enough efficiency to solve the problem. To really get the most of this problem, make sure to read the PDF that becomes available.

    EDIT: So there is an element of trial division, but we don't implement the division operator per se. We're testing divisibility by n, and this is often done using the modulo operator ( % ). One can conceptualize this as slowly "shaving off" factors only if doing so leaves an integer quotient. Bahh I've said too much.
    Last edited by Ocifer; 01-19-2012 at 12:00 AM.
    W7, Ubuntu -- mingw, gcc, g++, code::blocks, emacs, notepad++

  12. #12
    Registered User
    Join Date
    Jan 2012
    Location
    Michigan
    Posts
    7
    Thanks for all the input and advice everyone! This problem was definitely a multifaceted learning experience for me. Regardless of how one learns the material, the important part is learning it. I think I learned a lot, even if it may have been down the wrong path, but I also learned a lot by you all guiding me towards the light. Much appreciated, once again! Hopefully I'll be able to help people out in a similar fashion one day. I'm a bit too green for that currently, though. Best regards!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Is x=x++; Undefined Behavior?
    By envec83 in forum C Programming
    Replies: 5
    Last Post: 10-04-2011, 01:27 AM
  2. Undefined behavior from VC6 to 2k5
    By m37h0d in forum C++ Programming
    Replies: 10
    Last Post: 06-22-2011, 07:56 PM
  3. openGL: textures, gluLookAt, and undefined behavior
    By MK27 in forum Game Programming
    Replies: 7
    Last Post: 04-28-2009, 10:12 AM
  4. Dynamic libs and undefined references
    By ccox421 in forum C Programming
    Replies: 5
    Last Post: 03-28-2009, 10:25 AM
  5. Static array is allocated in undefined area
    By esben in forum C Programming
    Replies: 4
    Last Post: 05-13-2006, 05:24 PM

Tags for this Thread