3 ms·

I don't understand your comment. Take a simple definition of the factorial: http://codepad.org/GTBdCKin http://codepad.org/GTBdCKin The space usage for this fu

by ramchip 15y ago

I don't understand your comment. Take a simple definition of the factorial: http://codepad.org/GTBdCKin http://codepad.org/GTBdCKin The space usage for this function is obviously constant, and the number of multiplications will be linearly dependent on the number. If you mean to refer to the 'factorial function' as a mathematical object, and point out that bignum operations have different complexity... well that's true, but irrelevant to OP's post, and there are less snide ways of saying it.

deleted 15y ago
[deleted]
- cperciva 15y ago
  the # of bits required to represent the numeric argument That's usually what we mean, yes. When we talk about algorithms for computing factorials, exponentials, or other rapidly-growing functions, we change terminology. It's one of these "we all know what we mean so we don't need be clear about what we're saying" things. ;-)
cperciva 15y ago
Yes, when I say "factorial function" I mean the factorial function, taking an integer input n and returning the integer output n!. If cletus meant "factorial as long as the result is a 32-bit integer", I don't know why he would accept an O(n) solution to that: I wouldn't hire anyone who didn't immediately produce the obvious O(1) algorithm using a 13-element lookup table. (If he meant "factorial modulo 2^32", a 34-element lookup table suffices.) As for being snide... yes, but I'm tired of the myth that Google is full of (and only hires) algorithms gurus. I have yet to see any indication that Google requires any more than a minimal undergraduate level of algorithmic competency.
- ramchip 15y ago
  > I don't know why he would accept an O(n) solution to that Because it's a question used to weed out early stage candidates. It's a fizzbuzz test. The point is not to see if the candidate knows the algorithmic complexity of arbitrary-sized integer operations, and neither is it to see if he knows whether the factorial function grows quickly enough to make a look-up table worthwhile. It's just to take a very simple function and get him to write some code in a text editor. Or at least, that's what I read from the OP's post. Perhaps he meant otherwise.
Mvandenbergh 15y ago
Yes, the number of multiplications will be linearly dependent on the number, unfortunately the computational complexity of integer multiplication is not itself O(1). It can seem like it is, because modern CPUs can perform integer multiplications up to a certain number of bits (I think it's usually 32 or 64 depending on processor, but don't quote me on this). These are O(1) operations because the CPU contains logic to carry out the entire multiplication. Unfortunately that only works for the first few multiplications and 21! > 2^64, after that you need to use a fast multiplication algorithm. For comparison the normal way that humans use to multiply numbers has complexity O(n^2), and a naive factorial algorithm based on that has complexity O(n^3).
- cperciva 15y ago
  Classical multiplication is O(nm), not O(n^2) -- big times small is faster than big times big. A naive factorial is O(n^2 (log n)^2).
  - Mvandenbergh 15y ago
    big times small is faster than big times big Right you are, my mistake.
tomjen3 15y ago
The space usage for this function is obviously constant and, yes, the number of multiplications is linearly dependent on the number. But it is not a factorial function. It happens to have the same result as the factorial function as long as the result is less than what can be stored in a fixnum int in C. But it is a very real possibility that that isn't enough. I always wanted to find out what the sum of the factorial of the first 100 numbers was but what you claim is a factorial function can't do that.

by ramchip 15y ago

deleted 15y ago

[deleted]

cperciva 15y ago
the # of bits required to represent the numeric argument That's usually what we mean, yes. When we talk about algorithms for computing factorials, exponentials, or other rapidly-growing functions, we change terminology. It's one of these "we all know what we mean so we don't need be clear about what we're saying" things. ;-)

cperciva 15y ago

Yes, when I say "factorial function" I mean the factorial function, taking an integer input n and returning the integer output n!. If cletus meant "factorial as long as the result is a 32-bit integer", I don't know why he would accept an O(n) solution to that: I wouldn't hire anyone who didn't immediately produce the obvious O(1) algorithm using a 13-element lookup table. (If he meant "factorial modulo 2^32", a 34-element lookup table suffices.) As for being snide... yes, but I'm tired of the myth that Google is full of (and only hires) algorithms gurus. I have yet to see any indication that Google requires any more than a minimal undergraduate level of algorithmic competency.

ramchip 15y ago
> I don't know why he would accept an O(n) solution to that Because it's a question used to weed out early stage candidates. It's a fizzbuzz test. The point is not to see if the candidate knows the algorithmic complexity of arbitrary-sized integer operations, and neither is it to see if he knows whether the factorial function grows quickly enough to make a look-up table worthwhile. It's just to take a very simple function and get him to write some code in a text editor. Or at least, that's what I read from the OP's post. Perhaps he meant otherwise.

Mvandenbergh 15y ago

Yes, the number of multiplications will be linearly dependent on the number, unfortunately the computational complexity of integer multiplication is not itself O(1). It can seem like it is, because modern CPUs can perform integer multiplications up to a certain number of bits (I think it's usually 32 or 64 depending on processor, but don't quote me on this). These are O(1) operations because the CPU contains logic to carry out the entire multiplication. Unfortunately that only works for the first few multiplications and 21! > 2^64, after that you need to use a fast multiplication algorithm. For comparison the normal way that humans use to multiply numbers has complexity O(n^2), and a naive factorial algorithm based on that has complexity O(n^3).

cperciva 15y ago
Classical multiplication is O(nm), not O(n^2) -- big times small is faster than big times big. A naive factorial is O(n^2 (log n)^2).
- Mvandenbergh 15y ago
  big times small is faster than big times big Right you are, my mistake.

tomjen3 15y ago

The space usage for this function is obviously constant and, yes, the number of multiplications is linearly dependent on the number. But it is not a factorial function. It happens to have the same result as the factorial function as long as the result is less than what can be stored in a fixnum int in C. But it is a very real possibility that that isn't enough. I always wanted to find out what the sum of the factorial of the first 100 numbers was but what you claim is a factorial function can't do that.