Le moyen le plus rapide d'additionner les chiffres d'un nombre

Question

Étant donné un grand nombre, par exemple 9223372036854775807 ( Int64.MaxValue ), quel est le moyen le plus rapide d'additionner les chiffres ?

Actuellement, je suis en train de ToString et de reparsing chaque char dans une int :

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

Ce qui est sûrement horriblement inefficace. Des suggestions ?

Et enfin, comment faire pour que cela fonctionne avec BigInteger ?

Gracias

Answer 1

Eh bien, une autre option est :

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

BigInteger a un DivRem Vous pouvez donc utiliser la même approche.

Notez que j'ai vu DivRem ne sera pas aussi rapide que de faire la même arithmétique "manuellement", donc si vous êtes vraiment intéressés par la vitesse, vous devriez y réfléchir.

Considérez également une table de consultation avec (disons) 1000 éléments précalculés avec les sommes :

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

Cela signifierait moins d'itérations, mais chaque itération a un accès supplémentaire au tableau...

Answer 2

Personne n'a discuté de la version BigInteger. Pour cela, je regarderais 10 1 , 10 2 , 10 4 , 10 8 et ainsi de suite jusqu'à ce que vous trouviez les 10 derniers 2 n qui est inférieur à votre valeur. Prenez votre nombre div et modérez 10 2 n pour obtenir 2 valeurs plus petites. Laver, rincer et répéter récursivement. (Vous devriez conserver vos carrés itérés de 10 dans un tableau, et dans la partie récursive transmettre l'information sur la prochaine puissance à utiliser).

Avec un BigInteger à k chiffres, la division par 10 est O(k). Par conséquent, trouver la somme des chiffres avec l'algorithme naïf est O(k 2 ).

Je ne sais pas ce que C# utilise en interne, mais les algorithmes non naïfs qui existent pour multiplier ou diviser un entier de k bits par un entier de k bits fonctionnent tous en temps O(k 1.6 ) ou mieux (la plupart sont beaucoup, beaucoup mieux, mais ont une surcharge qui les rend pires pour les "petits grands entiers"). Dans ce cas, préparer votre liste initiale de puissances et la diviser une fois prend des temps O(k 1.6 ). Cela vous donne 2 problèmes de taille O((k/2) 1.6 ) = 2 -0.6 O(k 1.6 ). Au niveau suivant, vous avez 4 problèmes de taille O((k/4) 1.6 ) pour un autre 2 -1.2 O(k 1.6 ) travail. Additionnez tous les termes et les puissances de 2 se transforment en une série géométrique convergeant vers une constante, de sorte que le travail total est de O(k 1.6 ).

Il s'agit d'un avantage certain, et cet avantage sera très, très évident si vous travaillez avec des nombres à plusieurs milliers de chiffres.

Answer 3

Oui, c'est probablement un peu inefficace. Je diviserais probablement plusieurs fois par 10, en additionnant les restes à chaque fois.

Answer 4

La première règle de l'optimisation des performances : Ne divisez pas quand vous pouvez multiplier à la place. La fonction suivante prendra les nombres à quatre chiffres 0-9999 et fera ce que vous demandez. Les calculs intermédiaires sont supérieurs à 16 bits. Nous multiplions le nombre par 1/10000 et prenons le résultat comme un nombre à virgule fixe Q16. Les chiffres sont ensuite extraits en les multipliant par 10 et en prenant la partie entière.

#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;
}

Cela peut être étendu à des tailles plus grandes mais c'est délicat. Vous devez vous assurer que l'arrondi dans le calcul du point fixe fonctionne toujours correctement. J'ai également utilisé des nombres à 4 chiffres pour que le résultat intermédiaire de la multiplication à virgule fixe ne déborde pas.

Answer 5

    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;