Implement guarded fixed-point arithmetic

This commit is contained in:
RunasSudo 2021-06-14 21:43:43 +10:00
parent 3bbef933bb
commit f395e6f064
Signed by: RunasSudo
GPG Key ID: 7234E476BF21C61A
9 changed files with 414 additions and 10 deletions

View File

@ -19,7 +19,7 @@ OpenTally accepts data in the [BLT file format](https://yingtongli.me/git/OpenTa
OpenTally is highly customisable, including options for:
* different quotas and quota rules (e.g. exact Droop, Hare)
* calculations using fixed-point arithmetic or exact rational numbers
* calculations using fixed-point arithmetic, guarded fixed-point ([quasi-exact](http://www.votingmatters.org.uk/ISSUE24/I24P2.pdf)) or exact rational numbers
* different tie breaking rules (backwards, random, manual) with auditable deterministic random number generation
## Online usage

View File

@ -102,6 +102,7 @@ The algorithm used by the random number generator is specified at [rng.md](rng.m
This dropdown allows you to select how numbers (vote totals, etc.) are represented internally in memory. The options are:
* *Fixed*: Numbers are represented as fixed-precision decimals, up to a certain number of decimal places (default: 5).
* *Fixed (guarded)*: Numbers are represented as fixed-precision decimals with guard digits also known as [quasi-exact arithmetic](http://www.votingmatters.org.uk/ISSUE24/I24P2.pdf). If *n* decimal places are requested, numbers are represented up to 2*n* decimal places, and two values are considered equal if the absolute difference is less than (10<sup>*n*</sup>)/2.
* *Rational*: Numbers are represented exactly as fractions, resulting in the elimination of rounding error, but increasing computational complexity when the number of surplus transfers is very large.
* *Float (64-bit)*: Numbers are represented as native 64-bit floating-point numbers. This is fast, but not recommended as unexpectedly large rounding errors may be introduced in some circumstances.
@ -113,7 +114,7 @@ This option allows you to specify to how many decimal places votes will be repor
In the BLT file format, each set of preferences can have a specified weight this is typically used to indicate multiple voters who had the same preferences.
When ballots are not normalised (default), a set of preferences with weight *n* > 1 is represented as a single ballot with value *n*. This is known as [tree-packed ballots](http://www.votingmatters.org.uk/ISSUE21/I21P1.pdf).
When ballots are not normalised (default), a set of preferences with weight *n* > 1 is represented as a single ballot with value *n*. This is known as [list-packed ballots](http://www.votingmatters.org.uk/ISSUE21/I21P1.pdf).
When ballots are normalised, a set of preferences with weight *n* > 1 is instead converted to *n* ballots each with value 1. This is generally required only when the rules directly deal with individual ballot weights, such as when *Sum surplus transfers* is set to *Per ballot*.

View File

@ -149,7 +149,7 @@
<select id="selNumbers">
<option value="rational" selected>Rational</option>
<option value="fixed">Fixed</option>
<!--<option value="gfixed">Fixed (guarded)</option>-->
<option value="gfixed">Fixed (guarded)</option>
<option value="float64">Float (64-bit)</option>
</select>
</label>

View File

@ -15,6 +15,9 @@ onmessage = function(evt) {
if (evt.data.numbers === 'fixed') {
numbers = 'Fixed';
wasm.fixed_set_dps(evt.data.decimals);
} else if (evt.data.numbers === 'gfixed') {
numbers = 'GuardedFixed';
wasm.gfixed_set_dps(evt.data.decimals);
} else if (evt.data.numbers === 'float64') {
numbers = 'NativeFloat64';
} else if (evt.data.numbers === 'rational') {

View File

@ -17,7 +17,7 @@
use opentally::stv;
use opentally::election::{Candidate, CandidateState, CountCard, CountState, CountStateOrRef, Election, StageResult};
use opentally::numbers::{Fixed, NativeFloat64, Number, Rational};
use opentally::numbers::{Fixed, GuardedFixed, NativeFloat64, Number, Rational};
use clap::{AppSettings, Clap};
@ -52,7 +52,7 @@ struct STV {
// -- Numbers settings --
/// Numbers mode
#[clap(help_heading=Some("NUMBERS"), short, long, possible_values=&["rational", "float64", "fixed"], default_value="rational", value_name="mode")]
#[clap(help_heading=Some("NUMBERS"), short, long, possible_values=&["rational", "fixed", "gfixed", "float64"], default_value="rational", value_name="mode")]
numbers: String,
/// Decimal places if --numbers fixed
@ -175,6 +175,10 @@ fn main() {
Fixed::set_dps(cmd_opts.decimals);
let election: Election<Fixed> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
count_election(election, cmd_opts);
} else if cmd_opts.numbers == "gfixed" {
GuardedFixed::set_dps(cmd_opts.decimals);
let election: Election<GuardedFixed> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
count_election(election, cmd_opts);
}
}

358
src/numbers/gfixed.rs Normal file
View File

@ -0,0 +1,358 @@
/* OpenTally: Open-source election vote counting
* Copyright © 2021 Lee Yingtong Li (RunasSudo)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
use super::{Assign, Number};
use ibig::{IBig, ops::Abs};
use num_traits::{Num, One, Zero};
use std::cmp::{Ord, Ordering, PartialEq, PartialOrd};
use std::ops;
use std::fmt;
static mut DPS: Option<usize> = None;
static mut FACTOR: Option<IBig> = None;
static mut FACTOR_CMP: Option<IBig> = None;
#[inline]
pub fn get_dps() -> usize {
unsafe { DPS.unwrap() }
}
#[inline]
fn get_factor() -> &'static IBig {
unsafe { FACTOR.as_ref().unwrap() }
}
#[inline]
fn get_factor_cmp() -> &'static IBig {
unsafe { FACTOR_CMP.as_ref().unwrap() }
}
/// Guarded fixed-point number
#[derive(Clone, Eq)]
pub struct GuardedFixed(IBig);
impl GuardedFixed {
pub fn set_dps(dps: usize) {
unsafe {
DPS = Some(dps);
FACTOR = Some(IBig::from(10).pow(dps * 2));
FACTOR_CMP = Some(IBig::from(10).pow(dps) / IBig::from(2));
}
}
}
impl Number for GuardedFixed {
fn new() -> Self { Self(IBig::zero()) }
fn describe() -> String { format!("--numbers gfixed --decimals {}", get_dps()) }
fn pow_assign(&mut self, exponent: i32) {
self.0 = self.0.pow(exponent as usize) * get_factor() / get_factor().pow(exponent as usize);
}
fn floor_mut(&mut self, dps: usize) {
// Only do something if truncating
if dps < get_dps() * 2 {
let factor = IBig::from(10).pow(get_dps() * 2 - dps);
self.0 /= &factor;
self.0 *= factor;
}
}
fn ceil_mut(&mut self, dps: usize) {
// Only do something if truncating
if dps < get_dps() * 2 {
self.0 -= IBig::one();
let factor = IBig::from(10).pow(get_dps() * 2 - dps);
self.0 /= &factor;
self.0 += IBig::one();
self.0 *= factor;
}
}
}
impl Num for GuardedFixed {
type FromStrRadixErr = ibig::error::ParseError;
fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
match IBig::from_str_radix(str, radix) {
Ok(value) => Ok(Self(value * get_factor())),
Err(err) => Err(err)
}
}
}
impl PartialEq for GuardedFixed {
fn eq(&self, other: &GuardedFixed) -> bool {
if &(&self.0 - &other.0).abs() < get_factor_cmp() {
return true;
} else {
return false;
}
}
}
impl PartialOrd for GuardedFixed {
fn partial_cmp(&self, other: &GuardedFixed) -> Option<Ordering> {
return Some(self.cmp(other));
}
}
impl Ord for GuardedFixed {
fn cmp(&self, other: &GuardedFixed) -> Ordering {
if self.eq(other) {
return Ordering::Equal;
} else {
return self.0.cmp(&other.0);
}
}
}
impl Assign for GuardedFixed {
fn assign(&mut self, src: Self) { self.0 = src.0 }
}
impl Assign<&Self> for GuardedFixed {
fn assign(&mut self, src: &Self) { self.0 = src.0.clone() }
}
impl From<usize> for GuardedFixed {
fn from(n: usize) -> Self { Self(IBig::from(n) * get_factor()) }
}
impl From<f64> for GuardedFixed {
fn from(n: f64) -> Self {
return Self(IBig::from((n * 10_f64.powi((get_dps() * 2) as i32)).round() as u32))
}
}
impl fmt::Display for GuardedFixed {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let dps = match f.precision() {
Some(precision) => if precision < get_dps() * 2 { precision } else { get_dps() * 2 },
None => get_dps(),
};
let factor = IBig::from(10).pow(get_dps() * 2 - dps);
let mut result = (&self.0 / factor).abs().to_string();
let should_add_minus = (self.0 < IBig::zero()) && result != "0";
// Add leading 0s
result = format!("{0:0>1$}", result, dps + 1);
// Add the decimal point
if dps > 0 {
result.insert(result.len() - dps, '.');
}
// Add the sign
if should_add_minus {
result.insert(0, '-');
}
return f.write_str(&result);
}
}
impl One for GuardedFixed {
fn one() -> Self { Self(get_factor().clone()) }
}
impl Zero for GuardedFixed {
fn zero() -> Self { Self::new() }
fn is_zero(&self) -> bool { self.0.is_zero() }
}
impl ops::Neg for GuardedFixed {
type Output = Self;
fn neg(self) -> Self::Output { Self(-self.0) }
}
impl ops::Add for GuardedFixed {
type Output = Self;
fn add(self, _rhs: Self) -> Self::Output {
todo!()
}
}
impl ops::Sub for GuardedFixed {
type Output = Self;
fn sub(self, _rhs: Self) -> Self::Output {
todo!()
}
}
impl ops::Mul for GuardedFixed {
type Output = Self;
fn mul(self, _rhs: Self) -> Self::Output {
todo!()
}
}
impl ops::Div for GuardedFixed {
type Output = Self;
fn div(self, _rhs: Self) -> Self::Output {
todo!()
}
}
impl ops::Rem for GuardedFixed {
type Output = Self;
fn rem(self, _rhs: Self) -> Self::Output {
todo!()
}
}
impl ops::Add<&Self> for GuardedFixed {
type Output = Self;
fn add(self, rhs: &Self) -> Self::Output { Self(self.0 + &rhs.0) }
}
impl ops::Sub<&Self> for GuardedFixed {
type Output = Self;
fn sub(self, rhs: &Self) -> Self::Output { Self(self.0 - &rhs.0) }
}
impl ops::Mul<&Self> for GuardedFixed {
type Output = Self;
fn mul(self, rhs: &Self) -> Self::Output { Self(self.0 * &rhs.0 / get_factor()) }
}
impl ops::Div<&Self> for GuardedFixed {
type Output = Self;
fn div(self, rhs: &Self) -> Self::Output { Self(self.0 * get_factor() / &rhs.0) }
}
impl ops::Rem<&Self> for GuardedFixed {
type Output = Self;
fn rem(self, _rhs: &Self) -> Self::Output {
todo!()
}
}
impl ops::AddAssign for GuardedFixed {
fn add_assign(&mut self, rhs: Self) { self.0 += rhs.0; }
}
impl ops::SubAssign for GuardedFixed {
fn sub_assign(&mut self, rhs: Self) { self.0 -= rhs.0; }
}
impl ops::MulAssign for GuardedFixed {
fn mul_assign(&mut self, rhs: Self) {
self.0 *= rhs.0;
self.0 /= get_factor();
}
}
impl ops::DivAssign for GuardedFixed {
fn div_assign(&mut self, rhs: Self) {
self.0 *= get_factor();
self.0 /= rhs.0;
}
}
impl ops::RemAssign for GuardedFixed {
fn rem_assign(&mut self, _rhs: Self) {
todo!()
}
}
impl ops::AddAssign<&Self> for GuardedFixed {
fn add_assign(&mut self, rhs: &Self) { self.0 += &rhs.0; }
}
impl ops::SubAssign<&Self> for GuardedFixed {
fn sub_assign(&mut self, rhs: &Self) { self.0 -= &rhs.0; }
}
impl ops::MulAssign<&Self> for GuardedFixed {
fn mul_assign(&mut self, rhs: &Self) {
self.0 *= &rhs.0;
self.0 /= get_factor();
}
}
impl ops::DivAssign<&Self> for GuardedFixed {
fn div_assign(&mut self, _rhs: &Self) {
todo!()
}
}
impl ops::RemAssign<&Self> for GuardedFixed {
fn rem_assign(&mut self, _rhs: &Self) {
todo!()
}
}
impl ops::Neg for &GuardedFixed {
type Output = GuardedFixed;
fn neg(self) -> Self::Output { GuardedFixed(-&self.0) }
}
impl ops::Add<Self> for &GuardedFixed {
type Output = GuardedFixed;
fn add(self, rhs: Self) -> Self::Output { GuardedFixed(&self.0 + &rhs.0) }
}
impl ops::Sub<Self> for &GuardedFixed {
type Output = GuardedFixed;
fn sub(self, rhs: Self) -> Self::Output { GuardedFixed(&self.0 - &rhs.0) }
}
impl ops::Mul<Self> for &GuardedFixed {
type Output = GuardedFixed;
fn mul(self, _rhs: Self) -> Self::Output {
todo!()
}
}
impl ops::Div<Self> for &GuardedFixed {
type Output = GuardedFixed;
fn div(self, rhs: Self) -> Self::Output { GuardedFixed(&self.0 * get_factor() / &rhs.0) }
}
impl ops::Rem<Self> for &GuardedFixed {
type Output = GuardedFixed;
fn rem(self, _rhs: Self) -> Self::Output {
todo!()
}
}
/*
impl ops::Add<&&Rational> for &Rational {
}
impl ops::Sub<&&Rational> for &Rational {
}
impl ops::Mul<&&Rational> for &Rational {
}
impl ops::Div<&&Rational> for &Rational {
}
impl ops::Rem<&&Rational> for &Rational {
}
*/

View File

@ -17,6 +17,8 @@
/// Fixed-point arithmetic (using `ibig`)
mod fixed;
/// Guarded fixed-point arithmetic (using `ibig`)
mod gfixed;
/// Native 64-bit floating point arithmetic
mod native;
@ -73,6 +75,7 @@ where
}
pub use self::fixed::Fixed;
pub use self::gfixed::GuardedFixed;
pub use self::native::NativeFloat64;
#[cfg(not(target_arch = "wasm32"))]

View File

@ -18,7 +18,7 @@
#![allow(rustdoc::private_intra_doc_links)]
use crate::election::{CandidateState, CountState, Election};
use crate::numbers::{Fixed, NativeFloat64, Number, Rational};
use crate::numbers::{Fixed, GuardedFixed, NativeFloat64, Number, Rational};
use crate::stv;
extern crate console_error_panic_hook;
@ -34,6 +34,12 @@ pub fn fixed_set_dps(dps: usize) {
Fixed::set_dps(dps);
}
/// Wrapper for [GuardedFixed::set_dps]
#[wasm_bindgen]
pub fn gfixed_set_dps(dps: usize) {
GuardedFixed::set_dps(dps);
}
// Helper macros for making functions
macro_rules! impl_type {
@ -152,6 +158,7 @@ macro_rules! impl_type {
}
impl_type!(Fixed);
impl_type!(GuardedFixed);
impl_type!(NativeFloat64);
impl_type!(Rational);

View File

@ -18,7 +18,7 @@
// https://web.archive.org/web/20121004213938/http://www.glasgow.gov.uk/en/YourCouncil/Elections_Voting/Election_Results/ElectionScotland2007/LGWardResults.htm?ward=1&wardname=1%20-%20Linn
use opentally::election::{CandidateState, CountState, Election};
use opentally::numbers::Fixed;
use opentally::numbers::{Fixed, GuardedFixed, Number};
use opentally::stv;
use num_traits::Zero;
@ -31,8 +31,8 @@ use std::fs::File;
fn scotland_linn07_fixed5() {
let stv_opts = stv::STVOptions {
round_tvs: Some(5),
round_weights: None,
round_votes: None,
round_weights: Some(5),
round_votes: Some(5),
round_quota: Some(0),
sum_surplus_transfers: stv::SumSurplusTransfersMode::PerBallot,
normalise_ballots: true,
@ -49,7 +49,35 @@ fn scotland_linn07_fixed5() {
pp_decimals: 5,
};
Fixed::set_dps(5);
scotland_linn07::<Fixed>(stv_opts);
}
#[test]
fn scotland_linn07_gfixed5() {
let stv_opts = stv::STVOptions {
round_tvs: Some(5),
round_weights: Some(5),
round_votes: Some(5),
round_quota: Some(0),
sum_surplus_transfers: stv::SumSurplusTransfersMode::PerBallot,
normalise_ballots: true,
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
quota_mode: stv::QuotaMode::Static,
ties: vec![],
surplus: stv::SurplusMethod::WIG,
surplus_order: stv::SurplusOrder::BySize,
transferable_only: false,
exclusion: stv::ExclusionMethod::SingleStage,
bulk_exclude: false,
defer_surpluses: false,
pp_decimals: 5,
};
GuardedFixed::set_dps(5);
scotland_linn07::<GuardedFixed>(stv_opts);
}
fn scotland_linn07<N: Number>(stv_opts: stv::STVOptions) {
// Read XML file
let file = File::open("tests/data/linn07.xml").expect("IO Error");
let root = Element::parse(file).expect("Parse Error");