Timeline for Approximate LCM of reals
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| 20 hours ago | comment | added | greybeard | (The biggest obstacle I see is the required precision: with integers, $m = ik \implies hm = hik \space \space hm= hik \forall h$, but $\vert x - fy\vert\lt\epsilon$ does not imply $\vert 2x - 2fy\vert\lt\epsilon$. Rejecting $\mathcal O(n\log(\min{\text\{\text{elems}\}}))$ may have been hasty from my side: just determine the $min$ before "GCD-ing it with every element". | |
| 23 hours ago | comment | added | Foxy | @greybeard Thank you for your comments. I was a little hasty in stating the time complexity, simply multiplying by $n$ the complexity of the standard Euclid algorithm. The complexity I gave is indeed not correct, but on reflection it turns out to be a problem that seems more complicated than expected (I'm not sure why $\max$ would be the good answer), and having limited skills in complexity analysis, I'd rather not get ahead of myself. I've modified my answer accordingly. | |
| 23 hours ago | history | edited | Foxy | CC BY-SA 4.0 |
Updated detail on time complexity.
|
| yesterday | vote | accept | Gursimar Miglani | ||
| yesterday | comment | added | D.W.♦ | I understand your analysis of the running time, but why is this correct? It seems some more analysis/argument is needed. Also, the question asks about LCM, rather than LCM. | |
| yesterday | comment | added | greybeard | "$\mathcal O(n\log(\min{\text\{\text{elems}\}}))$" not quite - consider $\min{\text\{\text{elems}\}} = 1$. Obvious would be $\max$, have fun finding a simple tighter expression. | |
| yesterday | history | answered | Foxy | CC BY-SA 4.0 |