How long it would take you to make a working code to print out factorial of very very large numbers

Question

I was given this coding question in interview:

given a very very large number (say more than long or any in-built types) print out its factorial. you can not assume a max limit anywhere in the program.I had to make a working code on computer and during interview.

I am really curious, how long on average would it take for others?

this is subjective question but an average will set some ballpark figures and a benchmarks for such a coding question.

What I did?

I chose C and represented number by a linked list of characters (containing a single digit). though perhaps it can be made more efficient to store chunks in int/long and do int arithmetic than store it in chunk of characters. I took 2 hours and spat out a code with things in place, major fns coded, but then interviewer said she wanted a completely working one and asked me to do it offline and mail it to her.

Don't go for the linked list! Instead, you could use [GMP](http://gmplib.org), hope that they did it the best way possible, and measure. I can do 100000! in under second, but 1000000! is already a bit much (few seconds). For the asymptotics, [Stirling's formula](http://en.wikipedia.org/wiki/Stirling's_approximation) is indispensable. — Kerrek SB, Jul 06 '11 at 14:06
It's the [GNU Multiple Precision Library](http://gmplib.org/). Also, for this particular problem, you can save space by compressing the trailing zeroes. — R. Martinho Fernandes, Jul 06 '11 at 14:08
Forever, because you can't make that program because that number will not fit in the memory of any computer in existence. — Benjamin Lindley, Jul 06 '11 at 14:09
ok, I wasn't aware of The GNU Multiple Precision Arithmetic Library. so what all options excluding this? — xyz, Jul 06 '11 at 14:09
@Benjamin: what number? You can most definitely write a program without any assumption of limits. Lots of people do that, usually in the form of bugs like memory leaks and overflows. — R. Martinho Fernandes, Jul 06 '11 at 14:10
If you only need to know the **last** couple of digits of the result, I can give you a quick algorithm ;-) — Kerrek SB, Jul 06 '11 at 14:11
[Fast Factorial Functions]([http://www.luschny.de/math/factorial/FastFactorialFunctions.htm) — Zhen, Jul 06 '11 at 14:12
If you got this question on an interview, I'd question the quality of the employer. The problem is irrelevant to most everyday situations and a bit too complex for an interview. If they want to see how you stress-code together something in a few hours, that says something very bad about the company. Companies typically motivate these kind of odd questions by saying that they want to test problem-solving skill. But this isn't an everyday problem. More relevant questions would be more like: "write an ADT doing task x", "write a class doing task x", "find and fix the bug in this code" etc. — Lundin, Jul 06 '11 at 14:29
@Martinho: If part of the program spec is to display the number, and displaying the number is physically impossible, then writing the program is physically impossible. If there is to be no assumption of limits, then all these suggestions to use arbitrary precision or big int libraries are pointless, because a simple `uint factorial(uint n) { if(n < 2) return 1; return n * factorial(n-1); }` will be just as effective. — Benjamin Lindley, Jul 06 '11 at 14:34
@Lundin : I agree with you. I did feel strange in having to give them a working code for this and when interviewer looked a bit unhappy when I said I hadn't written the minor function to display the list -- just the protoype and she wanted a totally working code. but this got me curious on how much time on avg other pple would take. My code was still not in working condition after 2 hours though pretty much all pieces were done and major fns were coded — xyz, Jul 06 '11 at 14:45
I think this is a very good question, although not for a normal interview... I could imagine it at a company like google. if you start to blindly implement it, you have no chance to get hired. — Karoly Horvath, Jul 06 '11 at 22:16

score 2 · Accepted Answer · answered Jul 06 '11 at 14:09

2

The good solution is to write a BigInt class that supports addition and mutilplication only. The number shouldn't be kept in base 10, rather in base 10000, i.e. each digit is a number 0-9999. Writing this is about 50-60 lines of code which should be relatively quick. I would also go with vector rather than list

Of course if you're not allowed to use an existing big int class.

answered Jul 06 '11 at 14:09

Armen Tsirunyan

130,161
59
324
434

Why not base-256, so you can use one byte for each digit? ;-) – Kerrek SB Jul 06 '11 at 14:10
@Kerrek: Do you imagine how painful it is to convert a base 10 long number to a base 256 number and vice versa? I mean, the unput is going to be a string representation (base 10) of a number, isn't it? – Armen Tsirunyan Jul 06 '11 at 14:11
is it really 5-60 lines? including taking input of arbit length, representing it in your DS, printing out output, and actual calculation. – xyz Jul 06 '11 at 14:13
@p2pnode: Yes, it is, no more than 100 is a very reliable estimate – Armen Tsirunyan Jul 06 '11 at 14:13
@p2pnode: I am saying this because I have written it many times during different ACM contests – Armen Tsirunyan Jul 06 '11 at 14:14
@Armen: any reason to pick base 10000 over base 1000000000 (which is the largest power of 10 that fits a 32-bit integer)? – R. Martinho Fernandes Jul 06 '11 at 14:21
1

@Martinho: Yes, of course there is. The point is that the square of the base bust be representible in 32-bit (or whatever) so that multiplication code can be done easily – Armen Tsirunyan Jul 06 '11 at 14:23
Ah! That makes a lot of sense :) – R. Martinho Fernandes Jul 06 '11 at 14:25
@Martinho: Is that sarcasm or you're actually agreeing? :) – Armen Tsirunyan Jul 06 '11 at 14:34
2

I'm agreeing. I use ;) for sarcasm. – R. Martinho Fernandes Jul 06 '11 at 14:36
+1 for addressing the question? :-) giving your code size estimate .. and time estimate? yours looks 1 hour, given your acm background.. – xyz Jul 06 '11 at 15:12
@p2pnode: Actually, I can bet I can write this in 20 minutes if nice code isn't a concern. But it's because I have done it very many times in time pressure – Armen Tsirunyan Jul 06 '11 at 15:13
20 minutes coding and then an eternity waiting for the results – Karoly Horvath Jul 06 '11 at 23:42
@Armen : I find it very hard to believe that one can code it in 20 minutes. Sure, I am a bad and slow coder, but 20 minutes still looks totally undoable. But you know yourself best. – xyz Jul 07 '11 at 07:53
@p2pnode: If we agree that it's 100 lines, and If I have the algorithm thought through and I have coded it many times before, then 5 lines per minute is a reasonable estimate, isn't it? – Armen Tsirunyan Jul 07 '11 at 08:50

score 2 · Answer 2 · edited May 23 '17 at 12:13

2

Check the following links

edited May 23 '17 at 12:13

Community

1
1

answered Jul 06 '11 at 14:15

Balanivash

6,709
9
32
48

score 0 · Answer 3 · answered Jul 06 '11 at 14:11

0

I'd start by suggesting a straight factorial in Common Lisp as Lisp already supports arbitrary precision arithmetic.

Assuming "no max limits anywhere" is a bit disingenuous since the computer has limited memory / disk space in any case but I understand the general gist.

Barring those two points of argument, you need to implement some sort of ADT for an arbitrary-sized number like Armen suggests.

answered Jul 06 '11 at 14:11

Joris Timmermans

10,814
2
49
75

2

You can most certainly write programs assuming *no limits anywhere*. It doesn't mean they aren't there, just that you didn't consider them. – R. Martinho Fernandes Jul 06 '11 at 14:14
@MadKeithV: the same about Erlang which has builtin big number support – Andriy Tylychko Jul 06 '11 at 14:41

score 0 · Answer 4 · answered Jul 06 '11 at 21:29

0

To what accuracy? My first impulse would be to simply use Stirling's approximation.

answered Jul 06 '11 at 21:29

nibot

14,428
8
54
58

score 0 · Answer 5 · answered Jul 06 '11 at 22:09

0

There's no way I'm going to implement factorial for longs (bigger than ints) not to say above that.. It's totally pointless. No matter how fast my biginter library is.

32bit -> 4G, product of the numbers just from 1G till 4G.. well, lets just get a quick (under)estimation for the number of digits: 3G * 9 = 27G. rough estimation for the storage for that: 2^10=1024, so for 3 digits you need 1.25 bytes.. that's 11.25G. remember, this was a serious underestimation...

answered Jul 06 '11 at 22:09

Karoly Horvath

94,607
11
117
176

this was for a startup doing normal things, nothing out of the box or hyper scalable or anything. I could see that the question in unrealiastic, I assumed that they just wanted to check my coding skills of dealing with linked lists, error checking, being able to write a correct code etc. But now in retrospect, I think I should have asked them directly what do they want to test by such question or saying that some approximation would be more realistic etc etc. I just jumped on to a machine. My mistake. I didnt ask them for any practical applications of such a question etc. Now I feel stupid. – xyz Jul 07 '11 at 06:11
I think a good interview should make you feel kinda stupid. The only way you can test someone's real skills is to go beyond what he can perform. Otherwise how would you know his/her limits? – Karoly Horvath Jul 07 '11 at 08:48

How long it would take you to make a working code to print out factorial of very very large numbers

5 Answers5