9

I know there is a way of finding the sum of digits of 100!(or any other big number's factorial) using Python. But I find it really tough when it comes to C++ as the the size of even LONG LONG is not enough.

I just want to know if there is some other way.

I get it that it is not possible as our processor is generally 32 bits. What I am referring is some other kind of tricky technique or algorithm which can accomplish the same using the same resources.

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
Ashish Yadav
  • 1,667
  • 6
  • 20
  • 26

8 Answers8

16

Use a digit array with the standard, on-paper method of multiplication. For example, in C :

#include <stdio.h>

#define DIGIT_COUNT 256

void multiply(int* digits, int factor) {
  int carry = 0;
  for (int i = 0; i < DIGIT_COUNT; i++) {
    int digit = digits[i];
    digit *= factor;
    digit += carry;
    digits[i] = digit % 10;
    carry = digit / 10;
  }
}

int main(int argc, char** argv) {
  int n = 100;

  int digits[DIGIT_COUNT];
  digits[0] = 1;
  for (int i = 1; i < DIGIT_COUNT; i++) { digits[i] = 0; }

  for (int i = 2; i < n; i++) { multiply(digits, i); }

  int digitSum = 0;
  for (int i = 0; i < DIGIT_COUNT; i++) { digitSum += digits[i]; }
  printf("Sum of digits in %d! is %d.\n", n, digitSum);

  return 0;
}
Dinah
  • 52,922
  • 30
  • 133
  • 149
Olathe
  • 1,885
  • 1
  • 15
  • 23
  • 5
    I might be late in commenting, but still I don't know why the OP did not accept this as a solution. This is simple, clean, ingenuity is at best(basically doing paper multiplication with each digit as a array element to take care of bignum problems. When others are harping on using bignum and arbitrary precision libraries, this solution stands apart for its simplicity yet amazing effectiveness(Isee this would be O(N) solution). why is this gone so quietly unnoticed, uncommented when people comment on many trivial 'just for the sake of it' answers in general on SO. Sad. – goldenmean Jan 31 '12 at 17:47
  • very impressive solution. Thanks :) – Kaidul Mar 04 '14 at 13:28
14

How are you going to find the sum of digits of 100!. If you calculate 100! first, and then find the sum, then what is the point. You will have to use some intelligent logic to find it without actually calculating 100!. Remove all the factors of five because they are only going to add zeros. Think in this direction rather than thinking about the big number. Also I am sure the final answer i.e. the sum of the digits will be within LONG LONG.

There are C++ big int libraries, but I think the emphasis here is on algorithm rather than library.

Manoj R
  • 3,197
  • 1
  • 21
  • 36
  • The final answer of what will fit in `long long`? You can easily see the upper bound on the sum of digits is well under 100 * 2 * 10 = 2000, which easily fits in a `short`. Meanwhile, `100!` is 158 digits (525 bits), or 134 digits (445 bits) without the trailing zeroes, so those won't fit in a `long long`! – Gabe Oct 02 '10 at 00:47
  • Even after removing factors of 10, the result still won't fit in a `long long`, by a huge amount - see hobbe's comment in one of the other answers. There's a forum for people who have solved this problem and want to post their solution, and virtually every answer on that forum either uses a BigNum library/language feature, or creates a good-enough equivalent themselves. – Doug Oct 02 '10 at 05:07
  • 1
    Why does this have so many upvotes? This is only wishful thinking, I don't think there is an actual solution along the lines of this post. –  Dec 24 '15 at 16:23
6

If you're referring to the Project Euler problem, my reading of that is that it wants you to write your own arbitrary-precision integer library or class that can multiply numbers.

My suggestion is to store the base-10 digits of a number, in reverse order to the way you'd normally write them, because you'll need to convert the number to base 10 in the end, anyway. Storing the digits in reverse order makes writing the addition and multiplication routines slightly easier, in my opinion. Then write addition and multiplication routines that emulate how you would add or multiply numbers manually.

Doug
  • 8,780
  • 2
  • 27
  • 37
  • 2
    I find it simpler to use a vector of integers, each one of which uses only half of its bits (if you use a 64 bit integer, store in each element only 32 bits), that way you guarantee that there will be no overflow in any of the operations. Then each operation can be performed at each subelement first, and then the object can be normalized in a sequential way. – David Rodríguez - dribeas Oct 01 '10 at 08:29
  • 2
    @David Rodríguez - dribeas - I agree, that way is better in general, especially if memory usage or computation speed is important. But in this specific case, if all you want is the sum of the digits in base 10, but you effectively store them in some other base, then you've got to write a division or base-conversion function as well. – Doug Oct 01 '10 at 08:33
  • 3
    I don't know what Project Euler is, so if you're right then you may have more insight into the performance requirements, but IMO if he's just learning C++ from Python, and using this as an exercise, he could do worse than put ASCII-encoded digits into a std::string. Getting a multiplication algorithm that works is more important than efficient data representation, and a familiar type that grows and can be trivially displayed has some benefits. Doing it a digit at a time it's as easy to handle a carry in the algorithm - no need to reserve space in the data structure. – Tony Delroy Oct 01 '10 at 08:51
  • http://projecteuler.net/index.php?section=problems&id=20. I believe I solved it more or less the way Doug describes. – Fred Foo Oct 01 '10 at 09:02
  • @Steve: ...and I just used Python. I think this is just a warm-up question and writing a big-num library for this could be a serious overkill. The problems will get much tougher. – UncleBens Oct 01 '10 at 15:26
  • Or maybe I used Python. I did do one of the exercises by operating on decimal digits directly. It was a nice exercise. – Fred Foo Oct 01 '10 at 15:26
  • @UncleBens: heh, fair enough. I've only ever done Euler problems in C++, because I was doing them while I was learning C++ "properly". It was harder than I first thought to write template functions that work with `int` or `mpz_class` interchangeably, and that was exercise enough for me at the time... – Steve Jessop Oct 01 '10 at 15:42
6

long long is not a part of C++. g++ provides it as an extension.

Arbitrary Precision Arithmetic is something that you are looking for. Check out the pseudocode given in the wiki page.

Furthermore long long cannot store such large values. So you can either create your BigInteger Class or you can use some 3rd party libraries like GMP or C++ BigInteger.

Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
  • 2
    C++0x has `long `long`, borrowed from C which incorporated it into the standard over a decade ago. – hobbs Oct 01 '10 at 23:00
5

Observe that multiplying any number by 10 or 100 does not change the sum of the digits.

Once you recognize that, see that multiplying by 2 and 5, or by 20 and 50, also does not change the sum, since 2x5 = 10 and 20x50 = 1000.

Then notice that anytime your current computation ends in a 0, you can simply divide by 10, and keep calculating your factorial.

Make a few more observations about shortcuts to eliminate numbers from 1 to 100, and I think you might be able to fit the answer into standard ints.

abelenky
  • 63,815
  • 23
  • 109
  • 159
  • 2
    I should retract this answer. After working with several "shortcuts" today, I haven't found a workable solution. I reviewed the posted solutions to Euler#20, and everyone seemed to do it with a BigNum library of one variety or another. I am no longer convinced this problem can be solved within a UInt64. Can someone tell me that it can be? – abelenky Oct 04 '10 at 04:50
  • 100 factorial is 158 digits long, with only 24 trailing zeroes (source [WolframAlpha](http://www.wolframalpha.com/input/?i=100%21)). Removing the zeroes won't help enough, since, [even with the zeroes removed, it requires 446 bits](http://www.wolframalpha.com/input/?i=Ceil%5BLog%5B2%2C+100%21%2F10%5E24%5D%5D). – Olathe Jul 14 '13 at 15:16
3

There are a number of BigInteger libraries available in C++. Just Google "C++ BigInteger". But if this is a programming contest problem then you should better try to implement your own BigInteger library.

taskinoor
  • 45,586
  • 12
  • 116
  • 142
1

Nothing in project Euler requires more than __int64.

I would suggest trying to do it using base 10000.

Peter
  • 11
  • 2
  • 2
    Python is being very, very clever to be able to do that. Stunning that my 3-year-old laptop returns `print sum( map(int, str(math.factorial(30000))) )` as `511470` in just a few seconds. – Potatoswatter Oct 03 '10 at 19:18
0

You could take the easy road and use perl/python/lisp/scheme/erlang/etc to calculate 100! using one of their built-in bignum libraries or the fact some languages use exact integer arithmetic. Then take that number, store it into a string, and find the sum of the characters (accounting for '0' = 48 etc).

Or, you could consider that in 100!, you will get a really large number with many many zeros. If you calculate 100! iteratively, consider dividing by 10 every time the current factorial is divisible by 10. I believe this will yield a result within the range of long long or something.

Or, probably a better exercise is to write your own big int library. You will need it for some later problems if you do not determine the clever tricks.

Kizaru
  • 2,443
  • 3
  • 24
  • 39
  • Re: second paragraph: your guess is off. Factorial grows way too quickly. Ordinarily, a 64-bit int overflows between 20! and 21!. Removing tens as often as possible only gets you up to 23!. There are only four zeroes to remove (10,000), and 22 * 23 * 24 is 12,144 -- already more than 10,000. – hobbs Oct 01 '10 at 23:24
  • Err yes. I just looked at my source code for problem 20 of project euler (this problem), and I essentially did this combined with abelenky's idea while using a bit vector to keep track of the usable numbers. – Kizaru Oct 01 '10 at 23:35
  • If you have a bignum library, you can generally use `div` and `mod`, which will almost always be quicker than converting to a string and using those digits. For example: `digitSum = 0; while (n != 0) { digitSum += n.mod(10); n = n.div(10); }` – Olathe Oct 03 '10 at 15:43
  • I was talking about using a string for just languages that have exact integer arithmetic. It's much slower for a CPU to perform division or multiplication than addition or subtraction. Having a library which handles that will be even slower (has to perform more arithmetic for each digit). Converting the number to a string and then doing one pass on the array will be much, much faster than chopping off every digit and comparing. – Kizaru Oct 03 '10 at 18:58
  • Unless you were talking about converting the number to a string, which could be slower if you did it manually (because you would be repeating the digit sum process you described). But languages like Perl provide some nice abilities to do this efficiently. – Kizaru Oct 03 '10 at 19:06