Hello, Zig Community! I am pretty new to the language and I am curious about one thing.
How does Zig handle multiplication? What algorithm does it use?
Does it use the long multiplication algorithm with the time complexity of O(n^2), or does it use the Karatsuba algorithm with the time complexity of roughly O(n^1.58)?
I’ve heard that the naive, long multiplication, approach is faster for smaller numbers, and the Karatsuba algorithm works better for larger numbers, but which one does Zig use?
It is not a very important or practical question for me, but I would appreciate any answer!
I think you can find stuff for Zigs std.math.big.int in the matching source code and for the builtin * operator I guess there are some things in compiler_rt.
Note that there is a difference for the standard * operator (with a max size of like u64 or u128 or whatever, idk) which may just be one assembly instruction (which will probably result in long multiplication for u64 as logic gate in the processor), but Zig implements its own mechanisms for big ints and in compiler_rt (though I don’t really get the point of compiler_rt when we already have x86_64 assembly instructions for multiplicaton, probably some kind of special multiplication…).
You can check on godbolt (I’m using C23 _BitInt() here because it’s a bit easier to show the resulting assembly compared to Zig - I’m sure that at least the LLVM backend of Zig will behave the same:
Basically, anything above 64 bits is split into a sequence of 64-bit mul and add, anything below 64 bits is a mul.
Integer arithmetic on fixed size integers above 128 bits is one area where Zig’s x86 backend currently outperforms LLVM backend. By like 100x in both compilation time and runtime performance.
Unfortunately it’s not hooked up to godbolt at the moment. Might be a nice PR to send them.
Godbolt works fine with the x86_64 backend if you enable the “Link to binary” option; this causes it to link the result and show you the disassembly of that binary. Without that option, it tries to use -femit-asm instead, which currently doesn’t work for the x86_64 backend. In other words, the problem here is on our end!
Here’s an example of the codegen for u512 arithmetic: Compiler Explorer
You can change the option -fno-llvm to -fllvm to see what LLVM emits.
