Самый быстрый способ суммировать цифры в числе

Question

Учитывая большое количество, например 9223372036854775807 (Int64.MaxValue), какой самый быстрый способ сложить цифры?

В настоящее время я выполняю ToStringing и перекомпоновываю каждый символ в int:

num.ToString().Sum(c => int.Parse(new String(new char[] { c })));

Что, безусловно, ужасно неэффективно. Есть предложения?

И, наконец, как бы вы сделали эту работу с BigInteger?

Спасибо

Answer 1

Ну, другой вариант:

int sum = 0;
while (value != 0)
{
    int remainder;
    value = Math.DivRem(value, 10, out remainder);
    sum += remainder;
}

BigInteger также имеет метод DivRem, поэтому вы можете использовать тот же подход.

Обратите внимание, что я видел DivRem не так быстро, как делать ту же арифметику "вручную", поэтому, если вы действительно заинтересованы в скорости, вы можете подумать об этом.

Также рассмотрим справочную таблицу с (скажем) 1000 элементов, предварительно вычисленных с помощью сумм:

int sum = 0;
while (value != 0)
{
    int remainder;
    value = Math.DivRem(value, 1000, out remainder);
    sum += lookupTable[remainder];
}

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

Answer 2

Никто не обсуждал версию BigInteger. Для этого я бы посмотрел на 10 ¹ , 10 ² , 10 ⁴ , 10 ⁸ и так далее, пока вы не найдете последний 10 ^{2 n} , что меньше вашего значения. Возьмите ваш номер div и мод 10 ^{2 n} , чтобы получить 2 меньших значения. Вымойте, сполосните и повторите рекурсивно. (Вы должны хранить свои повторяющиеся квадраты 10 в массиве, а в рекурсивной части передавать информацию о следующей используемой мощности.)

Для BigInteger с k цифрами деление на 10 равно O (k). Поэтому нахождение суммы цифр с помощью наивного алгоритма равно O (k ² ).

Я не знаю, что C # использует внутренне, но не наивные алгоритмы для умножения или деления k-бита на k-битное целое все работают за время O (k ^1.6 ) или лучше (большинство намного, намного лучше, но имеют издержки, которые делают их хуже для «маленьких больших целых чисел»). В этом случае подготовка вашего начального списка степеней и разделение за один раз занимает время O (k ^1.6 ). Это дает вам 2 задачи размера O ((k / 2) ^1.6 ) = 2 ^-0.6 O (k ^1.6 ). На следующем уровне у вас есть 4 задачи размера O ((k / 4) ^1.6 ) для другой 2 ^-1.2 O (k ^1.6 ). Сложите все слагаемые и степени 2 превращаются в геометрический ряд, сходящийся к константе, поэтому общая работа составляет O (k ^1.6 ).

Это определенный выигрыш, и выигрыш будет очень и очень очевидным, если вы работаете с числами из многих тысяч цифр.

Answer 3

Первое правило оптимизации производительности: не делите, когда вы можете умножить вместо этого. Следующая функция будет принимать четыре цифры 0-9999 и делать то, что вы просите. Промежуточные вычисления превышают 16 бит. Мы умножаем число на 1/10000 и принимаем результат как число с фиксированной точкой Q16. Затем цифры извлекаются умножением на 10 и принятием целочисленной части.

#define TEN_OVER_10000 ((1<<25)/1000 +1) // .001 Q25

int sum_digits(unsigned int n)
{
    int c;
    int sum = 0;
    n = (n * TEN_OVER_10000)>>9; // n*10/10000 Q16
    for (c=0;c<4;c++)
    {
    printf("Digit: %d\n", n>>16);
        sum += n>>16;
        n = (n & 0xffff) * 10; // next digit
    }
    return sum;
}

Это может быть расширено до больших размеров, но это сложно. Необходимо убедиться, что округление при расчете с фиксированной точкой всегда работает правильно. Я также сделал 4-значные числа, чтобы промежуточный результат умножения с фиксированной точкой не переполнялся.

Answer 4

Да, это, вероятно, несколько неэффективно. Вероятно, я бы просто несколько раз делил на 10, складывая остатки каждый раз.

Answer 5

Вместо int.parse, почему бы не вычесть '0' из каждой цифры, чтобы получить фактическое значение.

Помните, что '9' - '0' = 9, так что вы должны иметь возможность сделать этов порядке k (длина числа).Вычитание - это всего лишь одна операция, так что это не должно замедлять процесс.

Answer 6

    Int64 BigNumber = 9223372036854775807;

    String BigNumberStr = BigNumber.ToString();
    int Sum = 0;

    foreach (Char c in BigNumberStr)
        Sum += (byte)c;

    // 48 is ascii value of zero
    // remove in one step rather than in the loop
    Sum -= 48 * BigNumberStr.Length;