Timeline for Integer square root of integer [closed]
Current License: CC BY-SA 3.0
58 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2018 at 17:20 | review | Reopen votes | |||
| Sep 22, 2018 at 11:12 | |||||
| Jul 16, 2018 at 4:14 | history | closed |
Wheat Wizard♦ Laikoni user202729 Asone Tuhid user45941 |
Needs details or clarity | |
| Jul 13, 2018 at 15:59 | review | Close votes | |||
| Jul 14, 2018 at 11:20 | |||||
| Aug 23, 2016 at 5:21 | answer | added | Chris | timeline score: 2 | |
| Jul 5, 2016 at 17:06 | answer | added | Toby Speight | timeline score: 1 | |
| Jul 4, 2016 at 8:00 | answer | added | Blue | timeline score: 1 | |
| Jul 4, 2016 at 7:33 | answer | added | Byeonggon Lee | timeline score: 0 | |
| Jun 29, 2016 at 23:55 | answer | added | juh | timeline score: 2 | |
| Jun 16, 2016 at 14:07 | answer | added | shrx | timeline score: 1 | |
| Jun 16, 2016 at 12:53 | answer | added | GoatInTheMachine | timeline score: 1 | |
| Jun 16, 2016 at 10:52 | answer | added | Adám | timeline score: 1 | |
| Jun 15, 2016 at 17:26 | answer | added | Patrick Roberts | timeline score: 1 | |
| Jun 15, 2016 at 14:32 | answer | added | m654 | timeline score: 0 | |
| Jun 13, 2016 at 22:02 | answer | added | QuantumKarl | timeline score: 3 | |
| Jun 13, 2016 at 20:48 | answer | added | Digital Trauma | timeline score: 7 | |
| Sep 3, 2014 at 15:58 | answer | added | Peter Taylor | timeline score: 1 | |
| Sep 2, 2014 at 19:51 | answer | added | Darren Stone | timeline score: 2 | |
| Sep 2, 2014 at 6:34 | answer | added | Darren Stone | timeline score: 1 | |
| Sep 1, 2014 at 20:14 | answer | added | ɐɔıʇǝɥʇuʎs | timeline score: 3 | |
| Aug 8, 2014 at 17:52 | answer | added | Rajkumar Madhuram | timeline score: 4 | |
| Aug 1, 2014 at 4:05 | answer | added | shadowtalker | timeline score: 2 | |
| Jul 30, 2014 at 19:27 | answer | added | bacchusbeale | timeline score: 1 | |
| Jul 30, 2014 at 18:10 | answer | added | fuandon | timeline score: 2 | |
| Jul 30, 2014 at 10:41 | answer | added | mantal | timeline score: 1 | |
| Jul 30, 2014 at 5:30 | answer | added | proud haskeller | timeline score: 3 | |
| Jul 30, 2014 at 0:31 | answer | added | Ben Reich | timeline score: 4 | |
| Jul 29, 2014 at 18:42 | answer | added | O-I | timeline score: 5 | |
| Jul 29, 2014 at 4:51 | answer | added | Eliseo D'Annunzio | timeline score: 2 | |
| Jul 27, 2014 at 22:26 | answer | added | Zaq | timeline score: 10 | |
| Jul 27, 2014 at 22:22 | answer | added | hobbs | timeline score: 6 | |
| Jul 27, 2014 at 18:47 | history | tweeted | twitter.com/#!/StackCodeGolf/status/493467673779765249 | ||
| Jul 27, 2014 at 14:00 | answer | added | edc65 | timeline score: 4 | |
| Jul 27, 2014 at 13:18 | answer | added | flawr | timeline score: 5 | |
| Jul 27, 2014 at 13:08 | answer | added | Bob | timeline score: 4 | |
| Jul 27, 2014 at 12:21 | answer | added | Οurous | timeline score: 3 | |
| Jul 27, 2014 at 4:33 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 90 characters in body
|
| Jul 27, 2014 at 3:17 | answer | added | isaacg | timeline score: 7 | |
| Jul 27, 2014 at 2:41 | comment | added | Todd Lehman |
@user2357112 — Yeah, definitely. Gotta use something like long double in C to get the whole 64-bit unsigned integer range (which does work, BTW...I've verified). Of course, this requires your compiler to implement long double such that sizeof(long double) >= 10.
|
|
| Jul 27, 2014 at 2:40 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 6 characters in body
|
| Jul 27, 2014 at 2:32 | comment | added | user2357112 | Most floating-point data types don't have the precision needed for this task anyway. 53 significant bits isn't enough for the whole input range. | |
| Jul 27, 2014 at 2:27 | answer | added | Matt Noonan | timeline score: 4 | |
| Jul 27, 2014 at 2:23 | answer | added | xnor | timeline score: 4 | |
| Jul 27, 2014 at 1:05 | comment | added | Milo | @ToddLehman ok :) | |
| Jul 27, 2014 at 1:05 | comment | added | Todd Lehman | @Milo — Right. Don't raise something to the 2/4 power either. Heh. No fractional exponents was really the intention of my statement. | |
| Jul 27, 2014 at 1:02 | comment | added | Milo | Does 2/4 count? | |
| Jul 27, 2014 at 0:12 | answer | added | Dennis | timeline score: 14 | |
| Jul 26, 2014 at 23:41 | answer | added | AndoDaan | timeline score: 3 | |
| Jul 26, 2014 at 21:34 | answer | added | seequ | timeline score: 3 | |
| Jul 26, 2014 at 21:13 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 62 characters in body
|
| Jul 26, 2014 at 21:08 | comment | added | Todd Lehman | @JanDvorak — Ah yes. If 2^k ≤ n < 2^{k+1}, k≥0 ∈ ℤ, then O(log₂(n)) = O(log₂(2^k)) = O(k), and O(√n) = O(√{2^k}) = O(2^{k/2}), which is exponential in k, as you point out. I wrote O(log₂(n)) because I was thinking more in terms of the input value n than in terms of n's scale, so without specifying what I meant by n, I'm sure that was pretty confusing. | |
| Jul 26, 2014 at 21:06 | answer | added | John Dvorak | timeline score: 7 | |
| Jul 26, 2014 at 20:50 | comment | added | John Dvorak |
Umm... O(log_2 n) === O(log_4 n). log_4(n) = log_2(n) / log_2(2) = log_2(n) / 2
|
|
| Jul 26, 2014 at 20:50 | comment | added | John Dvorak | Normally one uses the size of the input rather than the input value to derive algorithmic complexity. In that sense the increment-and-retry algorithm is exponential in speed. | |
| Jul 26, 2014 at 20:48 | comment | added | Todd Lehman | @JanDvorak — I guess I meant it in more than the bonus sense. It wasn't until after formulating the original question that I realized it would be trivial to write a simple O(√n) looping version in very few number of characters, which isn't really very interesting. So in some sense, it's a separate challenge, but really I am looking for solutions that are good performance, e.g., O(log₂(n)) or O(log₄(n)). | |
| Jul 26, 2014 at 20:44 | answer | added | Todd Lehman | timeline score: 4 | |
| Jul 26, 2014 at 20:35 | answer | added | Todd Lehman | timeline score: 2 | |
| Jul 26, 2014 at 20:34 | comment | added | John Dvorak | "but O(log₄(n)) time would really be better." - how much better? Is there a bonus? Is that a hard requirement? Is it essentially a separate challenge? Is that just a nice idea that doesn't really affect the scoring? | |
| Jul 26, 2014 at 20:23 | history | asked | Todd Lehman | CC BY-SA 3.0 |