meta user
network profile
| bio | website | |
|---|---|---|
| location | ||
| age | ||
| visits | member for | 2 years, 7 months |
| seen | Apr 20 at 8:01 | |
| stats | profile views | 20 |
|
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? |
|
Apr 10 |
accepted | 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$? |
