jonderry
Reputation
281
Top tag
Next privilege 500 Rep.
Access review queues
 Oct24 awarded Curious Oct23 comment How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)? Yes, I mentioned that :) Oct23 asked How to number the natural numbers lexicographically with minimal overhead (and provide a lower bound for the overhead)? Nov4 awarded Nice Question Apr1 awarded Popular Question Nov23 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. Nov22 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. Nov22 asked How to compute n choose k modulo a prime power efficiently using extended Lucas' Theorem? May16 accepted Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently Apr29 accepted Integrate over $t$ if $dr/dt = \sqrt{1 - r^2}$? Apr29 asked Integrate over $t$ if $dr/dt = \sqrt{1 - r^2}$? Oct19 awarded Yearling Aug29 awarded Commentator Aug29 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. Aug26 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). Aug25 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? Aug25 revised Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently fix the problem statement Aug24 awarded Editor Aug24 revised Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently clarify the title Aug24 comment Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently @Aryabhata, Exactly. I don't need to represent the expanded number, just the exponent. The input to the problem is the exponent $n$ and the return value is another exponent $m$. I'm asking whether I need to go through the intermediate step of expanding to the full binary representation of $3^n$ to solve the problem (or expand $\lg 3$ to a similar number of bits of precision).