1 /// This module provides arbitrary precision fixed-point arithmetic. 2 module bigfixed; 3 /// 4 @system unittest 5 { 6 // Return the square root of `n` to `prec` decimal places by a method of bisection. 7 string sqrt(ulong n, size_t prec) 8 { 9 import std.conv : to; 10 import std.math : ceil, log10; 11 12 immutable size_t q = (prec / log10(2.0)).ceil.to!size_t() + 1; 13 auto low = BigFixed(0, q); 14 auto high = BigFixed(n, q); 15 16 while ((high - low) != high.resolution) // BigFixed is integer internally. 17 { 18 immutable BigFixed mid = (high + low) >> 1; // Shift Expressions can be used. 19 immutable bool isLess = (mid * mid) < n; 20 if (isLess) 21 { 22 low = mid; 23 } 24 else 25 { 26 high = mid; 27 } 28 } 29 return low.toDecimalString(prec); 30 } 31 // 10 digits before the 1,000th digit. See http://www.h2.dion.ne.jp/~dra/suu/chi2/heihoukon/2.html 32 immutable sqrt2_tail = "9518488472"; 33 assert(sqrt(2, 1000)[$ - 10 .. $] == sqrt2_tail); 34 } 35 36 import std.bigint : BigInt; 37 import std.traits : isIntegral; 38 39 /** 40 A struct representing Fixed point number. 41 */ 42 struct BigFixed 43 { 44 private: 45 BigInt data; 46 size_t Q; 47 public: 48 /// Construct BigFixed from a built-in integral type 49 this(T)(T x, size_t Q) pure nothrow if (isIntegral!T) 50 { 51 data = BigInt(x); 52 this.Q = Q; 53 data <<= this.Q; 54 } 55 /// Construct BigFixed from BigInt 56 this(T : BigInt)(T x, size_t Q) pure nothrow 57 { 58 data = BigInt(x); 59 this.Q = Q; 60 data <<= this.Q; 61 } 62 /// 63 @system unittest 64 { 65 immutable ulong i = ulong.max; 66 immutable bfi1 = BigFixed(i, 10); 67 immutable bfi2 = BigFixed(BigInt(ulong.max), 10); 68 assert(bfi1 == bfi2); 69 } 70 71 /// 72 BigFixed convertQ(size_t newQ) pure nothrow const 73 { 74 if (this.Q != newQ) 75 { 76 BigFixed b = this; 77 sizediff_t diff = (cast(long) newQ) - b.Q; 78 b.data <<= diff; 79 b.Q = newQ; 80 return b; 81 } 82 else 83 { 84 return this; 85 86 } 87 } 88 /// the number of fractional bits 89 @property size_t fractional_bits() pure nothrow 90 { 91 return this.Q; 92 } 93 /// 94 @system unittest 95 { 96 auto b = BigFixed(5, 10); 97 98 assert(b.convertQ(10) == BigFixed(5, 10)); 99 assert(b.fractional_bits == 10); 100 } 101 102 /// Assignment from built-in integer types 103 BigFixed opAssign(T)(T x) pure nothrow if (isIntegral!T) 104 { 105 data = BigInt(x); 106 data <<= this.Q; 107 return this; 108 } 109 /// 110 @system unittest 111 { 112 auto b = BigFixed(5, 10); 113 b = 2; 114 assert(b == BigFixed(2, 10)); 115 } 116 117 /// Assignment from another BigFixed 118 BigFixed opAssign(T : BigFixed)(T x) pure @nogc 119 { 120 data = x.data; 121 this.Q = x.Q; 122 return this; 123 } 124 /// 125 @system unittest 126 { 127 immutable b1 = BigFixed(123, 5); 128 auto b2 = BigFixed(456, 10); 129 b2 = b1; 130 assert(b2 == BigFixed(123, 5)); 131 } 132 133 /// Convert the BigFixed to string 134 string toDecimalString(size_t decimal_digits) 135 { 136 import std.conv : to; 137 import std.string : rightJustify; 138 139 auto b = this.data * (BigInt(10) ^^ decimal_digits); 140 b >>= this.Q; 141 immutable str = b.to!string; 142 immutable sign = (this.data < 0) ? "-" : ""; 143 immutable begin = sign.length; 144 if (str.length - begin <= decimal_digits) 145 { 146 return sign ~ "0." ~ rightJustify(str[begin .. $], decimal_digits, '0'); 147 } 148 else 149 { 150 return sign ~ str[begin .. $ - decimal_digits] ~ "." ~ str[$ - decimal_digits .. $]; 151 } 152 } 153 154 /// Minimum number that can be represented greater than 0 155 @property BigFixed resolution() pure const nothrow 156 { 157 auto result = BigFixed(0, this.Q); 158 result.data = 1; 159 return result; 160 } 161 /// 162 @system unittest 163 { 164 auto b1 = BigFixed(0, 1).resolution; 165 assert(b1.toDecimalString(1) == "0.5"); 166 167 auto b2 = BigFixed(100, 1).resolution; 168 assert(b2.toDecimalString(1) == "0.5"); 169 170 auto b3 = BigFixed(100, 3).resolution; 171 assert(b3.toDecimalString(3) == "0.125"); 172 } 173 /// Implements assignment operators from BigFixed of the form `BigFixed op= BigFixed` 174 BigFixed opOpAssign(string op, T : BigFixed)(T y) pure nothrow 175 if (op == "+" || op == "-" || op == "*" || op == "/") 176 { 177 static if (op == "+" || op == "-") 178 { 179 (this.data).opOpAssign!op(y.convertQ(this.Q).data); 180 } 181 else static if (op == "*") 182 { 183 this.data *= y.convertQ(this.Q).data; 184 this.data >>= this.Q; 185 } 186 else static if (op == "/") 187 { 188 this.data <<= this.Q; 189 this.data /= y.convertQ(this.Q).data; 190 } 191 else 192 static assert(0, "BigFixed " ~ op[0 .. $ - 1] ~ "= " ~ T.stringof ~ " is not supported"); 193 return this; 194 } 195 196 @system unittest 197 { 198 auto b1 = BigFixed(1, 10); 199 b1 /= BigFixed(4, 10); 200 assert(b1.toDecimalString(2) == "0.25"); 201 b1 += BigFixed(1, 0); 202 assert(b1.toDecimalString(2) == "1.25"); 203 b1 *= BigFixed(2, 5); 204 assert(b1.toDecimalString(2) == "2.50"); 205 b1 -= BigFixed(1, 0); 206 assert(b1.toDecimalString(2) == "1.50"); 207 } 208 /// Implements assignment operators from built-in integers of the form `BigFixed op= Integer` 209 BigFixed opOpAssign(string op, T)(T y) pure nothrow 210 if ((op == "+" || op == "-" || op == "*" || op == "/" || op == ">>" 211 || op == "<<" || op == "|" || op == "&" || op == "^") && isIntegral!T) 212 { 213 static if (op == "+" || op == "-") 214 { 215 (this.data).opOpAssign!op(BigInt(y) << this.Q); 216 } 217 else static if (op == "*" || op == "/" || op == ">>" || op == "<<" 218 || op == "|" || op == "&" || op == "^") 219 { 220 (this.data).opOpAssign!op(y); 221 } 222 else 223 static assert(0, "BigFixed " ~ op[0 .. $ - 1] ~ "= " ~ T.stringof ~ " is not supported"); 224 return this; 225 } 226 /// 227 @system unittest 228 { 229 auto b1 = BigFixed(1, 10); 230 b1 /= 4; 231 assert(b1.toDecimalString(2) == "0.25"); 232 b1 += 1; 233 assert(b1.toDecimalString(2) == "1.25"); 234 b1 *= 2; 235 assert(b1.toDecimalString(2) == "2.50"); 236 b1 -= 1; 237 assert(b1.toDecimalString(2) == "1.50"); 238 b1 <<= 1; 239 assert(b1.toDecimalString(2) == "3.00"); 240 b1 >>= 2; 241 assert(b1.toDecimalString(2) == "0.75"); 242 b1 |= (1 << 5); 243 assert(b1.toDecimalString(5) == "0.78125"); 244 b1 &= (1 << 5); 245 assert(b1.toDecimalString(5) == "0.03125"); 246 b1 ^= (1 << 5); 247 assert(b1.toDecimalString(5) == "0.00000"); 248 } 249 /// Implements bitwise assignment operators from BigInt of the form `BigFixed op= BigInt` 250 BigFixed opOpAssign(string op, T : BigInt)(T y) pure nothrow 251 if (op == "+" || op == "-" || op == "*" || op == "/" || op == "|" || op == "&" 252 || op == "^") 253 { 254 static if (op == "+" || op == "-") 255 { 256 (this.data).opOpAssign!op(y << this.Q); 257 } 258 else static if (op == "*" || op == "/" || op == "|" || op == "&" || op == "^") 259 { 260 (this.data).opOpAssign!op(y); 261 } 262 else 263 static assert(0, "BigFixed " ~ op[0 .. $ - 1] ~ "= " ~ T.stringof ~ " is not supported"); 264 return this; 265 } 266 /// 267 @system unittest 268 { 269 auto b1 = BigFixed(1, 10); 270 b1 /= BigInt(4); 271 assert(b1.toDecimalString(2) == "0.25"); 272 b1 += BigInt(1); 273 assert(b1.toDecimalString(2) == "1.25"); 274 b1 *= BigInt(2); 275 assert(b1.toDecimalString(2) == "2.50"); 276 b1 -= BigInt(1); 277 assert(b1.toDecimalString(2) == "1.50"); 278 b1 |= BigInt(1 << 5); 279 assert(b1.toDecimalString(5) == "1.53125"); 280 b1 &= BigInt(1 << 5); 281 assert(b1.toDecimalString(5) == "0.03125"); 282 b1 ^= BigInt(1 << 5); 283 assert(b1.toDecimalString(5) == "0.00000"); 284 } 285 /// Implements binary operators between BigFixed 286 BigFixed opBinary(string op, T : BigFixed)(T y) pure nothrow const 287 if (op == "+" || op == "*" || op == "-" || op == "/") 288 { 289 BigFixed r = this; 290 return r.opOpAssign!(op)(y); 291 } 292 /// 293 @system unittest 294 { 295 auto b1 = BigFixed(1, 10); 296 assert((b1 / BigFixed(4, 10)).toDecimalString(2) == "0.25"); 297 assert((b1 + BigFixed(2, 10)).toDecimalString(2) == "3.00"); 298 assert((b1 * BigFixed(2, 10)).toDecimalString(2) == "2.00"); 299 assert((b1 - BigFixed(1, 10)).toDecimalString(2) == "0.00"); 300 } 301 /// Implements binary operators between BigInt 302 BigFixed opBinary(string op, T : BigInt)(T y) pure nothrow const 303 if (op == "|" || op == "&" || op == "^") 304 { 305 BigFixed r = this; 306 return r.opOpAssign!(op)(y); 307 } 308 /// 309 @system unittest 310 { 311 auto b1 = BigFixed(1, 10); 312 assert((b1 | (BigInt(1) << 9)).toDecimalString(2) == "1.50"); 313 assert((b1 & (BigInt(1) << 9)).toDecimalString(2) == "0.00"); 314 assert((b1 ^ (BigInt(1) << 9)).toDecimalString(2) == "1.50"); 315 } 316 /// Implements binary operators between Integer 317 BigFixed opBinary(string op, T)(T y) pure nothrow const 318 if ((op == "+" || op == "-" || op == "*" || op == "/" || op == ">>" 319 || op == "<<" || op == "|" || op == "&" || op == "^") && isIntegral!T) 320 { 321 BigFixed r = this; 322 return r.opOpAssign!(op)(y); 323 } 324 /// 325 @system unittest 326 { 327 auto b1 = BigFixed(1, 10); 328 assert((b1 + 1).toDecimalString(2) == "2.00"); 329 assert((b1 - 1).toDecimalString(2) == "0.00"); 330 assert((b1 * 2).toDecimalString(2) == "2.00"); 331 assert((b1 / 2).toDecimalString(2) == "0.50"); 332 assert((b1 >> 1).toDecimalString(2) == "0.50"); 333 assert((b1 << 1).toDecimalString(2) == "2.00"); 334 assert((b1 | (1 << 9)).toDecimalString(2) == "1.50"); 335 assert((b1 & 1).toDecimalString(2) == "0.00"); 336 assert((b1 ^ (1 << 9)).toDecimalString(2) == "1.50"); 337 } 338 /// Implements binary operators of the form `Integer op BigFixed` 339 BigFixed opBinaryRight(string op, T)(T y) pure nothrow const 340 if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T) 341 { 342 return this.opBinary!(op)(y); 343 } 344 /// ditto 345 BigFixed opBinaryRight(string op, T)(T y) pure nothrow 346 if ((op == "-" || op == "/") && isIntegral!T) 347 { 348 return BigFixed(y, this.Q).opBinary!(op)(this); 349 } 350 /// 351 @system unittest 352 { 353 auto b1 = BigFixed(1, 10); 354 assert((1 + b1).toDecimalString(2) == "2.00"); 355 assert((1 - b1).toDecimalString(2) == "0.00"); 356 assert((2 * b1).toDecimalString(2) == "2.00"); 357 assert((2 / b1).toDecimalString(2) == "2.00"); 358 assert(((1 << 9) | b1).toDecimalString(2) == "1.50"); 359 assert((1 & b1).toDecimalString(2) == "0.00"); 360 assert(((1 << 9) ^ b1).toDecimalString(2) == "1.50"); 361 } 362 /// Implements BigFixed equality test 363 bool opEquals()(auto ref const BigFixed y) const pure @nogc 364 { 365 return (this.data == y.data) && (this.Q == y.Q); 366 } 367 /// 368 @system unittest 369 { 370 auto x = BigFixed(1, 10) / 2; 371 auto y = BigFixed(5, 10) / 2; 372 assert(x == x); 373 assert(x != y); 374 assert((x + 2) == y); 375 } 376 /** Implements 3-way comparisons of BigFixed with BigFixed 377 or BigFixed with built-in integers. 378 **/ 379 int opCmp(ref const BigFixed y) pure nothrow const 380 { 381 return this.data.opCmp(y.convertQ(this.Q).data); 382 } 383 /// ditto 384 int opCmp(T)(T y) pure nothrow const if (isIntegral!T) 385 { 386 return this.data.opCmp(BigInt(y) << this.Q); 387 } 388 /// 389 @system unittest 390 { 391 immutable x = BigFixed(100, 10); 392 immutable y = BigFixed(10, 10); 393 immutable int z = 50; 394 const int w = 200; 395 396 assert(y < x); 397 assert(x > z); 398 assert(z > y); 399 assert(x < w); 400 } 401 /// Implement toHash so that BigFixed works properly as an AA key. 402 size_t toHash() const @safe nothrow 403 { 404 return this.data.toHash() + this.Q; 405 } 406 /// 407 @safe unittest 408 { 409 string[BigFixed] aa; 410 aa[BigFixed(123, 10)] = "abc"; 411 aa[BigFixed(456, 10)] = "def"; 412 aa[BigFixed(456, 5)] = "ghi"; 413 414 assert(aa[BigFixed(123, 10)] == "abc"); 415 assert(aa[BigFixed(456, 10)] == "def"); 416 assert(aa[BigFixed(456, 5)] == "ghi"); 417 } 418 /// Implements BigFixed unary operators. 419 BigFixed opUnary(string op)() pure nothrow const 420 if (op == "+" || op == "-" || op == "~") 421 { 422 static if (op == "+") 423 { 424 return this; 425 } 426 else static if (op == "-") 427 { 428 BigFixed r = this; 429 r.data = -r.data; 430 return r; 431 } 432 else static if (op == "~") 433 { 434 BigFixed r = this; 435 r.data = ~r.data; 436 return r; 437 } 438 } 439 /// 440 @system unittest 441 { 442 immutable x = BigFixed(1, 10) / 2; 443 444 assert(+x == x); 445 assert(-x == BigFixed(-1, 10) / 2); 446 assert(~x == -x - x.resolution); 447 } 448 }