Timeline for Minimal cover of bases for quadratic residue testing of squareness
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:41 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Aug 4, 2014 at 9:59 | history | tweeted | twitter.com/#!/StackCodeGolf/status/496233840932048896 | ||
| Aug 3, 2014 at 20:08 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 273 characters in body
|
| Aug 3, 2014 at 18:55 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 4 characters in body
|
| Aug 3, 2014 at 18:34 | answer | added | Martin Ender | timeline score: 7 | |
| Aug 3, 2014 at 17:58 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 558 characters in body
|
| Aug 3, 2014 at 10:59 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 8 characters in body
|
| Aug 3, 2014 at 10:42 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 1459 characters in body
|
| Aug 3, 2014 at 9:47 | comment | added | Todd Lehman | In the case of large n spaces, I think I will have to decide the tie based on the overall estimated efficiency, as calculated by multiplying the probabilities predicted by each residue set. For example, the bases {8,11,13,15} have probabilities of 0.375, 0.545455, 0.538462, and 0.4, respectively, which multiply to 0.044056. Subtracting from 1, this gives 0.955944, which agrees very closely with the exhaustive counting result of 95.62% as measured over all n in [0,2^24-1]. | |
| Aug 3, 2014 at 9:30 | comment | added | Martin Ender | Yeah, that makes sense. But will you decide the tie just by the first base whose probability differs, or how will you figure out the efficiency of the entire set based on the probabilities? I'm also thinking that the probabilities aren't independent any more once you've checked other bases. | |
| Aug 3, 2014 at 9:23 | comment | added | Todd Lehman | I'll look at the cardinality of the sets of quadratic residues for each base. For example, 4 is a better base than 3, because only half of the values modulo 4 are quadratic residues, whereas two-thirds of the values modulo 3 are quadratic residues. Thus, 4 has a greater ability to weed out numbers earlier. The worst base is 2, because it cannot rule out any number, and the best base less than 256 is 240, which is capable of ruling out 90% of numbers. Might have to do Monte Carlo sampling for really large bases. | |
| Aug 3, 2014 at 9:18 | comment | added | Martin Ender | How will you determine the tie-breaker short of testing every single number in the given range and counting how many checks were made in total? | |
| Aug 3, 2014 at 9:12 | history | edited | Todd Lehman | CC BY-SA 3.0 |
deleted 26 characters in body
|
| Aug 3, 2014 at 8:28 | history | edited | Todd Lehman | CC BY-SA 3.0 |
deleted 26 characters in body
|
| Aug 3, 2014 at 8:19 | history | edited | Todd Lehman | CC BY-SA 3.0 |
added 225 characters in body; edited title
|
| Aug 3, 2014 at 7:58 | history | asked | Todd Lehman | CC BY-SA 3.0 |