1
\$\begingroup\$

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

Given a number n, calculate the result of this sum, modulo 10,234,573:
12 + 22 + 32 + … + n2

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...

\$\endgroup\$
7
  • \$\begingroup\$ There is a formula for the sum of series you described. Google for it or find yourself. \$\endgroup\$ Dec 17 '17 at 14:38
  • \$\begingroup\$ And I just said that it would overflow if, for example, n is 2,000,000,000... \$\endgroup\$
    – Semetg
    Dec 17 '17 at 14:39
  • \$\begingroup\$ It is not hard to solve that either. No googling = no learning. \$\endgroup\$ Dec 17 '17 at 14:39
  • \$\begingroup\$ Then could you please give me an idea of how could I do it? \$\endgroup\$
    – Semetg
    Dec 17 '17 at 14:40
  • 1
    \$\begingroup\$ it is better to learn to search for that yourself. You need a fishing rod, not fish. The answer lies in properties of modulo. \$\endgroup\$ Dec 17 '17 at 14:41
0
\$\begingroup\$

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: (2n³ + 3n² + n) / 6. We can use this, as long as we keep intermediate values between 0 and UINT_FAST64_MAX (since 10234573² < 2⁶⁴, 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?)

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Semetg
    Dec 18 '17 at 14:17
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 18 '17 at 15:29
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ 10234573 is clearly prime, which simplifies the reasoning. \$\endgroup\$ Dec 18 '17 at 14:04
  • \$\begingroup\$ 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 ! \$\endgroup\$
    – Semetg
    Dec 18 '17 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.