The fastest way to add numbers in numbers

Question

Given a large number, for example. 9223372036854775807 ( Int64.MaxValue ), what is the fastest way to add numbers?

I am currently ToStringing and reparsing each char in int :

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

This is certainly terribly inefficient. Any suggestions?

And finally, how would you do this work with BigInteger ?

thanks

Answer 1

Well, another option:

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

BigInteger also has a DivRem method, so you can use the same approach.

Notice that I saw DivRem not as fast as doing the same arithmetic “manually”, so if you are really interested in speed, you can think about it.

Also consider a lookup table with (say) 1000 elements pre-computed by sums:

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

This would mean fewer iterations, but each iteration has additional access to the array ...

Answer 2

No one has discussed the version of BigInteger. To do this, I would look at 10 ¹ 10 ² 10 ⁴ 10 ⁸ and so on until you find the last 10 ^{2 n} which is less than your value. Take the number div and mod 10 ^{2 n} to get 2 smaller values. Rinse, rinse and repeat recursively. (You must save your iterated squares of 10 in an array, and in the recursive part pass information about the next power for use.)

With BigInteger with numbers k, dividing by 10 is O (k). Therefore, to find the sum of the digits with a naive algorithm is O (k ² ).

I don’t know what C # uses internally, but non-naive algorithms there for multiplying or dividing k-bits by a k-bit integer all work in O (k ^1.6 ) time or better (most of them are much better, but have overhead, which makes them worse for "small large integers"). In this case, preparing the initial list of degrees and splitting times takes O (k ^1.6 ) time. This gives you 2 problems of size O ((k / 2) ^1.6 ) = 2 ^-0.6 O (k ^1.6 ). At the next level, you have 4 problems of size O ((k / 4) ^1.6 ) for another 2 ^-1.2 O (k ^1.6 ) Work. Add all terms and powers of 2 to a geometric series converging to a constant, so the total work is O (k ^1.6 ).

This is a definite victory, and the victory will be very, very obvious if you work with numbers on thousands of numbers.

Answer 3

Yes, this is probably somewhat inefficient. I would probably just divide by 10, adding balances each time.

Answer 4

The first rule of performance optimization: do not divide when you can breed. The next function will take four-digit numbers 0-9999 and do what you ask. Intermediate calculations are more than 16 bits. We multiply the number by 1/10000 and accept the result as a fixed-point number Q16. Then the numbers are extracted by multiplying by 10 and take the integer part.

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

It can be expanded to large sizes, but it is difficult. You must make sure that rounding in a fixed-point calculation always works correctly. I also made 4-digit numbers, so the intermediate result of multiplying a fixed point will not overflow.

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; 

Answer 6

Instead of int.parse, why not subtract “0” from each digit to get the actual value.

Remember that "9" - "0" = 9, so you must do this in order k (number length). Subtraction is just one operation, so this should not slow down the work.