Reputation
3,179
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
Badges
1 15 22
Newest
 Good Answer
Impact
~89k people reached

Apr
3
comment Is (1/(1/x)) always a perfect round trip?
Nice use of the pigeonhole principle. It can be extended to get a bound equal to my estimate for the number of collisions. For x in (1, 2), the range (x, 2) maps onto the range (0.5, x^-1), so given the difference in ulp the proportion of collisions is at least (2 - x) - 2(x^-1 - 0.5) = 3 - x - 2x^-1. Differentiate: this has extrema when -1 + 2x^-2 = 0 i.e. x^2 = 2. Only the positive root is in range, so we get that the proportion of collisions is at least 3 - sqrt(2) - 2/sqrt(2) = 3 - 2sqrt(2).
Apr
2
awarded  Nice Answer
Apr
2
revised Is (1/(1/x)) always a perfect round trip?
Analysis backs up empirical results
Apr
1
comment Is (1/(1/x)) always a perfect round trip?
@MichaelShaw, there's no good reason to expect that the reciprocal should even be injective, which would be a precondition for double-reciprocal to round-trip. However, there's a difference between a) stating without proof that there's probably at least one number that doesn't round-trip; b) calculating and justifying an estimate for the number of mantissas which don't round-trip; c) proving that at least one mantissa doesn't round-trip. I would be quite interested to see a careful analysis which shows how good or bad my empirical measurement is.
Apr
1
comment Is (1/(1/x)) always a perfect round trip?
Empirically your rule of thumb is wrong: it returns true for slightly over 80% of values of x.
Apr
1
answered Is (1/(1/x)) always a perfect round trip?
Apr
1
comment Is (1/(1/x)) always a perfect round trip?
You cannot conclude from the fact that 1/x can't be represented exactly that 1/(1/x) != x. To take your example, in 3.s.f. decimal floating point, 1.00 / 3.00 = 0.333, and 1.00 / 0.333 is 3.00. That particular mantissa is a fixed point of the double-reciprocal in that floating point scheme.
Mar
21
comment Why interviewers want Optimal Algorithms
Are you sure they were doubtful about the correctness and not just wanting to see how clearly you were capable of explaining its working?
Mar
20
comment Login on every page requires SSL on all pages
FWIW some XSS vectors would allow the attacker to send information to an attacker-controlled site even if the page with the login form is only sent over HTTPS.
Feb
27
comment Validating Emails in PHP
@AmgadSuliman, probably not, but if you download IsEmail you can use its test suite to check most if not all of the corner cases.
Feb
27
answered Validating Emails in PHP
Feb
26
comment Tineye.com search algorithm?
@ScottWhitlock, there is an obvious approach to the problem, which is wavelet compression followed by quantising and prefix matching. Whether that's what tineye uses, I don't know.
Feb
18
awarded  Caucus
Feb
16
comment How does if/else work internally in all programming languages?
@Neil, depends on the processor's instruction set. ARM has some interesting stuff with conditional instructions.
Feb
10
answered Committing https certificates to Github…is there ever a good reason for this?
Feb
6
comment Why use partial classes?
Mixins. This could be combined with T4 to avoid manual copying...
Jan
14
awarded  Yearling
Jan
2
comment Evaluate math expressions without a stack
The approach of factoring out the a*b term works mathematically, assuming that we're using real numbers, rational numbers, or something structurally similar. But it wouldn't necessarily give the same result if we're using float, and it certainly wouldn't give the same result if we're using int (e.g. 7/2*2 gives 6). The question doesn't say what it's using, but from the comments it's definitely using int.
Jan
2
comment Evaluate math expressions without a stack
This assumes operation over a field, which isn't stated in the question and is unlikely in practice (as neither the integers nor IEEE-854 floating point representations are fields).
Jan
2
comment Evaluate math expressions without a stack
@Blrfl, I think the idea is to use a more powerful machine as the compiler.