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

algorithm math sum iteration digit

8538 просмотра

4 ответа

Некоторое время назад я видел вопрос на математическом форуме, где человек снова и снова обсуждал сложение цифр в числе, пока не будет достигнута одна цифра. (т. е. «362» станет «3 + 6 + 2», который станет «11» ... тогда «11» станет «1 + 1», станет «2»), а «362» вернет 2 ... Я написал хороший код, чтобы получить ответ на этот вопрос, и разместил его только для того, чтобы его обошел пользователь, который предположил, что любое число в модуле 9 равно этой «бесконечной сумме цифр», я проверил его, и он был прав ... хорошо почти верно, если ноль был возвращен, вы должны были поменять его на «9», но это было очень быстро исправить ...

362 = 3 + 6 + 2 = 11 = 1 + 1 = 2

или же...

362% 9 = 2

В любом случае, метод mod9 отлично работает для бесконечного добавления суммы цифр, пока вы не останетесь с одной цифрой ... но как насчет сделать это только один раз (то есть 362 просто вернет "11") ... Может кто-нибудь подумать быстрых алгоритмов?

Автор: Albert Renshaw Источник Размещён: 12.11.2019 09:25

Ответы (4)


5 плюса

Решение

Есть крутой трюк для суммирования 1 цифры в двоичном виде и с целым числом фиксированной ширины. На каждой итерации вы разделяете половину цифр на два значения, сдвигаете бит на одно значение вниз и затем добавляете. Первая итерация, отделяйте любую другую цифру. Вторая итерация, пары цифр и так далее.

Учитывая, что 27 является 00011011 как 8-разрядный двоичный файл, процесс ...

00010001 + 00000101 = 00010110  <-  every other digit step
00010010 + 00000001 = 00010011  <-  pairs of digits
00000011 + 00000001 = 00000100  <-  quads, giving final result 4

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

02040608 + 01030507 = 03071115  <-  every other digit
00070015 + 00030011 = 00100026  <-  pairs
00000026 + 00000010 = 00000036  <-  quads, final result

Так что 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36, что правильно, но вы можете сделать это эффективно, только если ваше числовое представление имеет десятичную фиксированную ширину. Это всегда занимает lg (n) итераций, где lg означает основание два логарифма, и вы округляете вверх.

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

Если вы посчитаете однозначные добавления, то здесь действительно больше работы, чем простой цикл. Идея, как и в случае с побитовым трюком для подсчета битов, состоит в том, чтобы переупорядочить эти сложения (используя ассоциативность), а затем вычислить как можно большее количество параллелей, используя одно сложение полной ширины для реализации двух сложений половинной ширины: четыре сложения на четверть ширины и т. д. Существуют значительные издержки для операций по очистке и смещению цифр, и даже больше, если вы реализуете это как цикл (вычисление или поиск значений маскирования цифр и расстояния сдвига для каждого шага). «Цикл», вероятно, должен быть полностью развернут, и эти маски и расстояния сдвига должны быть включены в код в качестве констант, чтобы избежать этого.

Процессор с поддержкой Binary Coded Decimal (BCD) может справиться с этим. Маскирование цифр и сдвиг цифр будут реализованы с использованием маскирования битов и сдвига битов, поскольку каждая десятичная цифра будет закодирована в 4 (или более) битах, независимо от кодирования других цифр.

Одна из проблем заключается в том, что поддержка BCD в наши дни довольно редка. Раньше это было довольно распространенным явлением в 8-битные и 16-битные дни, но, насколько я знаю, процессоры, которые все еще поддерживают его, теперь делают это главным образом для обратной совместимости. Причины включают в себя ...

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

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

  3. По мере того как числа увеличиваются, даже упакованные BCD упаковываются неэффективно. Числовые представления базы 10 ^ x обладают наиболее важными свойствами базы 10 и легко декодируются как десятичные. Base 1000 требуется только 10 бит на три цифры, а не 12, потому что 2 ^ 10 - это 1024. Этого достаточно, чтобы показать, что вы получаете дополнительную десятичную цифру для 32 бит - 9 цифр вместо 8 - и у вас еще осталось 2 бита Например, для знакового бита.

Дело в том, что для того, чтобы этот алгоритм суммирования цифр был вообще полезен, вам нужно работать с десятичной дробью фиксированной ширины, вероятно, не менее 32 бит (8 цифр). Это дает 12 операций (6 масок, 3 смены, 3 сложения), а не 15 сложений для (полностью развернутого) простого цикла. Однако это пограничный выигрыш - и другие проблемы в коде могут легко означать, что он на самом деле медленнее.

Прирост эффективности более ясен при 64 битах (16 десятичных цифр), поскольку в нем все еще только 16 операций (8 масок, 4 смены, 4 сложения), а не 31, но шансы найти процессор, поддерживающий 64-битные операции BCD, кажутся незначительными. И даже если бы вы это сделали, как часто вам это нужно? Кажется маловероятным, что это может стоить усилий и потери портативности.

Автор: Steve314 Размещён: 19.02.2013 05:52

1 плюс

Вот что-то в Хаскеле:

sumDigits n = 
  if n == 0 
     then 0
     else let a = mod n 10
          in a + sumDigits (div n 10)

О, но я только что прочитал, что ты уже это делаешь ...

(тогда есть и очевидное:

sumDigits n = sum $ map (read . (:[])) . show $ n

)

Автор: גלעד ברקן Размещён: 19.02.2013 05:35

1 плюс

Для краткого кода попробуйте это:

int digit_sum(int n){
    if (n<10) return n;
    return n%10 + digit_sum(n/10);
}

Или, на словах,

-Если число меньше десяти, то сумма цифр - это само число.

-Иначе, сумма цифр - это текущая последняя цифра (или n mod10 или n% 10), плюс сумма цифр всего слева от этого числа (n делится на 10, используя целочисленное деление).

-Этот алгоритм также может быть обобщен для любой базы, заменяя базу на 10.

Автор: user2016670 Размещён: 04.04.2013 04:07

0 плюса

int digit_sum(int n)
Do
    if (n<10) return n;
    Exit do
    else

    n=n%10 + digit_sum(n/10);

Loop 
Автор: Arun Размещён: 08.04.2013 04:35
Вопросы из категории :
32x32