News for hackers. Stuff that matters.
Re:Calculating integer factorials in constant time, taking a... by tantalor on Tuesday December 15, 2015 @09:26AM (#10737867)
If you enforce n<=12 (to prevent undefined behavior) in the original "naive" algorithm, then it too is constant time, i.e., O(12).
Re:Calculating integer factorials in constant time, taking a... by iconjack on Tuesday December 15, 2015 @01:49PM (#10739584)
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...
Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @02:04PM (#10739683)
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.

Re:Calculating integer factorials in constant time, taking a... by evanpw on Tuesday December 15, 2015 @04:39PM (#10740670)
> 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.

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @05:12PM (#10740861)
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.

Re:Calculating integer factorials in constant time, taking a... by evanpw on Tuesday December 15, 2015 @06:04PM (#10741130)
> Making those diverge is intentional obfuscation.

It's not obfuscation, it's literally the definition.

I'm not saying that the algorithm in question is practical, but asymptotic complexity has a precise mathematical definition, so it's totally possible for an algorithm with "good" time complexity to be so complicated or have such a huge constant that it's impossible to use (see [1] and [2] for some examples).

It's also totally legitimate to give a constraint on additional memory size, so that this algorithm is disallowed altogether (which is probably the right answer), or change the problem so that the word size varies with the list length, but it's not legitimate to just say that the algorithm isn't linear time because the constant is too big.

[1] http://cstheory.stackexchange.com/questions/4491/powerful-al...

[2] https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @06:22PM (#10741222)
The definition talks about what happens for extremely large numbers.

It does not talk about smaller numbers at all.

If you use an algorithm and complexity that are close for both moderately large numbers and extremely large numbers, you've done a good job.

If you introduce dumb things like constants that are larger than the known universe, you are performing obfuscation.

The suggested algorithm is linear, but only when applied to a very specific interpretation of the problem. I'm disagreeing with that interpretation of the problem, not the conclusion that it's linear within that particular interpretation.

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @02:08PM (#10739713)
Constant time goes beyond O(1), it means that the lower bound is equal to the upper bound. 10! can't be faster than 12!
Re:Calculating integer factorials in constant time, taking a... by tantalor on Tuesday December 15, 2015 @03:24PM (#10740228)
No, I don't think so. O(1) is "constant" time. See https://en.wikipedia.org/wiki/Time_complexity
Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Tuesday December 15, 2015 @04:11PM (#10740502)
O(1) is a constant time bound. But when people talk about constant time they often mean literally constant, such as to avoid timing attacks.
Re:Calculating integer factorials in constant time, taking a... by dragonwriter on Tuesday December 15, 2015 @04:24PM (#10740597)
Its true that constant time is sometimes used in that way, though in discussions of computation complexity, "constant time" usually means O(1).

There narrower use is more like Θ(1) with the upper and lower constants identical.

Re:Calculating integer factorials in constant time, taking a... by uxcn on Tuesday December 15, 2015 @06:43PM (#10741335)
This isn't correct. Consider an algorithm that special cases powers of two for dividing a number. Both cases take a constant number of steps, although dividing by a power of two is fewer.

The lower and upper bound differ, but they are both still constant.

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Wednesday December 16, 2015 @12:25AM (#10742557)
asymptotically constant != constant
Re:Calculating integer factorials in constant time, taking a... by uxcn on Wednesday December 16, 2015 @01:15AM (#10742703)
Asymptotically constant is what we normally talk about in relation to constant time. An algorithm that always runs in n steps with respect to input would be considered constant given the definition you're using, which would at very least be confusing.

It's also difficult to talk about constant time outside of an asymptotic context. There are a number of subtle sources for timing variances (e.g. branches, branch mispredicts, cache misses, pipeline stalls, context switches, etc..).

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Wednesday December 16, 2015 @11:45AM (#10745424)
Lower bound equaling upper bound was in addition to O(1), not instead of.

In simpler terms, it always runs in exactly k time.

It is a difficult problem. It's also a critically important one when you're doing things like cryptography. Maybe we look at different kinds of algorithms, because while I see a lot of worrying about O(n) vs. O(logn) vs. O(nlogn) vs. O(n^2), most of the time when I see people worry about whether something is constant or not, they mean truly constant, not asymptotically. They are worrying about side channels.

Re:Calculating integer factorials in constant time, taking a... by uxcn on Wednesday December 16, 2015 @04:22PM (#10747451)
I honestly haven't heard the term constant time used in a context other than asymptotic in computer science, even in relation to side-channels. I think this is the way the majority of people use the term. I worry that trying to use it another way will probably just confuse people, not to say I don't think it isn't a valid concept.

In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops?

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Wednesday December 16, 2015 @05:53PM (#10748005)
>I worry that trying to use it another way will probably just confuse people, not to say I don't think it isn't a valid concept.

I'll keep that in mind so I don't give wrong impressions in the future.

>In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops?

It can be extremely difficult to design algorithms so that they spend the same amount of time no matter what the input number is. You can't just use no-op instructions because you don't know how many cycles things will take, no-ops aren't perfect at soaking up extra time, and they don't help at all against something like an attacker on the same EC2 host. Even worse is if you have the OS interrupt mid-computation and wreck the cycle-accurate counters that would tell you how many no-ops to use. You want to design it so that the same instruction sequence happens every time, without branching based on input, without having varied memory accesses based on input. And avoiding other variable length pitfalls like division.

Re:Calculating integer factorials in constant time, taking a... by arbre on Tuesday December 15, 2015 @11:14AM (#10738571)
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.

Re:Calculating integer factorials in constant time, taking a... by wyager on Tuesday December 15, 2015 @11:38AM (#10738724)
Won't most modern compiled languages statically evaluate constant numerical expressions?
Re:Calculating integer factorials in constant time, taking a... by hellofunk on Tuesday December 15, 2015 @09:01AM (#10737762)
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.
Re:Calculating integer factorials in constant time, taking a... by mzl on Tuesday December 15, 2015 @09:19AM (#10737838)
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.
Re:Calculating integer factorials in constant time, taking a... by dietrichepp on Tuesday December 15, 2015 @09:13AM (#10737810)
I don't think it's really a stretch. It's the classic tradeoff: space versus time. The results are the same.
Re:Calculating integer factorials in constant time, taking a... by bemmu on Tuesday December 15, 2015 @09:03AM (#10737772)
Well in the first example it's calculated, just at compile time.
Re:Calculating integer factorials in constant time, taking a... by liquidise on Tuesday December 15, 2015 @12:14PM (#10738934)
Watch it. i've "calculated" more than a few project euler solutions this way.
Re:Calculating integer factorials in constant time, taking a... by dvh on Tuesday December 15, 2015 @09:32AM (#10737906)
Re:Calculating integer factorials in constant time, taking a... by uxcn on Tuesday December 15, 2015 @10:52AM (#10738435)
I was expecting to see a variant of this.
Re:Calculating integer factorials in constant time, taking a... by kleiba on Tuesday December 15, 2015 @09:33AM (#10737911)
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.
Re:Calculating integer factorials in constant time, taking a... by a1k0n on Tuesday December 15, 2015 @10:46AM (#10738398)
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.
Re:Calculating integer factorials in constant time, taking a... by jeffwass on Tuesday December 15, 2015 @01:18PM (#10739388)
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.

Re:Calculating integer factorials in constant time, taking a... by a1k0n on Wednesday December 16, 2015 @12:41AM (#10742605)
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.

Re:Calculating integer factorials in constant time, taking a... by kleiba on Wednesday December 16, 2015 @04:35PM (#10747531)
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.
Re:Calculating integer factorials in constant time, taking a... by WhitneyLand on Tuesday December 15, 2015 @09:29AM (#10737884)
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.

Re:Calculating integer factorials in constant time, taking a... by jmount on Tuesday December 15, 2015 @12:14PM (#10738937)
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.
Re:Calculating integer factorials in constant time, taking a... by noobermin on Tuesday December 15, 2015 @11:18AM (#10738588)
What do you mean? They asked you to compute something but expected you to use a lookup table instead?
Re:Calculating integer factorials in constant time, taking a... by WhitneyLand on Tuesday December 15, 2015 @03:49PM (#10740368)
Yes, it was the only way to speed up an algorithm's implementation and they wanted to see if you could realize that.
Re:Calculating integer factorials in constant time, taking a... by scott_s on Tuesday December 15, 2015 @10:47AM (#10738405)
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....
Re:Calculating integer factorials in constant time, taking a... by drfuchs on Tuesday December 15, 2015 @11:46AM (#10738765)
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.
Re:Calculating integer factorials in constant time, taking a... by uxcn on Tuesday December 15, 2015 @01:35PM (#10739502)
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.

Re:Calculating integer factorials in constant time, taking a... by scott_s on Tuesday December 15, 2015 @01:16PM (#10739377)
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.

Re:Calculating integer factorials in constant time, taking a... by ape4 on Tuesday December 15, 2015 @12:40PM (#10739100)
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, ...
Re:Calculating integer factorials in constant time, taking a... by tromp on Tuesday December 15, 2015 @02:17PM (#10739769)
Meanwhile, here's an artistic rendering of the factorial function:

    ┬────────────────
    ┼─────────────┬──
    │ ──┬──────── ┼ ┬
    │ ┬─┼─┬────── │ │
    │ │ │ ┼─┬─┬── │ │
    │ │ │ ┼─┼─┼─┬ │ │
    │ │ │ └─┤ ├─┘ │ │
    │ │ │   ├─┘   │ │
    │ │ ├───┘     │ │
    │ ├─┘         │ │
    └─┤           │ │
      └───────────┤ │
                  └─┘
(a diagram of factorial on Church numerals)
Re:Calculating integer factorials in constant time, taking a... by NelsonMinar on Tuesday December 15, 2015 @12:43PM (#10739116)
There's a similar algorithm for O(1) primality checking. It does require access to Google though.
Re:Calculating integer factorials in constant time, taking a... by mikeash on Tuesday December 15, 2015 @02:34PM (#10739889)
This also works well for reversing many cryptographic hashes.
Re:Calculating integer factorials in constant time, taking a... by banku_brougham on Tuesday December 15, 2015 @12:59PM (#10739260)
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.
Re:Calculating integer factorials in constant time, taking a... by yangshun on Tuesday December 15, 2015 @09:42AM (#10737966)
Clickbait much.