Nayuki
Reputation
217
Next privilege 250 Rep.
 Apr 24 comment Need help understanding Fibonacci Fast Doubling Proof I see where you're coming from. There are some algorithms whose runtime is described in terms of the value instead of the bit length. For example: Ford-Fulkerson, subset sum (dynamic programming solution). But which convention to use is a matter of opinion and style, as long as the assumptions are stated clearly Apr 24 comment Need help understanding Fibonacci Fast Doubling Proof Your answer is largely excellent. I have a problem with the last paragraph - "exponential time to compute due to the size of the output". This is not true, because the bit length of the output is linearly proportional to the value of the input. In other words, $\log_2 F(n) \in O(n)$. Mar 2 comment What does “adic” mean? The third definition is also seen in programming, especially for variadic function Mar 1 comment What's wrong with this transformation? @tdudzik Among all your steps, not every step is a bi-implication. In particular, the second step is only valid if $\cos(x) \ne 0$. Feb 23 comment Proving integer inequality Awesome. Because in my world, buggy theorems can crash computer programs. =) Feb 23 comment Proving integer inequality A slight correction: The interval should be $(1, \infty)$ because $f(1)$ is a division by zero when $c=1$. Feb 23 comment Proving integer inequality Thanks! I was able to find more information based on the full name (which wasn't clear to me before). Bernoulli's inequality at Wikipedia Feb 23 comment Proving integer inequality How does the Bernoulli step work? Feb 23 comment Proving integer inequality If there happens to be an alternative simpler/shorter answer (such as one that involves manipulating integer inequalities without calculus), I would appreciate it. I want to fully understand and internalize this part of the proof before proceeding with work that builds on it. Feb 23 comment Proving integer inequality Thank you for the quick answer! I will incorporate it into my proof and verify each line before accepting. It looks reasonable and understandable to me at a glance. Dec 28 comment What does E mean in 9.0122222900391E-5? How does this page have 125K views now?? Aug 27 comment How to solve equations to the fourth power? Further reading: en.wikipedia.org/wiki/Rational_root_theorem Aug 24 comment Show that the equation $y^2 = x^3 + 7$ has no integral solutions. Note: This is the elliptic curve used in secp256k1, which has applications in computer cryptography. Aug 24 comment Solve for $x$ in elliptic curve $y^2 = x^3 + ax + b$ Thanks! I've implemented your algorithm and it works. Specifically I implemented $\rho$ and $x_1 = c^{(p+2)/9}$. I can see that for a random sample of $y$ values, only about 1/3 of them have any solution for $x$ at all. And of course when there's a solution, there are 3 solutions. Jul 25 comment Solve for $x$ in elliptic curve $y^2 = x^3 + ax + b$ Covering the secp256k1 case is sufficient for my purposes. Sep 28 comment How to write this in mathematical notation? In your question, "either x or y" is misleading because it is possible for both x and y to be irrational and have their product be irrational too. Apr 16 comment Prove that $\lfloor \lfloor x / a\rfloor / b \rfloor = \lfloor x / (ab) \rfloor$ (a) Is $k$ constrained to be an integer? (b) How does your proof address the fact that $m$ and $n$ must be positive integers (not arbitrary real numbers)? Apr 16 comment Prove that $\lfloor \lfloor x / a\rfloor / b \rfloor = \lfloor x / (ab) \rfloor$ @MathGems: I looked at your proof, but I'm not convinced about why those bi-implications are true. I found the proof by Brian M. Scott to be better explained and easier for me to understand. Apr 13 comment Prove that $\lfloor \lfloor x / a\rfloor / b \rfloor = \lfloor x / (ab) \rfloor$ Wow André, that was a pretty terse hint. But with some work, I was able to expand it into a full solution. Thanks! Apr 13 comment Prove that $\lfloor \lfloor x / a\rfloor / b \rfloor = \lfloor x / (ab) \rfloor$ You're right. Though I feel embarrassed about asking a duplicate question, I'd like thank you very much!