Самый быстрый способ найти сумму десятичных цифр

Question

Какой самый быстрый способ найти сумму десятичных цифр?Следующий код - это то, что я написал, но он очень и очень медленный для диапазона 1 to 1000000000000000000

long long sum_of_digits(long long input) {
    long long total = 0;
    while (input != 0) {
        total += input % 10;
        input /= 10;
    }
    return total;
}

int main ( int argc, char** argv) {
    for ( long long i = 1L; i <= 1000000000000000000L; i++) {
        sum_of_digits(i);
    }
    return 0;
}

Answer 1

Редактировать: Кажется, вам нужна сумма действительных цифр, такая что: 12345 = 1 + 2 + 3 + 4 + 5 не количество цифр или сумма всех чисел от 1 до 12345 (включительно);

Таким образом, самое быстрое, что вы можете получить:

long long sum_of_digits(long long input) {
    long long total = input % 10;
    while ((input /= 10) != 0)
        total += input % 10;
    return total;
}

Что все еще будет медленным, когда вы выполняете достаточно итераций. Ваше требование в 1 000 000 000 000 000 000 л итераций составляет один миллион, миллион, миллион. Учитывая, что на моем компьютере 100 миллионов занимает около 10000 мс, можно ожидать, что на 1 млн записей потребуется 100 мс, а вы хотите сделать это еще миллион миллионов раз. В день всего 86400 секунд, поэтому в лучшем случае мы можем вычислять около 86,400 миллионов записей в день. Это займет один компьютер

Предположим, что ваш метод может быть выполнен в одной операции с плавающей запятой (каким-то образом), предположим, что вы используете компьютер K, который в настоящее время является самым быстрым (Rmax) суперкомпьютером со скоростью более 10 петафлопс, если вы выполняете математику, равную = 10 000 миллионов Миллион плавающих операций в секунду. Это означает, что для цикла «1 миллион, миллион, миллион» потребуется самый быстрый в мире нераспределенный суперкомпьютер за 100 секунд для вычисления сумм (если для вычисления потребовалась 1 операция с плавающей запятой, а это невозможно), поэтому вам придется подождать около на какое-то время компьютеры становятся на 100% более мощными, чтобы ваше решение работало менее чем за одну секунду.

Что бы вы ни пытались сделать, вы либо пытаетесь решить неразрешимую проблему почти в реальном времени (например, связанные с графикой), либо неправильно поняли заданный вам вопрос / задачу, или вас ожидают выполнять что-то быстрее, чем любая (не распределенная) компьютерная система.

Если ваша задача на самом деле сложить все цифры диапазона, как вы показываете, а затем вывести их, ответ не в том, чтобы улучшить цикл for. например:

1 = 0
10 = 46
100 = 901
1000 = 13501
10000 = 180001
100000 = 2250001
1000000 = 27000001
10000000 = 315000001
100000000 = 3600000001

Исходя из этого, вы могли бы разработать формулу для фактического вычисления общей суммы всех цифр для всех чисел от 1 до N. Но не совсем понятно, чего вы действительно хотите, кроме гораздо более быстрого компьютера.

Answer 2

Если вы хотите найти сумму для диапазона, скажем, от 1 до N, просто выполните следующее

long sum = N(N+1)/2;

это самый быстрый способ.