Compiler Explorer

Source code

const std = @import("std");
const bigint = std.math.big.int;

const allocator = std.heap.c_allocator;

pub fn main() !void {
    const stdout = std.io.getStdOut();

var k = try bigint.Managed.initSet(allocator, 1);
    defer k.deinit();
    var i: u32 = 0;
    const n: u32 = 10000; // atoi(argv[1]);

var u = try bigint.Managed.init(allocator);
    defer u.deinit();
    var v = try bigint.Managed.init(allocator);
    defer v.deinit();

var w = try bigint.Managed.initSet(allocator, 0);
    defer w.deinit();
    var n1 = try bigint.Managed.initSet(allocator, 4);
    defer n1.deinit();
    var n2 = try bigint.Managed.initSet(allocator, 3);
    defer n2.deinit();
    var d = try bigint.Managed.initSet(allocator, 1);
    defer d.deinit();
    
    var ten_managed = try bigint.Managed.initSet(allocator, 10);
    defer ten_managed.deinit();
    const ten = ten_managed.toConst();
    
    var minus_ten_managed = try bigint.Managed.initSet(allocator, -10);
    defer minus_ten_managed.deinit();
    const minus_ten = minus_ten_managed.toConst();

while (true) {
        {
            var r = try bigint.Managed.init(allocator);
            defer r.deinit();
            try u.divTrunc(&r, n1.toConst(), d.toConst());
        }
        {
            var r = try bigint.Managed.init(allocator);
            defer r.deinit();
            try v.divTrunc(&r, n2.toConst(), d.toConst());
        }
    
        if (bigint.Managed.eq(u, v)) {
            try stdout.writer().print("{}", .{u.to(u4) catch unreachable});
            i += 1;
            if (i % 10 == 0) {
                try stdout.writer().print("\t:{}\n", .{i});
            }
            if (i == n) {
                break;
            }
    
            // extract
            try u.ensureMulCapacity(u.toConst(), minus_ten);
            u.mul(u.toConst(), minus_ten) catch unreachable;
            try u.ensureMulCapacity(d.toConst(), u.toConst());
            u.mul(d.toConst(), u.toConst()) catch unreachable;
            try n1.ensureMulCapacity(n1.toConst(), ten);
            n1.mul(n1.toConst(), ten) catch unreachable;
            try n1.add(n1.toConst(), u.toConst());
            try n2.ensureMulCapacity(n2.toConst(), ten);
            n2.mul(n2.toConst(), ten) catch unreachable;
            try n2.add(n2.toConst(), u.toConst());
        } else {
            // produce
            // k2 = k * 2 - 1
            var k2 = try k.clone();
            defer k2.deinit();
            try k2.shiftLeft(k2, 1);
            try k2.addScalar(k2.toConst(), -1);
            // u = n1 * k2
            try u.mul(n1.toConst(), k2.toConst());
            // v = n2 + n2
            try v.add(n2.toConst(), n2.toConst());
            // k = k - 1
            try k.addScalar(k.toConst(), -1);
            try w.mul(n1.toConst(), k.toConst());
            try n1.add(u.toConst(), v.toConst());
            // k = k + 3
            try k.addScalar(k.toConst(), 3);
            // u = n2 * k
            try u.mul(n2.toConst(), k.toConst());
            // n2 = w + u
            try n2.add(w.toConst(), u.toConst());
            // k2 = k2 + 2
            try k2.addScalar(k2.toConst(), 2);
            // d = d * k2
            try d.ensureMulCapacity(d.toConst(), k2.toConst());
            d.mul(d.toConst(), k2.toConst()) catch unreachable;
            // k = k - 1
            try k.addScalar(k.toConst(), -1);
        }
    }
    
    if (i % 10 != 0) {
        try stdout.writer().print("{}\n", .{n});
    }
}