Adding all the digits in a large number gives me an incorrect result

So I am trying to add all the individual in 100! but the output is 683. Weirdly, this works with smaller numbers.

factnum = sprintf("%.f",factorial(5));

charfact = convertStringsToChars(factnum);

i = 1;

for i = 1:length(charfact)

x(i) = str2num(charfact(i));

end

disp(sum(x));

Answer 1

[John D'Errico]

How large is 100! ?

factorial(100)
ans =
     9.33262154439441e+157

So a number with what, 158 digits? How many digits does a double precision number have in MATLAB? (Roughly 16.)

So you are only 142 digits short. Of course it works for factorial(5), which is what, 120? A 3 digit number? No problem.

This is clearly homework, so you are going to need to think of something more creative, since I won't do your homework for you. You might expand those multiplications essentially long hand. Or you might use syms. Hey, at least you won't have to add up those 24 trailing zeros. In case you are wondering, either of the approaches I mentioned are quite easy to implement. Or, I suppose you could be really lazy and use my VPI toolbox. This should work:

sum(digits(factorial(vpi(100))))

Or, you could spend some time and learn to use the java.math.BigInteger tools.

(Actually, 683 is not that terribly far off. Lets see, 158 digits. Assume a uniform distribution, so each digit contributes 4.5 to the average. 158*4.5=711. But there are 24 known trailing zeros, which are not contributing to that average. So 600-700 should be in the right ballpark for the sum.)

[Eqan Ahmad]

Hi John I am solving these questions just for practice. Thank you for taking the time to reply. My question is as to why smaller digits work, and large digits like 158 digits do not. The code is supposed to take every single character in the string array, convert it to an integer array, and finally compute its sum.

I am not sure what other methods are available for solving this problem. If you could point me in the right direction that would be fantastic.

I have tried the VPI toolbox before, but it was a bit challenging to setup.

[Eqan Ahmad]

yep.. the vpi function worked perfectly. Thank you immensly, I just hoped I could have solved it my way.

[John D'Errico]

What you don't realize is MATLAB stores numbers in double precision. Not all of the digits in factorial(100) are available. A double can represent any integer not exceeding 2^53--1. But factorials are seriously BIG numbers.

format short g
log2(factorial(1:20))
ans =
  Columns 1 through 11
            0            1        2.585        4.585       6.9069       9.4919       12.299       15.299       18.469       21.791        25.25
  Columns 12 through 20
       28.835       32.536       36.343        40.25        44.25       48.338       52.508       56.755       61.077

So a double gives up around factorial(17). Go past that, and a double starts to lose some digits. Yes, you could use uint64, but that will get you only to factorial(19) before it gives up.

If you want really large factorials, then as I said, you need to use tools that are designed to retain ALL of those digits.

That means either syms or vpi would be the obvious choices. Or you can store each digit separately as a vector. Now do all of the multiplies. That means after you multiply by a number, you will need to do carries. And factorial(100) = 1*2*3*4*...*99*100. So you would need to do 100 multiplies.

The easy solution really is to use either vpi or syms. I already gave you the one line of code that will do it with vpi. (It should not be difficult to set up vpi. Not sure what you found to be a problem. Just download, unzip, add the top directory to your search path.)

Using syms is not much harder. You would start with factorial(sym(100)). Then you need to figure out how to extract the digits. If you don't know, then try this:

syms x
methods(x)

Is there a method in there that might prove useful? I predict there is. A person of good character could find it. (Yes, that was a Hint.) You might want to subtract '0' though. (That was another hint.)

[Eqan Ahmad]

I am trying hard to implement it! Just need some time to understand methods().

EDIT:

I GOT IT

sum(char(factorial(sym(100)))-'0')

I was so confused with method(), thank you so much John. I will be using this a lot from now on. Much more efficient than what I started off with.

[John D'Errico]

Well done. I was hoping you would get it yourself. The trick here was to recognize that once you have the symbolic form, you can convert it to a string of characters. Once you have that, subtracting '0' is the simple way in MATLAB to convert achar string to a vector of numbers. And then just sum. So a few tricks you wanted to learn. But having done so, you know them, and now they are yours for the next problem to be solved.