Commit d3e1f32362

@@ -93,6 +93,7 @@ pub const Int = struct {
     }
 
     pub fn clone(other: Int) !Int {
+        other.assertWritable();
         return Int{
             .allocator = other.allocator,
             .positive = other.positive,
@@ -804,11 +805,13 @@ pub const Int = struct {
             rem.positive = true;
         } else {
             // x and y are modified during division
-            var x = try a.clone();
+            var x = try Int.initCapacity(quo.allocator.?, a.len);
             defer x.deinit();
+            try x.copy(a);
 
-            var y = try b.clone();
+            var y = try Int.initCapacity(quo.allocator.?, b.len);
             defer y.deinit();
+            try y.copy(b);
 
             // x may grow one limb during normalization
             try quo.ensureCapacity(a.len + y.len);

@@ -3,6 +3,7 @@ const builtin = @import("builtin");
 const debug = std.debug;
 const math = std.math;
 const mem = std.mem;
+const testing = std.testing;
 const Allocator = mem.Allocator;
 const ArrayList = std.ArrayList;
 
@@ -425,6 +426,7 @@ var al = debug.global_allocator;
 const SignedDoubleLimb = @IntType(true, DoubleLimb.bit_count);
 
 fn gcd(rma: *Int, x: Int, y: Int) !void {
+    rma.assertWritable();
     var r = rma;
     var aliased = rma.limbs.ptr == x.limbs.ptr or rma.limbs.ptr == y.limbs.ptr;
 
@@ -463,19 +465,23 @@ fn FixedIntFromSignedDoubleLimb(A: SignedDoubleLimb, storage: []Limb) Int {
 //
 // r = gcd(x, y) where x, y > 0
 fn gcdLehmer(r: *Int, xa: Int, ya: Int) !void {
-    debug.assert(xa.positive and ya.positive);
-    debug.assert(xa.cmp(ya) >= 0);
-
     var x = try xa.clone();
+    x.abs();
     defer x.deinit();
 
     var y = try ya.clone();
+    y.abs();
     defer y.deinit();
 
+    if (x.cmp(y) < 0) {
+        x.swap(&y);
+    }
+
     var T = try Int.init(r.allocator.?);
     defer T.deinit();
 
     while (y.len > 1) {
+        debug.assert(x.positive and y.positive);
         debug.assert(x.len >= y.len);
 
         // chop the leading zeros of the limbs and normalize
@@ -540,7 +546,13 @@ fn gcdLehmer(r: *Int, xa: Int, ya: Int) !void {
             try r.add(x, r.*);
 
             x.swap(&T);
+            x.abs();
             y.swap(r);
+            y.abs();
+
+            if (x.cmp(y) < 0) {
+                x.swap(&y);
+            }
         }
     }
 
@@ -563,7 +575,7 @@ test "big.rational gcd non-one small" {
 
     try gcd(&r, a, b);
 
-    debug.assert((try r.to(u32)) == 1);
+    testing.expect((try r.to(u32)) == 1);
 }
 
 test "big.rational gcd non-one small" {
@@ -573,7 +585,7 @@ test "big.rational gcd non-one small" {
 
     try gcd(&r, a, b);
 
-    debug.assert((try r.to(u32)) == 38);
+    testing.expect((try r.to(u32)) == 38);
 }
 
 test "big.rational gcd non-one large" {
@@ -583,7 +595,7 @@ test "big.rational gcd non-one large" {
 
     try gcd(&r, a, b);
 
-    debug.assert((try r.to(u32)) == 4369);
+    testing.expect((try r.to(u32)) == 4369);
 }
 
 test "big.rational gcd large multi-limb result" {
@@ -593,11 +605,11 @@ test "big.rational gcd large multi-limb result" {
 
     try gcd(&r, a, b);
 
-    debug.assert((try r.to(u256)) == 0xf000000ff00000fff0000ffff000fffff00ffffff1);
+    testing.expect((try r.to(u256)) == 0xf000000ff00000fff0000ffff000fffff00ffffff1);
 }
 
 fn extractLowBits(a: Int, comptime T: type) T {
-    debug.assert(@typeId(T) == builtin.TypeId.Int);
+    testing.expect(@typeId(T) == builtin.TypeId.Int);
 
     if (T.bit_count <= Limb.bit_count) {
         return @truncate(T, a.limbs[0]);
@@ -619,71 +631,71 @@ test "big.rational extractLowBits" {
     var a = try Int.initSet(al, 0x11112222333344441234567887654321);
 
     const a1 = extractLowBits(a, u8);
-    debug.assert(a1 == 0x21);
+    testing.expect(a1 == 0x21);
 
     const a2 = extractLowBits(a, u16);
-    debug.assert(a2 == 0x4321);
+    testing.expect(a2 == 0x4321);
 
     const a3 = extractLowBits(a, u32);
-    debug.assert(a3 == 0x87654321);
+    testing.expect(a3 == 0x87654321);
 
     const a4 = extractLowBits(a, u64);
-    debug.assert(a4 == 0x1234567887654321);
+    testing.expect(a4 == 0x1234567887654321);
 
     const a5 = extractLowBits(a, u128);
-    debug.assert(a5 == 0x11112222333344441234567887654321);
+    testing.expect(a5 == 0x11112222333344441234567887654321);
 }
 
 test "big.rational set" {
     var a = try Rational.init(al);
 
     try a.setInt(5);
-    debug.assert((try a.p.to(u32)) == 5);
-    debug.assert((try a.q.to(u32)) == 1);
+    testing.expect((try a.p.to(u32)) == 5);
+    testing.expect((try a.q.to(u32)) == 1);
 
     try a.setRatio(7, 3);
-    debug.assert((try a.p.to(u32)) == 7);
-    debug.assert((try a.q.to(u32)) == 3);
+    testing.expect((try a.p.to(u32)) == 7);
+    testing.expect((try a.q.to(u32)) == 3);
 
     try a.setRatio(9, 3);
-    debug.assert((try a.p.to(i32)) == 3);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == 3);
+    testing.expect((try a.q.to(i32)) == 1);
 
     try a.setRatio(-9, 3);
-    debug.assert((try a.p.to(i32)) == -3);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == -3);
+    testing.expect((try a.q.to(i32)) == 1);
 
     try a.setRatio(9, -3);
-    debug.assert((try a.p.to(i32)) == -3);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == -3);
+    testing.expect((try a.q.to(i32)) == 1);
 
     try a.setRatio(-9, -3);
-    debug.assert((try a.p.to(i32)) == 3);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == 3);
+    testing.expect((try a.q.to(i32)) == 1);
 }
 
 test "big.rational setFloat" {
     var a = try Rational.init(al);
 
     try a.setFloat(f64, 2.5);
-    debug.assert((try a.p.to(i32)) == 5);
-    debug.assert((try a.q.to(i32)) == 2);
+    testing.expect((try a.p.to(i32)) == 5);
+    testing.expect((try a.q.to(i32)) == 2);
 
     try a.setFloat(f32, -2.5);
-    debug.assert((try a.p.to(i32)) == -5);
-    debug.assert((try a.q.to(i32)) == 2);
+    testing.expect((try a.p.to(i32)) == -5);
+    testing.expect((try a.q.to(i32)) == 2);
 
     try a.setFloat(f32, 3.141593);
 
     //                = 3.14159297943115234375
-    debug.assert((try a.p.to(u32)) == 3294199);
-    debug.assert((try a.q.to(u32)) == 1048576);
+    testing.expect((try a.p.to(u32)) == 3294199);
+    testing.expect((try a.q.to(u32)) == 1048576);
 
     try a.setFloat(f64, 72.141593120712409172417410926841290461290467124);
 
     //                = 72.1415931207124145885245525278151035308837890625
-    debug.assert((try a.p.to(u128)) == 5076513310880537);
-    debug.assert((try a.q.to(u128)) == 70368744177664);
+    testing.expect((try a.p.to(u128)) == 5076513310880537);
+    testing.expect((try a.q.to(u128)) == 70368744177664);
 }
 
 test "big.rational setFloatString" {
@@ -692,8 +704,8 @@ test "big.rational setFloatString" {
     try a.setFloatString("72.14159312071241458852455252781510353");
 
     //                  = 72.1415931207124145885245525278151035308837890625
-    debug.assert((try a.p.to(u128)) == 7214159312071241458852455252781510353);
-    debug.assert((try a.q.to(u128)) == 100000000000000000000000000000000000);
+    testing.expect((try a.p.to(u128)) == 7214159312071241458852455252781510353);
+    testing.expect((try a.q.to(u128)) == 100000000000000000000000000000000000);
 }
 
 test "big.rational toFloat" {
@@ -701,11 +713,11 @@ test "big.rational toFloat" {
 
     // = 3.14159297943115234375
     try a.setRatio(3294199, 1048576);
-    debug.assert((try a.toFloat(f64)) == 3.14159297943115234375);
+    testing.expect((try a.toFloat(f64)) == 3.14159297943115234375);
 
     // = 72.1415931207124145885245525278151035308837890625
     try a.setRatio(5076513310880537, 70368744177664);
-    debug.assert((try a.toFloat(f64)) == 72.141593120712409172417410926841290461290467124);
+    testing.expect((try a.toFloat(f64)) == 72.141593120712409172417410926841290461290467124);
 }
 
 test "big.rational set/to Float round-trip" {
@@ -720,7 +732,7 @@ test "big.rational set/to Float round-trip" {
     while (i < 512) : (i += 1) {
         const r = prng.random.float(f64);
         try a.setFloat(f64, r);
-        debug.assert((try a.toFloat(f64)) == r);
+        testing.expect((try a.toFloat(f64)) == r);
     }
 }
 
@@ -730,54 +742,54 @@ test "big.rational copy" {
     const b = try Int.initSet(al, 5);
 
     try a.copyInt(b);
-    debug.assert((try a.p.to(u32)) == 5);
-    debug.assert((try a.q.to(u32)) == 1);
+    testing.expect((try a.p.to(u32)) == 5);
+    testing.expect((try a.q.to(u32)) == 1);
 
     const c = try Int.initSet(al, 7);
     const d = try Int.initSet(al, 3);
 
     try a.copyRatio(c, d);
-    debug.assert((try a.p.to(u32)) == 7);
-    debug.assert((try a.q.to(u32)) == 3);
+    testing.expect((try a.p.to(u32)) == 7);
+    testing.expect((try a.q.to(u32)) == 3);
 
     const e = try Int.initSet(al, 9);
     const f = try Int.initSet(al, 3);
 
     try a.copyRatio(e, f);
-    debug.assert((try a.p.to(u32)) == 3);
-    debug.assert((try a.q.to(u32)) == 1);
+    testing.expect((try a.p.to(u32)) == 3);
+    testing.expect((try a.q.to(u32)) == 1);
 }
 
 test "big.rational negate" {
     var a = try Rational.init(al);
 
     try a.setInt(-50);
-    debug.assert((try a.p.to(i32)) == -50);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == -50);
+    testing.expect((try a.q.to(i32)) == 1);
 
     a.negate();
-    debug.assert((try a.p.to(i32)) == 50);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == 50);
+    testing.expect((try a.q.to(i32)) == 1);
 
     a.negate();
-    debug.assert((try a.p.to(i32)) == -50);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == -50);
+    testing.expect((try a.q.to(i32)) == 1);
 }
 
 test "big.rational abs" {
     var a = try Rational.init(al);
 
     try a.setInt(-50);
-    debug.assert((try a.p.to(i32)) == -50);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == -50);
+    testing.expect((try a.q.to(i32)) == 1);
 
     a.abs();
-    debug.assert((try a.p.to(i32)) == 50);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == 50);
+    testing.expect((try a.q.to(i32)) == 1);
 
     a.abs();
-    debug.assert((try a.p.to(i32)) == 50);
-    debug.assert((try a.q.to(i32)) == 1);
+    testing.expect((try a.p.to(i32)) == 50);
+    testing.expect((try a.q.to(i32)) == 1);
 }
 
 test "big.rational swap" {
@@ -787,19 +799,19 @@ test "big.rational swap" {
     try a.setRatio(50, 23);
     try b.setRatio(17, 3);
 
-    debug.assert((try a.p.to(u32)) == 50);
-    debug.assert((try a.q.to(u32)) == 23);
+    testing.expect((try a.p.to(u32)) == 50);
+    testing.expect((try a.q.to(u32)) == 23);
 
-    debug.assert((try b.p.to(u32)) == 17);
-    debug.assert((try b.q.to(u32)) == 3);
+    testing.expect((try b.p.to(u32)) == 17);
+    testing.expect((try b.q.to(u32)) == 3);
 
     a.swap(&b);
 
-    debug.assert((try a.p.to(u32)) == 17);
-    debug.assert((try a.q.to(u32)) == 3);
+    testing.expect((try a.p.to(u32)) == 17);
+    testing.expect((try a.q.to(u32)) == 3);
 
-    debug.assert((try b.p.to(u32)) == 50);
-    debug.assert((try b.q.to(u32)) == 23);
+    testing.expect((try b.p.to(u32)) == 50);
+    testing.expect((try b.q.to(u32)) == 23);
 }
 
 test "big.rational cmp" {
@@ -808,11 +820,11 @@ test "big.rational cmp" {
 
     try a.setRatio(500, 231);
     try b.setRatio(18903, 8584);
-    debug.assert((try a.cmp(b)) < 0);
+    testing.expect((try a.cmp(b)) < 0);
 
     try a.setRatio(890, 10);
     try b.setRatio(89, 1);
-    debug.assert((try a.cmp(b)) == 0);
+    testing.expect((try a.cmp(b)) == 0);
 }
 
 test "big.rational add single-limb" {
@@ -821,11 +833,11 @@ test "big.rational add single-limb" {
 
     try a.setRatio(500, 231);
     try b.setRatio(18903, 8584);
-    debug.assert((try a.cmp(b)) < 0);
+    testing.expect((try a.cmp(b)) < 0);
 
     try a.setRatio(890, 10);
     try b.setRatio(89, 1);
-    debug.assert((try a.cmp(b)) == 0);
+    testing.expect((try a.cmp(b)) == 0);
 }
 
 test "big.rational add" {
@@ -838,7 +850,7 @@ test "big.rational add" {
     try a.add(a, b);
 
     try r.setRatio(984786924199, 290395044174);
-    debug.assert((try a.cmp(r)) == 0);
+    testing.expect((try a.cmp(r)) == 0);
 }
 
 test "big.rational sub" {
@@ -851,7 +863,7 @@ test "big.rational sub" {
     try a.sub(a, b);
 
     try r.setRatio(979040510045, 290395044174);
-    debug.assert((try a.cmp(r)) == 0);
+    testing.expect((try a.cmp(r)) == 0);
 }
 
 test "big.rational mul" {
@@ -864,7 +876,7 @@ test "big.rational mul" {
     try a.mul(a, b);
 
     try r.setRatio(571481443, 17082061422);
-    debug.assert((try a.cmp(r)) == 0);
+    testing.expect((try a.cmp(r)) == 0);
 }
 
 test "big.rational div" {
@@ -877,7 +889,7 @@ test "big.rational div" {
     try a.div(a, b);
 
     try r.setRatio(75531824394, 221015929);
-    debug.assert((try a.cmp(r)) == 0);
+    testing.expect((try a.cmp(r)) == 0);
 }
 
 test "big.rational div" {
@@ -888,11 +900,11 @@ test "big.rational div" {
     a.invert();
 
     try r.setRatio(23341, 78923);
-    debug.assert((try a.cmp(r)) == 0);
+    testing.expect((try a.cmp(r)) == 0);
 
     try a.setRatio(-78923, 23341);
     a.invert();
 
     try r.setRatio(-23341, 78923);
-    debug.assert((try a.cmp(r)) == 0);
+    testing.expect((try a.cmp(r)) == 0);
 }