256 reputation
17
bio website
location
age
visits member for 3 years, 6 months
seen Apr 9 at 23:03

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
Aug
24
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).
Aug
24
comment Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently
Both of these ideas still require $\Omega(n)$ time. Note that the final repeated squaring alone requires $\Omega(n \lg n)$ time because of the size of the numbers involved. For the logarithm idea, you still need a lot of precision to get the exact answer.
Aug
24
asked Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently
Apr
10
comment If $g$ is a primitive root of $p^2$ where $p$ is an odd prime, why is $g$ a primitive root of $p^k$ for any $k \geq 1$?
Don't you mean $g^{p^{k - 1}(p - 1)}$, and similarly with some of the other expressions?