Grade 12 · Math for programmingCitește în română

Sum of an arithmetic progression: formula vs. loop

Original: Suma unei progresii aritmetice: formulă vs. buclă

O(1)C++1753 lines2 examples

The idea

The progression has first term a, common difference r and n terms: a, a + r, ..., a + (n-1) * r. The loop adds the terms one by one, so it takes n steps. Gauss's formula gives directly S = n * a + r * n * (n-1) / 2 (the product n * (n-1) is always even, so the division is exact). The program computes the sum both ways, so you can see they give the same result; for n = 10^12 the loop would take minutes, the formula answers instantly. First line: the formula, second: the loop.

Original description (Romanian)

Progresia are primul termen a, rația r și n termeni: a, a + r, ..., a + (n-1) * r. Bucla adună termenii unul câte unul, deci face n pași. Formula lui Gauss dă direct S = n * a + r * n * (n-1) / 2 (produsul n * (n-1) este mereu par, deci împărțirea e exactă). Programul calculează suma în ambele feluri, ca să vezi că dau același rezultat; pentru n = 10^12 bucla ar dura minute, formula răspunde instant. Prima linie: formula, a doua: bucla.

Complexity
O(1) with the formula, O(n) with the loop
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

1 1 100

Expected output

5050
5050
Example 2

Input

3 4 1000000

Expected output

2000001000000
2000001000000

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

suma-progresiei-formula-vs-bucla.cpp
/*
 * Titlu: Suma unei progresii aritmetice: formulă vs. buclă
 * Clasa: 12
 * Capitol: Matematică pentru programare
 * Descriere: Progresia are primul termen a, rația r și n termeni: a, a + r, ...,
 *            a + (n-1) * r. Bucla adună termenii unul câte unul, deci face n
 *            pași. Formula lui Gauss dă direct S = n * a + r * n * (n-1) / 2
 *            (produsul n * (n-1) este mereu par, deci împărțirea e exactă).
 *            Programul calculează suma în ambele feluri, ca să vezi că dau
 *            același rezultat; pentru n = 10^12 bucla ar dura minute, formula
 *            răspunde instant. Prima linie: formula, a doua: bucla.
 * Complexitate: O(1) cu formula, O(n) cu bucla
 *
 * Exemplu
 * Intrare: 1 1 100
 * Ieșire:
 * 5050
 * 5050
 *
 * Exemplu
 * Intrare: 3 4 1000000
 * Ieșire:
 * 2000001000000
 * 2000001000000
 */
#include <iostream>
using namespace std;

long long sumaFormula(long long a, long long r, long long n)
{
    return n * a + r * (n * (n - 1) / 2);
}

long long sumaBucla(long long a, long long r, long long n)
{
    long long s = 0, termen = a;
    for (long long i = 1; i <= n; i++)
    {
        s += termen;
        termen += r;
    }
    return s;
}

int main()
{
    long long a, r, n;
    cin >> a >> r >> n;
    cout << sumaFormula(a, r, n) << '\n';
    cout << sumaBucla(a, r, n) << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.