11 ms·

Calculating integer factorials in constant time, taking advantage of overflow

64 points by DmitryNovikov 11y ago

hellofunk 11y ago
I found this rather strange. Use of the word "calculate" is a bit of a stretch with dealing with a lookup table to get results. Worth reading, however.
- bemmu 11y ago
  Well in the first example it's calculated, just at compile time.
- dietrichepp 11y ago
  I don't think it's really a stretch. It's the classic tradeoff: space versus time. The results are the same.
- mzl 11y ago
  The point is that the lookup table contains results for _all_ inputs to the function that have a defined result (that is, functions that do not trigger overflow and thus undefined behaviour). In that sense, it has the same semantics as the original function although most people would not suspect that.
- liquidise 11y ago
  Watch it. i've "calculated" more than a few project euler solutions this way.
deleted 11y ago
[deleted]
tantalor 11y ago
If you enforce n<=12 (to prevent undefined behavior) in the original "naive" algorithm, then it too is constant time, i.e., O(12).
- iconjack 11y ago
  That's right, if there's a limit on n, then your algorithm is O(n). I took some downvotes when I made this point on StackOverflow: http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list/1587119#1587119 http://stackoverflow.com/questions/1586858/find-the-smallest...
  - Dylan16807 11y ago
    That's because 2^64 is naturally represented as 2^n, while you're representing it as n. You can technically define n as whatever you want, but if you don't follow certain conventions you will face opposition. n as 12 makes a lot of sense. n as a number too large to count doesn't make sense in the context of real programs.
    - evanpw 11y ago
      > You can technically define n as whatever you want The formal definition of time complexity measures relative to the size of the input, which in this case would be proportional to the number of elements in the list. > n as a number too large to count doesn't make sense in the context of real programs The definition of big-O notation involves taking the limit as n goes to infinity. It doesn't really even make sense if you only have a finite (even if huge) number of problem instances, since then everything is bounded by a constant.
      - Dylan16807 11y ago
        When people want to use big-O notation, they use limits that dominate both for astronomical values of n, and for realistic values of n. Making those diverge is intentional obfuscation. More importantly, you ignore the nature of the problem when you treat 2^64 as a constant, but the number of values in the list as n. I'm comfortable betting that if you take this problem, and push n to 2^100, you'll find that your integer size has been changed to 2^128. In other words, iconjack's algorithm is actually O(n) space or worse.
WhitneyLand 11y ago
I wonder if old school developers are more likely to think of these types of solutions. When I wrote games for older hardware every frickin' thing possible used look up tables to maximize speed. Coincidentally I received this type of problem later when interviewing at MS, but it wasn't Raymond Chen's group.
- noobermin 11y ago
  What do you mean? They asked you to compute something but expected you to use a lookup table instead?
  - WhitneyLand 11y ago
    Yes, it was the only way to speed up an algorithm's implementation and they wanted to see if you could realize that.
- jmount 11y ago
  Table lookup tended to be fast in the old days before the CPU and memory timings got so far out of whack. Now you need to double check that the calculation isn't in fact faster for the range you are interested in.
dvh 11y ago
... or get real: https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation
- uxcn 11y ago
  I was expecting to see a variant of this.
kleiba 11y ago
Interestingly, I was just doing some calculations over the weekend involving large factorials. Naturally, I used a "big integer" library to overcome the limitations of the hardware architecture. That anyone outside a class-room would be willing to restrict themselves to 32 or 64 bit for the largest integers thus seems contrived: of course, dealing with factorials will quickly get you past your system's word size, but that's what arbitrary-length integer libs are for.
- a1k0n 11y ago
  Depends what you need them for... In statistics, factorials appear in normalizing constants for various distributions (e.g., Poisson) and often you're working with floating point log-probabilities, in which case you can use the log-gamma function (built into most math libraries) to replace the log factorial. And that's a 64-bit float, no bignums needed.
  - jeffwass 11y ago
    But in what situation would you actually need an arbitrary precision library for general statistics? Ie, in what situations would any reasonable approximations not suffice for reasonable real-world precision? Eg, Stirlings approximation for ln(n!) should serve fairly well for moderate and above values of n. And knowing your statistical distribution at large n you can likely find a decent distribution from a discrete case requiring n! into a continuous one, eg Gaussian.
    - a1k0n 11y ago
      You wouldn't, for statistics. That's my point. Only in number theory problems do you actually need bignums for factorials, and those are usually toy problems or modulo some big prime. I don't know of any actual applications where you need to compute the bignum factorial. I'm curious what the GP needed it for.
      - kleiba 11y ago
        I needed them for a toy problem as well. Tried to experimentally verify the equality of two formulas involving large factorials. It was a counting problem.
yangshun 11y ago
Clickbait much.
scott_s 11y ago
I've used a similar technique for base-2 logarithms, when I knew the context in which it was used would only require handling powers-of-2 up to 16384: https://github.com/scotts/streamflow/blob/master/streamflow.c#L269 https://github.com/scotts/streamflow/blob/master/streamflow....
- drfuchs 11y ago
  Dude, your case statement will compile into a bunch of test and branch instructions, implementing a binary search if you're lucky, and a linear search if you're not. Better to use __builtin_clz() or similar, so your function will just take a few cycles with no (expensive) branching. Extra bonus: with care, it can work for all inputs, giving a truncated or rounded result.
  - scott_s 11y ago
    Dude, this outperformed log2 by a large margin, which is what I cared about. Cycles mattered in this code, but after this optimization, that's not where most cycles were being spent. edit: Investigating further, this intrinsic was introduced into gcc around 2006, which means I'm not sure it would have been available to me at the time.
  - uxcn 11y ago
    On x86, it could also compile down to just a jmp. A bsr would still be faster, but it would probably be worth checking that __builtin_clz actually compiles down to bsr. For portability reasons, it might be better just using bit tricks and letting the compiler try to optimize it though. Clang and GCC do pretty well here.
arbre 11y ago
You can also compute the factorials at compile time with templates: template<int64_t n> int64_t fact() { return n * fact<n-1>(); } template<> int64_t fact<0>() { return 1; } The book "Modern C++ design" from Alexandrescu extensively covers that kind of stuff. There might even be a way to use a loop and constexprs.
- wyager 11y ago
  Won't most modern compiled languages statically evaluate constant numerical expressions?
ape4 11y ago
I like the idea of hybrid. Since the value of a factorial depends on the factorial of the previous 2 numbers. Cache fact(n) and fact(n-1) for a selection of n's. eg n = 10, 100, 1000, 10000, ...
NelsonMinar 11y ago
There's a similar algorithm for O(1) primality checking. It does require access to Google though.
- mikeash 11y ago
  This also works well for reversing many cryptographic hashes.
banku_brougham 11y ago
I like this. It clearly shows that for all the computing power available, some algebra or calculus can be better for discovering the general form of a solution.
tromp 11y ago
Meanwhile, here's an artistic rendering of the factorial function: ┬──────────────── ┼─────────────┬── │ ──┬──────── ┼ ┬ │ ┬─┼─┬────── │ │ │ │ │ ┼─┬─┬── │ │ │ │ │ ┼─┼─┼─┬ │ │ │ │ │ └─┤ ├─┘ │ │ │ │ │ ├─┘ │ │ │ │ ├───┘ │ │ │ ├─┘ │ │ └─┤ │ │ └───────────┤ │ └─┘ (a diagram of factorial on Church numerals)

64 points by DmitryNovikov 11y ago

I found this rather strange. Use of the word "calculate" is a bit of a stretch with dealing with a lookup table to get results. Worth reading, however.

bemmu 11y ago
Well in the first example it's calculated, just at compile time.
dietrichepp 11y ago
I don't think it's really a stretch. It's the classic tradeoff: space versus time. The results are the same.
mzl 11y ago
The point is that the lookup table contains results for _all_ inputs to the function that have a defined result (that is, functions that do not trigger overflow and thus undefined behaviour). In that sense, it has the same semantics as the original function although most people would not suspect that.
liquidise 11y ago
Watch it. i've "calculated" more than a few project euler solutions this way.

deleted 11y ago

[deleted]

tantalor 11y ago

If you enforce n<=12 (to prevent undefined behavior) in the original "naive" algorithm, then it too is constant time, i.e., O(12).

iconjack 11y ago
That's right, if there's a limit on n, then your algorithm is O(n). I took some downvotes when I made this point on StackOverflow: http://stackoverflow.com/questions/1586858/find-the-smallest-integer-not-in-a-list/1587119#1587119 http://stackoverflow.com/questions/1586858/find-the-smallest...
- Dylan16807 11y ago
  That's because 2^64 is naturally represented as 2^n, while you're representing it as n. You can technically define n as whatever you want, but if you don't follow certain conventions you will face opposition. n as 12 makes a lot of sense. n as a number too large to count doesn't make sense in the context of real programs.
  - evanpw 11y ago
    > You can technically define n as whatever you want The formal definition of time complexity measures relative to the size of the input, which in this case would be proportional to the number of elements in the list. > n as a number too large to count doesn't make sense in the context of real programs The definition of big-O notation involves taking the limit as n goes to infinity. It doesn't really even make sense if you only have a finite (even if huge) number of problem instances, since then everything is bounded by a constant.
    - Dylan16807 11y ago
      When people want to use big-O notation, they use limits that dominate both for astronomical values of n, and for realistic values of n. Making those diverge is intentional obfuscation. More importantly, you ignore the nature of the problem when you treat 2^64 as a constant, but the number of values in the list as n. I'm comfortable betting that if you take this problem, and push n to 2^100, you'll find that your integer size has been changed to 2^128. In other words, iconjack's algorithm is actually O(n) space or worse.

WhitneyLand 11y ago

I wonder if old school developers are more likely to think of these types of solutions. When I wrote games for older hardware every frickin' thing possible used look up tables to maximize speed. Coincidentally I received this type of problem later when interviewing at MS, but it wasn't Raymond Chen's group.

noobermin 11y ago
What do you mean? They asked you to compute something but expected you to use a lookup table instead?
- WhitneyLand 11y ago
  Yes, it was the only way to speed up an algorithm's implementation and they wanted to see if you could realize that.
jmount 11y ago
Table lookup tended to be fast in the old days before the CPU and memory timings got so far out of whack. Now you need to double check that the calculation isn't in fact faster for the range you are interested in.

dvh 11y ago

... or get real: https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation

uxcn 11y ago
I was expecting to see a variant of this.

kleiba 11y ago

Interestingly, I was just doing some calculations over the weekend involving large factorials. Naturally, I used a "big integer" library to overcome the limitations of the hardware architecture. That anyone outside a class-room would be willing to restrict themselves to 32 or 64 bit for the largest integers thus seems contrived: of course, dealing with factorials will quickly get you past your system's word size, but that's what arbitrary-length integer libs are for.

a1k0n 11y ago
Depends what you need them for... In statistics, factorials appear in normalizing constants for various distributions (e.g., Poisson) and often you're working with floating point log-probabilities, in which case you can use the log-gamma function (built into most math libraries) to replace the log factorial. And that's a 64-bit float, no bignums needed.
- jeffwass 11y ago
  But in what situation would you actually need an arbitrary precision library for general statistics? Ie, in what situations would any reasonable approximations not suffice for reasonable real-world precision? Eg, Stirlings approximation for ln(n!) should serve fairly well for moderate and above values of n. And knowing your statistical distribution at large n you can likely find a decent distribution from a discrete case requiring n! into a continuous one, eg Gaussian.
  - a1k0n 11y ago
    You wouldn't, for statistics. That's my point. Only in number theory problems do you actually need bignums for factorials, and those are usually toy problems or modulo some big prime. I don't know of any actual applications where you need to compute the bignum factorial. I'm curious what the GP needed it for.
    - kleiba 11y ago
      I needed them for a toy problem as well. Tried to experimentally verify the equality of two formulas involving large factorials. It was a counting problem.

yangshun 11y ago

Clickbait much.

scott_s 11y ago

I've used a similar technique for base-2 logarithms, when I knew the context in which it was used would only require handling powers-of-2 up to 16384: https://github.com/scotts/streamflow/blob/master/streamflow.c#L269 https://github.com/scotts/streamflow/blob/master/streamflow....

drfuchs 11y ago
Dude, your case statement will compile into a bunch of test and branch instructions, implementing a binary search if you're lucky, and a linear search if you're not. Better to use __builtin_clz() or similar, so your function will just take a few cycles with no (expensive) branching. Extra bonus: with care, it can work for all inputs, giving a truncated or rounded result.
- scott_s 11y ago
  Dude, this outperformed log2 by a large margin, which is what I cared about. Cycles mattered in this code, but after this optimization, that's not where most cycles were being spent. edit: Investigating further, this intrinsic was introduced into gcc around 2006, which means I'm not sure it would have been available to me at the time.
- uxcn 11y ago
  On x86, it could also compile down to just a jmp. A bsr would still be faster, but it would probably be worth checking that __builtin_clz actually compiles down to bsr. For portability reasons, it might be better just using bit tricks and letting the compiler try to optimize it though. Clang and GCC do pretty well here.

arbre 11y ago

You can also compute the factorials at compile time with templates: template<int64_t n> int64_t fact() { return n * fact<n-1>(); } template<> int64_t fact<0>() { return 1; } The book "Modern C++ design" from Alexandrescu extensively covers that kind of stuff. There might even be a way to use a loop and constexprs.

wyager 11y ago
Won't most modern compiled languages statically evaluate constant numerical expressions?

ape4 11y ago

I like the idea of hybrid. Since the value of a factorial depends on the factorial of the previous 2 numbers. Cache fact(n) and fact(n-1) for a selection of n's. eg n = 10, 100, 1000, 10000, ...

NelsonMinar 11y ago

There's a similar algorithm for O(1) primality checking. It does require access to Google though.

mikeash 11y ago
This also works well for reversing many cryptographic hashes.

banku_brougham 11y ago

I like this. It clearly shows that for all the computing power available, some algebra or calculus can be better for discovering the general form of a solution.

tromp 11y ago

Meanwhile, here's an artistic rendering of the factorial function: ┬──────────────── ┼─────────────┬── │ ──┬──────── ┼ ┬ │ ┬─┼─┬────── │ │ │ │ │ ┼─┬─┬── │ │ │ │ │ ┼─┼─┼─┬ │ │ │ │ │ └─┤ ├─┘ │ │ │ │ │ ├─┘ │ │ │ │ ├───┘ │ │ │ ├─┘ │ │ └─┤ │ │ └───────────┤ │ └─┘ (a diagram of factorial on Church numerals)