Thread: Integer Factorization

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    71

    Integer Factorization

    Hi all,

    again another question hoping to find it's answer on this forum. The question is related to a program I recently made, a program for integer factorization.

    I won't be posting the whole code here, since it's six pages long, and half of that is only "ifs" and "switches" so I never get output in the form of, say, "5^0", or "2 ^1" and such. The basic way the program works:

    1. Asks user for the number they want to factorize
    2. Generates primes up to that number into an 2D array (second dimension explained later), and at the same time checks if the entered number is prime.
    3. Divides by two while possible, incrementing a variable every time it does so.
    4. Does the same thing except with division by three.
    5. If, after division by two and three, the result is one, it prints out something like "2^2 x 3"
    6. If after division by two and three, the result isn't one, division continues with the primes in the array generated at the beginning. Whenever a prime is a divisor, the second dimension, which is by default 0, is incremented. This is done while possible.
    7. The primes that have a value bigger than 0 in the second dimension of the array are transfered to a new array, which is then printed out. I have the same switches/ifs etc. to ensure proper form

    The complete source code is included in the attachment. The code works fine, except for one thing, that being that it can't factorize numbers above thirty two thousand something. I can't remember the exact number. I have a feeling that is has something to do with the number of elements an array can have, but I'm not sure. I've tried changing the data type, but even when I use an unsigned long long int it won't change anything.

    Help is appreciated
    Last edited by G4B3; 03-19-2008 at 12:24 AM.

  2. #2
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Methinks you can probably do that in much less than 6 pages of code.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by arpsmack View Post
    Methinks you can probably do that in much less than 6 pages of code.
    That depends on the font size!
    Yeah I think 1-2 pages would be more like it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    71
    Of course you can. As I said, like half of that, and I just checked and it's a little more, is just ifs and switches that have no use other than visual appeal. Check for yourselves, I just added the source ;-)

    Any idea however on what to do with the problem I'm having?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Instead of generating all the possible prime factors, it would be less memory intensive to find the prime factors on the fly.

    A possible algorithm would be along the lines of:
    Code:
    n = number entered by user
    sqrt_n = sqrt(n)
    i = 2
    while n > 1 and i <= sqrt_n
        if n is divisible by i
            add i to list of prime factors
            count = 1
            n = n / i
            while n is divisible by i
                increment count
                n = n / i
            add count to list of prime factor counts
        increment i
    if n > 1
        add n to list of prime factors
        add 1 to list of prime factor counts
    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
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    That program does not deserve 6 pages of code ! Can be done in about 20-25 lines or less than that.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  7. #7
    Registered User
    Join Date
    Mar 2008
    Posts
    71
    @laserlight: Thanks for that algorithm. Looks nice :-)

    @ping: I know. As I said, over half of the program length is taken up by visual details. Check the source, or one of my previous posts, for what I mean, because this would be the third time I'd be trying to explain. The program length isn't what bothers me. I know it could be made much shorter. But my question was not "Can this program be made shorter in any way", which is a question all of you, possibly excluding laserlight, are answering to. I don't mean or want to sound ungrateful, but seriously, I don't need to hear that the program could be a thousand times shorter three times for me to acknowledge it. The problem I am having, which was also the reason I started this topic, is stated above, and remains unsolved:

    The code works fine, except for one thing, that being that it can't factorize numbers above thirty two thousand something. I can't remember the exact number. I have a feeling that it has something to do with the number of elements an array can have, but I'm not sure. I've tried changing the data type, but even when I use an unsigned long long int it won't change anything.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Arrays can certainly go beyond 32767 on a machine with 32-bit registers and sufficient amount of memory to hold the array.

    If you are using for example Turbo C, it gives you 16-bit code, so there arrays are limited to 64KB of memory.

    You could of course use other techniques to store more than 64KB, but it gets complicated.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463
    That was shocking, the formatting that is.

  10. #10
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463
    Quote Originally Posted by matsp View Post
    Arrays can certainly go beyond 32767 on a machine with 32-bit registers and sufficient amount of memory to hold the array.

    If you are using for example Turbo C, it gives you 16-bit code, so there arrays are limited to 64KB of memory.

    You could of course use other techniques to store more than 64KB, but it gets complicated.

    --
    Mats

    The question immediately arises, how complicated?

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Instead of using a plain array, you would have to write a function that takes a long int, and then uses multiple tables to look up the value. This simple example shows the principle [but to make it work in a 16-bit environment, you'd have to use dynamic memory allocation to get the data to get over the 64KB limit]:
    Code:
    int arr1[100];
    int arr2[100];
    int arr3[100]
    int *arrarr[3] = { arr1, arr2, arr3 };
    
    int findval(int x) 
    {
       return arrarr[x / 100][x % 100]; 
    }
    The overhead of splitting the number and indexing, and calling a function, will be noticable compared to a straight array index.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    I know. As I said, over half of the program length is taken up by visual details. Check the source, or one of my previous posts, for what I mean, because this would be the third time I'd be trying to explain. The program length isn't what bothers me. I know it could be made much shorter. But my question was not "Can this program be made shorter in any way", which is a question all of you, possibly excluding laserlight, are answering to. I don't mean or want to sound ungrateful, but seriously, I don't need to hear that the program could be a thousand times shorter three times for me to acknowledge it. The problem I am having, which was also the reason I started this topic, is stated above, and remains unsolved:
    Smaller code = Easier to Debug.

    You do not specify what compiler, what architecture you are working on..

    One thing that comes to my mind is your array size which is equal to 2*input. You are declaring it inside main which means on the stack. Make it global.

    P.S. I don't feel like going through 6 pages of mindless code when the OP can improve his algorithm as suggested by everyone else and make it easier to debug for all of us.
    Last edited by PING; 03-20-2008 at 10:15 AM.
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  13. #13
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Quote Originally Posted by PING
    I don't feel like going through 6 pages of mindless code when the OP can improve his algorithm as suggested by everyone else and make it easier to debug for all of us.
    My thoughts exactly. I work as a teaching assistant at my university, and there is nothing more agonizing than a professor asking you to grade a student's 300+ line bloated program that could have been done with around 40-50 lines.

    Its much easier to sit down with the student, scrap everything they've written, and explain to them how to do it right (which laserlight helped you with). If you know what you're doing, you should be able to implement the pseudo-code that was posted in less than a half hour, and I think you'll appreciate the elegance of the solution (and how much easier it is to debug!).

    As an example of where we're coming from, here's a an actual situation I had to deal with:

    A student was asked to write a program that processed a 2D array of numbers. For each number in the array, they needed to check every number around it and do something with it (details not important). One particular student wrote a solution that consisted of a giant if-then-else block that had a separate case for each corner, the top row, the bottom row, the left column, the right column, and every element in the middle. It was HUGE and complicated.

    If that student had a tiny bug hidden somewhere in their giant rat's nest of code, do you think I want to wade through all that and find it? Absolutely not. Instead I politely pointed out a much more elegant solution, and once they understood it, I saw that light bulb turn on in their head (one of those 'Ah hah!' moments). They rewrote all their code, and it was MUCH easier to get working.

    Quote Originally Posted by Edsger Dijkstra
    How do we convince people that in programming simplicity and clarity —in short: what mathematicians call "elegance"— are not a dispensable luxury, but a crucial matter that decides between success and failure?
    [edit]
    On a side note, when I'm writing programs, I often realize after I've partially finished that I could have done it so much better a different way. I sometimes rewrite programs SEVERAL TIMES before I'm satisfied. Don't think that this is a sign of a bad programmer. On the contrary I think that makes you a better programmer, and your rewrites will decrease as you gain more experience.
    [/edit]
    Last edited by arpsmack; 03-20-2008 at 04:54 PM.

  14. #14
    Registered User
    Join Date
    Mar 2008
    Posts
    71
    I admit, I did get a little impatient. And of course you're right. I apologize. Thanks for the help everyone. I'll have a look at the code, try to re-write it, and then post the final source when I'm done :-) Once more, sorry.

  15. #15
    Cogito Ergo Sum
    Join Date
    Mar 2007
    Location
    Sydney, Australia
    Posts
    463
    That's k, for my first assignment ever, most people did 300 lines of code, i did 1800, lol.

    Of course...they were if statements

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  4. No Match For Operator+ ???????
    By Paul22000 in forum C++ Programming
    Replies: 24
    Last Post: 05-14-2008, 10:53 AM
  5. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 10:43 AM