Как ускорить вычисления?

Question

Вот краткий код, который вычисляет сумму всех квадратных чисел (на самом деле это не сумма квадратов) до n, где n может быть до 10 Pow 20.

    long long res=0;
    long long sm=0;

    for (long long i = 1; res <=n; i=i+2)
    {
        res = (res+i);
        sm  = sm+(res*(n/res));

    }

Как заставить работать приведенный выше код Быстрее? Здесь вычисление sm занимает время для очень большого n, например 10 pow 20.

Есть ли способ, которым вычисление sm может быть сделано быстрее?

Здесь res вычисляет все квадраты числа типа 1,4,9,16,25 ....

скажем, n = 10, затем квадраты 1,4,9, а затем по приведенному выше коду sm (1) (10 /4)+(4)(10/4)+(9)(10/9)=27.

1 * 10 + 4 * 2 + 9 * 1 = 27.

Здесь деление является целочисленным делением.

edit1:

Мне нужно вычислить sm, упомянутый в коде выше.

здесь sm is суммирование ( i ² * этаж (n / (i ² )) ), где i = 1 до sqrt (n)

Answer 1

Есть ли способ, что вычисление sm может быть сделано быстрее?

Если вы заметили шаблон и примените немного математики, да.

Следующий идеал квадрат после вашего самого первого идеального квадрата (1 во всех случаях, кроме n==0) будет квадратом ceil(sqrt(first number)).

Другими словами, квадрат root, скажем, n-го числа, в соответствии с вашим первым числом будет дан как pow(ceil(sqrt(L)), n).

Теперь обратите внимание на шаблон между квадратами: 0 1 4 9 16 25 ...
Разница между 0 и 1 составляет 1
Разница между 1 и 4 составляет 3
Разница между 4 и 9 составляет 5
Разница между 9 и 16 составляет 7
Разница между 16 и 25 равна 9 и т. Д.

Это дает понять, что разница между двумя идеальными квадратами всегда является нечетным числом.

Продолжая это знание, вы нужно знать, что нужно добавить, чтобы получить следующее число, ответ на который (sqrt(square) * 2) + 1).

, т. е. current_square + (sqrt(current_square)*2+1) = next_square.

Например, и чтобы доказать это уравнение, рассмотрим идеальный квадрат 25. При применении этой логики c следующий идеальный квадрат будет 25 + (sqrt (25) * 2 + 1) = 36, что правильно. Здесь 11 добавляется к 25, что является нечетным числом.

Точно так же, если вы следуете этой тенденции, вы увидите, что все эти числа странные, с разницей +2. Чтобы найти следующий квадрат 2, вам нужно добавить к нему (sqrt (2 ² ) + 1) = 5 (4 + 5 = 9); для нахождения следующего квадрата (т.е. для 3) вам нужно добавить к нему (sqrt (3 ² + 1) = 7 (9 + 7 = 16). Разница всегда +2.

Кроме того, суммирование нечетного числа или применение сложения в вычислительном отношении обходится дешевле, чем умножение или нахождение квадратных корней каждого числа, поэтому ваша сложность должна быть в порядке.

---

После этого сделайте это :

• Соберите первый квадрат. (В идеале должно быть 1, но если условие n>0 не упомянуто, примените условие if(n!=0) к моим логам c)
• Назначьте разницу следующего термина как first_square*2+1. Вам нужно будет добавить первый квадрат, так как это не следующий квадрат, а разница между следующим квадратом и текущим квадратом. Добавьте термин в al oop, как я сделал ниже.
• Запустите al oop до нужного вам числа. Соберите необходимую сумму, заданную (square*floor(n/square), в переменной внутри l oop.
• Следуйте подходу, который я упоминал выше , т.е. добавить текущий квадрат к next тер м (разница между текущим и следующим квадратом) и увеличение следующего квадрата на 2.

Рабочий пример для вышеупомянутых логик c:

#include <iostream>
#include <cmath>
#define ll long long 
int main() 
{ 
    ll int n; 
    std::cin>>n;

   // Start from 1: (add case for 0 if input is not >0)
   // you can also start from any other square or define a range.
    ll int first = 1; 

   // Square it:
    ll int first_square = first * first; 

   // Find next square:
    ll int next = (first_square * 2) + 1; 

   // Initialize variable to collect your required sum:
    ll int sum = 0;
    ll int square = first_square;

    while ((square >= 0 && square <= n)) 
    {  
        sum += (square *floor(n/square));

        // Add the perfect square: 
        square += next; 

        // Next odd number to be added:
        next += 2;      
    }     
    std::cout<<sum;  
    return 0; 
} 

Answer 2

мы можем найти сумму всех квадратов до n, используя формулу:

n * (n + 1) * (2 * n + 1) / 6

long summation(long n) 
{ 
    return (n * (n + 1) *  
        (2 * n + 1)) / 6; 
}