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

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

Я предполагаю, что вы пытаетесь сделать это в соответствии с

#include <iostream>
const long long limit = 1000000000000000000LL;
int main () {
   long long grand_total = 0;
   for (long long ii = 1; ii <= limit; ++ii) {
      grand_total += sum_of_digits(i);
   }
   std::cout << "Grand total = " << grand_total << "\n";
   return 0;
}

Это не сработает по двум причинам:

• Это займет много времениlong time.
• Переполнение.

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

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

Сначала рассмотрим задачу вычисления суммы цифр всех целых чисел от 0 до 10 ⁿ -1 (например, от 0 до 9 (n = 1), от 0 до 99 (n = 2) и т. Д.) Обозначим сумму цифр всех целых чисел от 10 ⁿ -1 как S _{п * * тысяча двадцать-один.Для n = 1 (от 0 до 9) это просто 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 (9 * 10/2).Таким образом, S 1 = 45.}

Для n = 2 (от 0 до 99) вы суммируете 0-9 раз и снова суммируете 0-9 раза.Для n = 3 (от 0 до 999) вы суммируете 0-99 раз и суммируете 0-9 100 раз.Для n = 4 (от 0 до 9999) вы суммируете 0-999 раз и суммируете 0-9 1000 раз.В общем случае S _n = 10S _n-1 + 10 ^n-1 S ₁ в качестве рекурсивного выражения.Это упрощается до S _n = (9n10 ⁿ ) / 2.

Если верхний предел имеет вид 10 ⁿ , решениеэто выше S _n плюс еще один для числа 1000 ... 000.Если верхний предел - произвольное число, вам нужно будет проявить творческий подход еще раз.Подумайте в том же духе, что и при разработке формулы для S _n .

Answer 2

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

Примечание - 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = N (N + 1) / 2 = 45.

---- Изменение ответачтобы прояснить ситуацию после комментария Дэвида

См. ответ Дэвида - я ошибся

Answer 3

Вы можете разбить это рекурсивно.Сумма цифр из 18-значного числа представляет собой сумму первых 9 цифр плюс последние 9 цифр.Аналогично, сумма цифр 9-битного числа будет суммой первых 4 или 5 цифр плюс сумма последних 5 или 4 цифр.Естественно, вы можете особый случай, когда значение равно 0.

Answer 4

Чтение ваших правок: вычисление этой функции в цикле для i от 1 до 1000000000000000000 занимает много времени. Это ежу понятно.

1000000000000000000 - это один миллиард миллиардов. Ваш процессор сможет выполнять в лучшем случае миллиарды операций в секунду. Даже с несуществующим процессором 4-5 ГГц и в лучшем случае он компилируется в сложение, мод, div и скачок сравнения, вы можете делать только 1 миллиард итераций в секунду, то есть он будет иметь порядок 1 миллиард секунд.

Answer 5

Довольно поздно на вечеринку, но в любом случае, вот мое решение. Извините, это на Python, а не на C ++, но его должно быть относительно легко перевести. И поскольку это в первую очередь проблема алгоритма, я надеюсь, что все в порядке.

Что касается проблемы переполнения, то единственное, что приходит на ум, - это использовать массивы цифр вместо реальных чисел. Учитывая этот алгоритм, я надеюсь, что он не сильно повлияет на производительность.

https://gist.github.com/frnhr/7608873

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

отношение 1

Сокращает количество вызовов функций с произвольным аргументом до нескольких рекурсивных вызовов с более предсказуемыми аргументами для использования в отношениях 2 и 3.

foo(3456) == foo(3000)
           + foo(400) + 400 * (3)
           + foo(50) + 50 * (3 + 4)
           + foo(6) + 6 * (3 + 4 + 5)

Отношение 2

Сокращение вызовов с аргументом в форме L*10^M (например, 30, 7000, 900000) до рекурсивного вызова, используемого для отношения 3. Эти треугольные числа появились совершенно незваными (но приветствуются) :)

triangular_numbers = [0, 1, 3, 6, 10, 15, 21, 28, 36]  # 0 not used
foo(3000) == 3 * foo(1000) + triangular_numbers[3 - 1] * 1000

Полезно только если L > 1. Это верно для L = 1, но тривиально. В этом случае перейдите непосредственно к соотношению 3.

отношение 3

Рекурсивно сокращать вызовы с аргументом в формате 1*10^M до вызова с аргументом, который делится на 10.

foo(1000) == foo(100) * 10 + 44 * 100 + 100 - 9  # 44 and 9 are constants

В конечном итоге вам нужно только реально рассчитать сумму или цифры для чисел от 0 до 10, и получается, что требуется только до 3 из этих вычислений. Все остальное решается с помощью этой рекурсии. Я почти уверен, что он запускается в O(logN) время. Это ФАСТ !!!!! 11one

На моем ноутбуке он вычисляет сумму цифр для данного числа с более чем 1300 цифрами менее чем за 7 секунд! Ваш тест (1000000000000000000) рассчитывается за 0,000112057 секунд!

Answer 6

Возможность 1:

Вы могли бы сделать это быстрее, передав результат одной итерации цикла в следующую итерацию.

Например, если i == 365, результат будет 14. В следующем цикле i == 366 - на 1 больше, чем в предыдущем результате. Сумма также еще 1: 3 + 6 + 6 = 15.

Проблемы возникают при наличии цифры переноса. Если i == 99 (т.е. result = 18), результатом следующего цикла будет не 19, а 1. Вам понадобится дополнительный код для обнаружения этого случая.

Возможность 2:

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

Однако, как отмечали некоторые другие: даже при самой быстрой реализации sum_of_digits и наиболее оптимизированном циклическом коде невозможно вычислить результаты 1000000000000000000 в любой полезный период, и, конечно, не менее чем за одну секунду .

Answer 7

Вам нужно будет обмануть - ищите математические шаблоны, которые позволят вам сократить ваши вычисления.

• Например, вам действительно нужно каждый раз проверять этот ввод! = 0?Имеет ли значение, если вы добавите 0/10 несколько раз?Так как это не имеет значения, рассмотрите возможность развертывания цикла.
• Можете ли вы сделать расчет на большей базе, например, на базе 10 ^ 2, 10 ^ 3 и т. Д., Которая может позволить вам уменьшить количествоцифры, которые вы затем должны будете преобразовать в базу 10?Если это сработает, вам будет проще реализовать кэш.
• Рассмотрите возможности встроенного компилятора, которые позволяют давать подсказки компилятору для прогнозирования ветвлений.
• Учитывая, что это C ++рассмотрите возможность реализации этого с помощью шаблонного метапрограммирования.
• Учитывая, что sum_of_digits является чисто функциональным, рассмотрите возможность кэширования результатов.

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

Это, вероятно, отличная отправная точка, если вы хотите исследовать это подробно: http://mathworld.wolfram.com/DigitSum.html

Answer 8

Я думаю, что вы не можете сделать лучше, чем O(N), где N is the number of digits in the given number (что не дорого в вычислительном отношении)

Однако, если я правильно понял ваш вопрос (диапазон), вы хотите вывести сумму цифр длядиапазон чисел.В этом случае вы можете увеличить на единицу при переходе с номера 0 на номер 9, а затем уменьшить на 8.

Answer 9

Не самый лучший, но простой:

int DigitSumRange(int a, int b) {
    int s = 0;
    for (; a <= b; a++)
        for(c : to_string(a)) 
            s += c-48;

    return s;
}

Answer 10

Формула для нахождения суммы цифр чисел от 1 до N:

(1 + N) * (N / 2)

http://mathforum.org/library/drmath/view/57919.html

Существует класс, написанный на C #, который поддерживает число с более чем поддерживаемым максимальным пределом long.Вы можете найти это здесь. Oyster.Math

Используя этот класс, я сгенерировал блок кода на c #, может быть вам он поможет.

using Oyster.Math;
class Program
{
    private static DateTime startDate;
    static void Main(string[] args)
    {
        startDate = DateTime.Now;
        Console.WriteLine("Finding Sum of digits from {0} to {1}", 1L, 1000000000000000000L);
        sum_of_digits(1000000000000000000L);
        Console.WriteLine("Time Taken for the process: {0},", DateTime.Now - startDate);
        Console.ReadLine();
    }

    private static void sum_of_digits(long input)
    {
       var answer = IntX.Multiply(IntX.Parse(Convert.ToString(1 + input)), IntX.Parse(Convert.ToString(input / 2)), MultiplyMode.Classic);
        Console.WriteLine("Sum: {0}", answer);
    }
}

Пожалуйста, игнорируйте этопрокомментируйте, если это не относится к вашему контексту.