[SOLVED] I'm trying to right a least common multiplke program, don't know what i did wrong(c++

rwalek668 · 01-08-2011, 11:23 AM

THis is my code, there are no error messages, and i think the problem has to do with nLowestValue but i am not sure:

Code:

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;


int main(int nNumberofArgs, char* pszArgs[])
{
    //States program objective
    cout << "This program while find the least common multiple\n"
         << "of a few numbers.  Enter a zero after you\n"
         << "have entered all the desired values." << endl;

    int nFactors[100];
    int nAccumulator = 0;
    //entrance of numbers loop
    for (int nIntake = 1; nIntake > 0; nAccumulator++)
    {
        cin >> nIntake;
    nFactors[nAccumulator] = nIntake;
    }

    //sets one past final array value to zero and stores total number + 1 of numbers in Array
    int nAccumulatorStore = nAccumulator;

    nAccumulator = 0;

    int nLowestValue = nFactors[0];

    //find the lowest of the numbers in the array
    for (;nFactors[nAccumulator] > 0;nAccumulator++)
    {
        if (nFactors[nAccumulator] < nLowestValue)
        {
            nLowestValue = nFactors[nAccumulator];

        }
    }

    //create loop which adds one to stored value if number is divisible 1,2,3...

    // multiply all the numbers together
    int nMultiplied = 1;
    nAccumulator = 0;
    for (;nFactors[nAccumulator] > 0;nAccumulator++)
    {
        nMultiplied = nMultiplied * nFactors[nAccumulator];
    }
    nAccumulator = 0;

//add one loop and divisibility test
for (int nDivisor = 1; nDivisor < nLowestValue; nDivisor++)
{
    int nTotalofDivisors = 0;

    //finds number of numbers divisibe by divisor
    for ( ;nFactors[nAccumulator] > 0;nAccumulator++ )
    {
        if (0 == nFactors[nAccumulator] % nDivisor)
        {
            nTotalofDivisors++;

        }
    }
    if (nTotalofDivisors >= 2)
    {
        nMultiplied = nMultiplied / nDivisor;
        nLowestValue = nLowestValue / nDivisor;
        cout << nMultiplied;
    }
}
cout << "The least common multiple is: " << nMultiplied << endl;
system("PAUSE");
return 0;
}

[/SIZE]
Thanks for any help

johnsfine · 01-08-2011, 11:44 AM

I tried reading your code (pretty hard, since you didn't use CODE tags) to deduce what algorithm you think you are using to get the lcm of multiple numbers. I decided that was too much trouble. Your algorithm is wrong by more than some minor detail. Finding exactly the right factors to divide the product by from the large collection of numbers would be fairly complicated.

Quote:

Originally Posted by rwalek668

i think the problem has to do with nLowestValue but i am not sure

A problem (not the problem) has to do with nLowestValue. The lowest value is simply not useful for anything like the way you're using it. Think about lcm(1,8,12). Your use of lowest value keeps you from seeing that a factor of 2 is in two of the inputs. But even if you fixed that, the approach is still flawed, because dealing with that 2 stops you from correctly dealing with the factor of 4 that is also in there twice.

Even if your algorithm were right, it would only work for a very small group of small numbers, because one of your steps is multiplying all the numbers together.

I assume you are working with an architecture in which int's hold only up to 2**31-1. That isn't very big when you start multiplying several numbers together. For example, multiply together six number bigger than 35 and you're over that limit.

I think you should switch to a simpler algorithm.

Do you know a good algorithm for gcd of two numbers? If so, then a good algorithm for lcm of two numbers is:
lcm(a,b) = a/gcd(a,b) * b;

If you have a good algorithm for lcm of two numbers, you can easily use it for lcm of many numbers:
lcm(a,b,c,...) = lcm( lcm(a,b), c, ...)

You could compute that right in the input loop and never need to store the list of inputs. Assume you already defined a helper function lcm(a,b)

Code:

   int nResult = 1;
   for (int nIntake = 1; nIntake > 0; )
   {
      cin >> nIntake;
      if ( nIntake > 0 )
         nResult = lcm( nResult, nIntake );
   }

Alternately, here is a slightly more advanced syntax to show that same loop in a cleaner way:

Code:

   int nResult = 1;
   int nIntake;
   while ( cin >> nIntake, nIntake > 0 )
   {
      nResult = lcm( nResult, nIntake );
   }

I suspect I just did a bit more of your homework than is appropriate, but I didn't know another way to demonstrate the various lessons I hope you can learn from my post:

1) Notice how I used CODE tags. Use them the next time you post your own code.

2) Define and use helper functions. Don't write the whole algorithm in one sequence of steps.

3) Keep the limits of 32 bit integers in mind. In most cases, you should be able to hit the following goal:
If the inputs fit in 32 bit ints and the result fits in a 32 bit int, you ought to find a way to make the algorithm work without overflowing. Remember my example of six numbers each a little bigger than 35. Probably their lcm fits in a 32 bit int, even though their product doesn't. So you avoid overflow by avoiding computing unnecessarily large intermediate values, such as that product.
lcm(36,38,39,40,45,52) = 88920, which fits easily in an int
36*38*39*40*45*52 = 4993747200, which doesn't even fit in an unsigned int.

4) The harder but most important lesson is
Think more, code less.

rwalek668 · 01-08-2011, 02:42 PM

I tried to take your advice on all of those aspects and heres what i came up with instead, however i now have a different problem, the code i wrote only accepts two values despite the loop at the beggining and then it freezes, i think its bc the loop in the second part of the program doesn't terminate or something like that but i included the inequalities that should end up being completed.
the main code is:

Code:

int nIntake = 1;
   int nIntake1;
   cin >> nIntake1;
   for (int nIntake11, nIntake01;nIntake > 0; )
   {
      cin >> nIntake;
      if ( nIntake > 0 )
      {
         nIntake11 = nIntake1;
         nIntake01 = nIntake;
        int nGCF = LCM( nIntake1, nIntake );
         nIntake1 = (nIntake11 * nIntake01) / nGCF;
      }
   }

the part that i think the problem now is in is:

Code:

int LCM(int nIntake1, int nIntake)
{
    int nSubtractionCounter = 1
   for (;nIntake1!=0;)
   {
    if (nIntake1 > nIntake)
    {
        int nIntakeTemporary = nIntake1;
        nIntake1 = nIntake;
        nIntake = nIntakeTemporary;
    }
    for (;(nIntake > nIntake1) & (nIntake!=0) ;nSubtractionCounter++)
    {
        nIntake = nIntake - nIntake1;
    }
   }
    return nSubtractionCounter;
}

Snark1994 · 01-08-2011, 04:48 PM

What did you hope to achieve by

Code:

int LCM(int nIntake1, int nIntake)
{
    int nSubtractionCounter = 1
   for (;nIntake1!=0;)
   {
    if (nIntake1 > nIntake)
    {
        int nIntakeTemporary = nIntake1;
        nIntake1 = nIntake;
        nIntake = nIntakeTemporary;
    }
    for (;(nIntake > nIntake1) & (nIntake!=0) ;nSubtractionCounter++)
    {
        nIntake = nIntake - nIntake1;
    }
   }
    return nSubtractionCounter;
}

?

Firstly, I think you meant && instead of just & in the second for loop.

Secondly, it would look nicer and be more readable if you used while() instead of a for(;<condition>; ).

Thirdly, what exactly did you hope to do with the code? It certainly doesn't compute the LCM, and the loops are by no means guaranteed to finish. In fact, it will ONLY finish if nIntake1 = 0. Look at the code - you loop while it doesn't equal 0, and never change its value. Obviously, you can't compute LCM(0,x), because it makes no sense mathematically.

The code is... close. Playing around with it, I can kinda see that it's almost working, but I can't quite see what's going wrong. If I spot it, I'll post

However, Johnsfine has already told you a solution:

Quote:

Do you know a good algorithm for gcd of two numbers? If so, then a good algorithm for lcm of two numbers is:
lcm(a,b) = a/gcd(a,b) * b;

If you have a good algorithm for lcm of two numbers, you can easily use it for lcm of many numbers:
lcm(a,b,c,...) = lcm( lcm(a,b), c, ...)

A very good algorithm for the GCD of two numbers is the Euclidean algorithm - I suggest researching this then following Johnsfine's suggestion.

EDIT: *HEADSLAP* Duh, it's almost working. It's an almost-working *GCD* algorithm. Try this:

Code:

int GCD(int a, int b){
    while(a != b) {
        if (b > a) {
            int t = b;
            b = a;
            a = t;
        }
	while (a > b) {
            a = a - b;
	}
    }
    return a;
}

I got confused by your function name, 'LCM' - it's obviously a GCD algorithm as both numbers go down, not up

you were quite close, you just added a strange variable which you then returned, and got a test wrong. So... What I just posted should give you the correct GCD, now you should be able to use that in your other code

EDIT 2: Oh, right. Just read your other code, and saw you had "nGCF = LCM(blah blah". I should have read more... But still, LCM is a confusing function name for a function that calculates a GCD

johnsfine · 01-08-2011, 05:04 PM

Snark1994 explained the reason the program hangs, the loop

Code:

for (;nIntake1!=0;)

inside your LCM function. But even if you fix that:

Quote:

Originally Posted by rwalek668

Code:

int nIntake = 1;
   int nIntake1;
   cin >> nIntake1;
   for (int nIntake11, nIntake01;nIntake > 0; )
   {
      cin >> nIntake;

I don't understand what you're trying to accomplish with the four different nIntake variables.

Quote:

Code:

         nIntake11 = nIntake1;
         nIntake01 = nIntake;
        int nGCF = LCM( nIntake1, nIntake );
         nIntake1 = (nIntake11 * nIntake01) / nGCF;

The first time through that code, nIntake1 is an uninitialized variable. So nIntake11 has an unpredictable value, then you set nIntake1 based on a computation from unpredictable values, so it is garbage.

But also, you are using a helper function named LCM, but using it as if you expect it to compute the GCD rather than the LCM.

That seems to be a very common aspect of posted lcm homework attempts: People understand they want a GCD function as a helper for computing LCM, and they try to write such a function (sometime correctly, sometimes not), but they name it "LCM".

I've seen that so many times, and I still don't understand the thought process. A function that does a simple job like GCD should be named for that job. Don't confuse yourself plus anyone helping you by naming your GCD function LCM.

Quote:

Code:

int LCM(int nIntake1, int nIntake)
{
    int nSubtractionCounter = 1
   for (;nIntake1!=0;)
   {
    if (nIntake1 > nIntake)
    {
        int nIntakeTemporary = nIntake1;
        nIntake1 = nIntake;
        nIntake = nIntakeTemporary;
    }
    for (;(nIntake > nIntake1) & (nIntake!=0) ;nSubtractionCounter++)
    {
        nIntake = nIntake - nIntake1;
    }
   }
    return nSubtractionCounter;
}

What do you think nSubtractionCounter is accomplishing?

You have an almost correct GCD algorithm there (after fixing the outer loop). But that count means nothing. At the point nIntake becomes zero, the gcd is nIntake1, so that is what the function should return.

As Snark1994 said, you used & in a place where && is generally used. In fact that makes no difference to the behavior, but experienced programmers tend to be distracted by strange usage like that even when they don't matter. Also if you get in bad habits like that, you'll use & instead of && someplace it does matter. You should use & only for bitwise AND. Use && for logical AND.

One more extra detail:

Code:

nIntake1 = (nIntake11 * nIntake01) / nGCF;

If you were multiplying the correct two numbers and if nGCF were the correct greatest common factor, that sequence of operations is worse than dividing first. Divide either factor by the gcd, then multiply by the other. If you multiply first, you might overflow an int even when the final result would fit.

rwalek668 · 01-08-2011, 05:55 PM

Okay I got it to work now with your advice but the intake1 part did work without changes... do the values of Intake And Intake 1 change when I use the in LCM(Intake, Intake1)? or can I use them again in teh main function with them still being the user inputs?

Code:

nIntake11 = nIntake1;
         nIntake01 = nIntake;
        int nGCF = LCM( nIntake1, nIntake );
         nIntake1 = (nIntake11 * nIntake01) / nGCF;

I thought they changed and dont know how to use pointers yet so I assumed I had to intoroduce new variables to store their value and actually haha im not doing this for homewoirk, I just want to now how to program and so am reading some books and stuff. Thanks for all the help!

johnsfine · 01-08-2011, 06:59 PM

Quote:

Originally Posted by rwalek668

Okay I got it to work now with your advice but the intake1 part did work without changes.

An uninitialized stack local variable at the beginning of a simple program will usually be zero, and zero might work right.

But it is a bad idea to rely on things like that. Some small change elsewhere in the program (or maybe just running the same code after some Linux upgrade that changes the C startup code) can change the uninitialized value and make the program fail.

Quote:

.. do the values of Intake And Intake 1 change when I use the in LCM(Intake, Intake1)?

No, calling the function makes a copy of the function inputs. Changing the function inputs inside the function doesn't change the original values outside the function.

Now I understand why you had four variables doing the job of two.

Quote:

can I use them again

Yes. Now you should understand why you only needed two.

Quote:

Code:

nIntake11 = nIntake1;
         nIntake01 = nIntake;
        int nGCF = LCM( nIntake1, nIntake );
         nIntake1 = (nIntake11 * nIntake01) / nGCF;

So that whole thing could be replaced by

Code:

nIntake1 = nIntake1/LCM(nIntake1, nIntake) * nIntake;

You still should initialize nIntake1 before the loop.

Quote:

im not doing this for homewoirk,

Good. People should still give you concepts rather than complete code, but that makes it easier for us to illustrate concepts with partial code.

For example, Snark1994's sample GCD routine could be changed as follows to avoid needing a nested loop:

Code:

int GCD(int a, int b){
    while(a) {
        if (b > a) {
            int t = b;
            b = a;
            a = t;
        }
        else {
            a = a - b;
        }
    }
    return b;
}

Snark1994 mentioned earlier that lcm(0,x) doesn't make much sense but gcd(0,x) makes sense and should be x. Taking advantage of that makes the code simpler.