Reputation
291
Top tag
Next privilege 500 Rep.
Access review queues
Badges
2 8
Impact
~4k people reached

  • 0 posts edited
  • 0 helpful flags
  • 7 votes cast
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