<div dir="ltr"><div class="gmail_default" style="font-family:times new roman,serif">49 seconds to count 366 votes is pretty rough. Even if all the explosive combinatorics is in Candidates and Seats and that just scales linearly with additional votes, anything more than a small town starts to take all day to compute.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Jan 15, 2017 at 7:21 AM, Markus Schulze <span dir="ltr"><<a href="mailto:markus.schulze@alumni.tu-berlin.de" target="_blank">markus.schulze@alumni.tu-berlin.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hallo,<br>
<br>
when there are S seats and C candidates (with C > S),<br>
then there are C!/(S!*(C-S)!) possible ways to fill<br>
these seats. When you compare every possible way<br>
to fill these seats with every other possible way<br>
that differs in exactly one candidate, then you have<br>
to make C!/(S!*(C-S-1)!) comparisons. This cannot be<br>
done in a runtime that is polynomial in S and C.<br>
<br>
The largest example in Tideman's database is example A90<br>
with S=12 seats and C=20 candidates. It takes 49.0 s<br>
(on a computer with two 6-core "E5-2630v2 @ 2.60 GHz"<br>
processors) to calculate the winning set of Schulze STV.<br>
See section 10.3 of this paper:<br>
<br>
<a href="http://m-schulze.9mail.de/verylong.pdf" rel="noreferrer" target="_blank">http://m-schulze.9mail.de/very<wbr>long.pdf</a><br>
<br>
The source code (multi01g.cpp, multi01v.cpp, singl01g.cpp,<br>
singl01v.cpp) can be found in this paper:<br>
<br>
<a href="http://m-schulze.9mail.de/schulze3.zip" rel="noreferrer" target="_blank">http://m-schulze.9mail.de/schu<wbr>lze3.zip</a><br>
<br>
singl01g.cpp and singl01v.cpp are single-threading.<br>
multi01g.cpp and multi01v.cpp are multi-treading.<br>
<br>
singl01g.cpp and multi01g.cpp are for g++.<br>
singl01v.cpp and multi01v.cpp are for Microsoft Visual C++.<span class="HOEnZb"><font color="#888888"><br>
<br>
Markus Schulze</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
----<br>
Election-Methods mailing list - see <a href="http://electorama.com/em" rel="noreferrer" target="_blank">http://electorama.com/em</a> for list info<br>
</div></div></blockquote></div><br></div>