C++ how to efficiently multiply a range of numbers

[morper]

Hey!

I recently started learning C++, and as a beginner I have had alot of use of this forum since so many of beginner-type of questions have been asked and answered before.

I havent found the answer to a problem im currently facing thou. Im working on a program that will take 2 numbers as input from the user and let the user choose between some different options on how to calculate things using the users numbers.

One calculating option is to take the users numbers and calculating the product of the whole range of numbers inbetween the numbers.
For example, the user inputs 1 and 5. What I want to calculate is 1*2*3*4*5=120.

There might be a math term for what im trying to say but unfortunately my math is rusty (but im working on that =))

Anyhow, I have tried different ways to accomplish this calculation and I have found a working method althou im sure there is a more simple and efficient way to do it, and I really would like to hear your thoughts about this.

my code for the calculation:

int number1, number2;
    cout << "Please input 2 numbers" << endl;
    cin >> number1 >> number2;



    int i = number1, sum = number1;

    while ( i < number2 )
    {
        sum = sum * (i+1);
        cout << "The sum is " << sum << " and the value of i is " << i << endl;
        i++;
    }

    return 0;

Cheers,
morper

[giannhssdra]

you can try to do it with a for loop

int number1 , number2 , sum = 1;
cout<<"your message\n";
cin>>number1>>number2;

for( int i = number1 ; i <= number2 ; i++ )
         sum *= i;//its the same as     sum = sum * i;
cout<<"sum = "<<sum<<endl;

[hanst99]

Don't read this, I am an idiot that can't tell apart multiplication and addition. The only reason I leave this in is that it took me over 10 minutes to write this. To be fair, I was kinda confused by you calling your product a sum. Basically you could do pretty much the same thing I did here if there was a constant-time way to calculate faculty, but I don't think there is. At the very least I don't know it..

The sum of the range between two numbers is

(first + last) * (last - first + 1) / 2.

For example,

5+6+7 = 18
(5+7) * (7 - 5 + 1)/2 = 18.

Proof:

Lemma (1): The sum of all numbers from 1 to n is equal to (1+n) * n/2.
Induction:
Beginning: The sum from 1 to 1 is equal to (1+1) * 1/2. (true, obviously).
Assumption: The lemma is true for all n with 1<=n<=k.
Step: k -> k+1
The sum of all numbers from 1 to k+1 = sum of all numbers from 1 to k + k+1
= (1+k) * k/2 + k+1 (The bold part is a replacement that we can perform due to our assumption).
= (1+k) * k/2 + 2 * (k+1) / 2
= (k + k^2) / 2 + (2k + 2)/2
= (k^2 + 3k + 2) /2
= (k+2) * (k+1 ) /2 (DONE).

Now, the sum from n to k is equal to the sum from 1 to k - the sum from 1 to (n-1) (evidently true by definition).

So sum from n to k = (1 +k) * k/2 - n * (n-1) /2 (Lemma 1)
= ((1+k) * k - n *(n-1)) /2.
= (k +k^2 - n^2 +n ) /2
= (k^2 -n^2 + k + n) / 2
= ((k+n) * (k-n) + k + n) /2
= (k+n) *(k-n + 1) / 2
Q.E.D.

(Will probably not work with negative numbers, though I didn't bother to check).

[morper]

Thanks for the replies =)

giannhssdra - this was exactly was I was looking for. Thanks!

hanst99 - I can see why that can be confusing. Nice explanation, I didnt know that about addition thanks =)

[hanst99]

Well, I suppose the time didn't completely go to waste. Then again I do have a math exam next week so doing a small proof like that is probably a good practice (SOMETHING like this will be asked, at least I'm pretty sure it will).