Modular sum of square numbers in C++

Question

So I've got an assignment which sounds like this:

Given a number n, calculate the result of this sum, modulo 10,234,573:
1² + 2² + 3² + ... + n²

This is what I've come up with :

 #include <iostream>
 using namespace std;
 int main()
 {
 uint n;
 cin >> n;
 uint num{10234573};
 uint64_t sum{0};
 for (uint i = 1; i <= n; ++i) {
 sum += (i*i)%num;
 sum %= num;
 }
 cout << sum;
 return 0;
 }

And I can check my algorithm on a website, but it tells me that it is "too slow"... How can I optimise it so it will be faster? I know there is a formula for this, but the given number n can be as big as 2,000,000,000, so it will obviously overflow...

• Incomputable: There is a formula for the sum of series you described. Google for it or find yourself.
• Semetg: And I just said that it would overflow if, for example, n is 2,000,000,000...
• Incomputable: It is not hard to solve that either. No googling = no learning.
• Semetg: Then could you please give me an idea of how could I do it?
• Incomputable: it is better to learn to search for that yourself. You need a fishing rod, not fish. The answer lies in properties of modulo.

Answer 1

Headers

You'll need to include <cstdint> to get a definition of uint64_t. Actually, uint_fast64_t is probably a better choice, as it's fine if we have a wider type.

Avoid using namespace std;

Importing all names of a namespace is a bad habit to get into, and can cause surprise when names like begin and size are in the global namespace. Get used to using the namespace prefix (std is intentionally very short), or importing just the names you need into the smallest reasonable scope.

The exceptions to this rule are namespaces explicitly intended to be imported wholesale, such as the std::literals namespaces.

Separate I/O from computation

Instead of bashing everything into your main() function, it's better to provide a pure function that's amenable to unit tests, and separately provide the means to drive that from positional parameters, standard input, file streams, GUI, etc.

Use appropriate types

uint isn't a standard type; I'm guessing from the name that it's declared as an alias for unsigned int - in which case the minimum guaranteed UINT_MAX (65535) may not be sufficient for the problem requirements. I think we should be using the same type for i and n as for sum.

Use a more efficient algorithm

There is a simple formula for computing a Square pyramidal number: (2n3 + 3n2 + n) / 6. We can use this, as long as we keep intermediate values between 0 and UINT_FAST64_MAX (since 102345732 < 264, this can be done by reducing mod m before multiplying).

---

Cleaned-up version

Applying all bar the last recommendation (and with input from arguments, for easier testing), I have:

#include <cstdint>
using Number = uint_fast64_t;
Number pyramidal_modn(Number number, Number modulus)
{
 Number sum{0};
 for (Number i = 1; i <= number; ++i) {
 sum += (i*i) % modulus;
 sum %= modulus;
 }
 return sum;
}
#include <iostream>
int main(int argc, char **argv)
{
 static const Number m = 10234573;
 for (int i = 1; i < argc; ++i) {
 Number n = std::stoul(argv[i]);
 std::cout << n << ": " << pyramidal_modn(n, m) << '\n';
 }
 // test a large value
 const Number t = 123456798;
 return pyramidal_modn(t, m) != (pyramidal_modn(t-1, m) + t*t) %m;
}

We can now substitute with a more efficient implementation without changing any other code (in particular, without disturbing the tests):

constexpr Number pyramidal_modn(Number n, Number m)
{
 n %= m;
 auto n2 = n*n % m;
 auto n3 = n2*n % m;
 return (2*n3 + 3*n2 + n) / 6;
}

Note that we're now able to give it the constexpr qualifier.

(Exercise: why did we not need % m in the return statement?)

• Semetg: Well, n will be smaller than m, the same for n2 and n3... if we add 3 numbers smaller than m and then divide them by 6 the result will obviously be smaller than m. Am I right? Edit: in the worst case, n will be m-1 and let’s just say it could be the same for n2 and n3, so it will be 6*(m-1)/6, in the worst case scenario.
• Toby Speight: Yes, that's right - we're adding 6 numbers smaller than m (6 not 3, because of the 2* and the 3*), then dividing by 6, so the result can't exceed m.

Answer 2

To use the modulo in equations, You need to maintain the equivalence of the Equation. The Equation you wrote in comment is not according to equivalence. See Division Under Equivalences

So, going by the equivalence you have to calculate it like this :

[ ( (n) %x ) * ( (n+1) %x ) * ( ( 2*n + 1 ) %x ) ) * ( (1/6)%x ) ] %x

Have a look at this.

Note that this will not work If given n is any multiple of x. So, n & x must be Co-prime. In your case, x = 10234573 is already a prime number as pointed by Toby's Comment

• Toby Speight: 10234573 is clearly prime, which simplifies the reasoning.
• Semetg: Oh you’re right, you’re the only one who actually explained to me how does the distributivity of the modulus operator work. Thanks a lot !