jonderry
Reputation
291
Top tag
Next privilege 500 Rep.
Access review queues
 Aug 30 awarded Notable Question Oct 24 awarded Curious Oct 23 comment How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)? Yes, I mentioned that :) Oct 23 asked How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)? Nov 4 awarded Nice Question Apr 1 awarded Popular Question Nov 23 comment How to compute n choose k modulo a prime power efficiently using extended Lucas' Theorem? I saw that answer, but it's still a bit opaque to me how that translates into a working algorithm. Nov 22 comment How to compute n choose k modulo a prime power efficiently using extended Lucas' Theorem? Thanks, but this link is for Lucas' original Theorem, which only works for primes. I understand Lucas' original Theorem reasonably well. Nov 22 asked How to compute n choose k modulo a prime power efficiently using extended Lucas' Theorem? May 16 accepted Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently Apr 29 accepted Integrate over $t$ if $dr/dt = \sqrt{1 - r^2}$? Apr 29 asked Integrate over $t$ if $dr/dt = \sqrt{1 - r^2}$? Oct 19 awarded Yearling Aug 29 awarded Commentator Aug 29 comment Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently Yes, any ideas you have would be great. Aug 26 comment Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently I was mainly interested in the 'hard' cases where the numbers are very close together, but I think the application of this algorithm that I had in mind should have a small number of such cases. Still, it needs to be correct, so variable precision is needed for instances in which the results are close at low precision. This solution is one approach to variable precision (+1). Aug 25 comment Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently The $\log(n)^{\mathrm{th}}$ term will have $\Omega(n)$ bits in its representation, right? Won't this still require $\Omega(n)$ time? Aug 25 revised Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently fix the problem statement Aug 24 awarded Editor Aug 24 revised Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently clarify the title