Extremely slow integer multiplication and math.pow

[oittaa]

I'm new to Zig so I might have missed something, but the documentation talks about integers being usable up to 65535 bits. But on my machine they become basically unusable long before that.

This relatively simple code for generating an adversarial pseudoprime runs extremely slowly taking over a minute on a M1 Mac. Even in Python it's basically instant. math.pow had to be replaced with bit shifts since I think the program just hung up and I had to kill it after 15 minutes. I also tried to put it in godbolt, but it just failed to compile with both 0.13 and trunk.

const std = @import("std");

pub fn main() !void {
    //const pow = std.math.pow;
    // const p1 = pow(u4279, 2, 1344) * 0x0000000000000000000000000000083DDA18EB04A7597CA3;
    var p1: u8192 = (1 << 1344) * 0x0000000000000000000000000000083DDA18EB04A7597CA3;
    p1 += (1 << 1152) * 0xC6BC877DF8A08EEC6725FA0832CBA270C42ADC358BC0CF50;
    p1 += (1 << 960) * 0xC82CB10F2733C3FB8875231FC1498A7B14CB675FAC1BF3C5;
    p1 += (1 << 768) * 0x127A76FC11E5D20E27940C95CEBA671FE1C4232250B74CBD;
    p1 += (1 << 576) * 0xF8448C90321513324C0681AFB4BA003353B1AFB0F1E8B91C;
    p1 += (1 << 384) * 0x60AF672A5A6F4D06DD0070A4BC74E425F3EAE90379E57754;
    p1 += (1 << 192) * 0x82D26E80E247464A4BB817DFCF7572F89F8B9CACD059B584;
    p1 += 0x0E4389C8AF84F6A6EA15A3EA5D62CB994B082731BA4CDE73;
    const n: u8192 = p1 * (1013 * (p1 - 1) + 1) * (2053 * (p1 - 1) + 1);

    std.debug.print("p1: {d}\n", .{p1});
    std.debug.print("n: {d}\n", .{n});
}

$ time zig run example.zig
...snip...

real    1m32.436s
user    1m31.264s
sys     0m0.394s

$ zig version
0.13.0

[nikic]

This is because LLVM does naive (quadratic) inline expansion of the multiplications. This is done because there used to be no agreement on the names of the necessary builtins with libgcc. However, it looks like libgcc has implemented them in the meantime: https://gcc.gnu.org/onlinedocs/gccint/Integer-library-routines.html#Bit-precise-integer-arithmetic-functions

So now this just needs implementation of __mulbitint3 and __divmodbitint4 in compiler-rt, and some adjustments to make LLVM lower to these libcalls.

Edit: Created an issue for the compiler-rt part: #126384