4 ms·
Yes, the number of multiplications will be linearly dependent on the number, unfortunately the computational complexity of integer multiplication is not itself
by 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 agoClassical 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 agobig times small is faster than big times big Right you are, my mistake.