Why is Julia the only one that doesn't overflow?

General Usage
, ,
1

I have the following tail recursive fibonacci function in zig, rust, julia and c. For some reason, only the Julia version doesn’t overflow. Why is that?

fn fib(n: usize, p1: usize, p2: usize) -> usize {
    if n < 2 {
        return p1 + p2;
    }
    return fib(n - 1, p1 + p2, p1);
}

fn main() {
    dbg!(fib(100, 1, 1));
}

const std = @import("std");

fn fib(n: usize, p1: usize, p2: usize) usize {
    if (n < 2) {
        return p1 + p2;
    }
    return fib(n - 1, p1 + p2, p1);
}

pub fn main() !void {
    std.debug.print("fib(100, 1, 1) = {d}", .{fib(100, 1, 1)});
}

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t fib(uint64_t n, uint64_t p1, uint64_t p2) {
    if (n < 2)
        return p1 + p2;
    return fib(n - 1, p1 + p2, p1);
}

int main() {
    printf("fib(100, 1, 1) = %" PRIu64 "\n", fib(100, 1, 1));
    return 0;
}


function fib(n::UInt64, p1::UInt64, p2::UInt64) ::UInt64
    if (n < 2)
        return p1 + p2
    end
    return fib(n - 1, p1 + p2, p1)
end

@show fib(UInt64(100), UInt64(1), UInt64(1))

And running all of them:

$ rustc -o fibrs fib.rs && ./fibrs

thread 'main' (10899) panicked at fib.rs:5:23:
attempt to add with overflow
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
$ zig build-exe --name fibz fib.zig && ./fibz
thread 10921 panic: integer overflow
...
$ gcc -o fibc fib.c && ./fibc
fib(100, 1, 1) = 101
$ julia fib.jl
fib(UInt64(100), UInt64(1), UInt64(1)) = 0x45e1a61e5624f888

Why does Julia not overflow? Am I missing something? I think my implementations are all the same. The actual code I’ve uploaded to my GitHub

Edit: I’m a dummy and my C code was buggy. Both julia and C overflow

2

It does overflow. It just doesn’t throw an error on overflow.

julia> 0xff * 0xff
0x01

In particular, let me rewrite your fib function to work for any integer type:

fib(n, p1, p2) = n < 2 ? p1 + p2 : fib(n - one(n), p1 + p2, p1)

(using one(n) to avoid accidentally using 1, which is an Int). Then we can compute the exact result using BigInt and compare to the UInt64 result:

julia> exact = fib(big(100), big(1), big(1))
927372692193078999176

julia> uint64 = fib(UInt64(100), UInt64(1), UInt64(1))
0x45e1a61e5624f888

julia> BigInt(uint64)
5035488507601418376

julia> uint64 == exact
false

and we see that the UInt64 calculation gave a different result due to overflow.

4 Likes
3

It seems like it does overflow anyway, but doesn’t tell you about it.

First, your C code has 2 bugs: you’re calling fib(n - 1, p1 + p2, 1) instead of fib(n - 1, p1 + p2, p1) and your format specifier %d is for ints. Apparently you need a different specifier: https://stackoverflow.com/a/9225648.

Putting this together, I get:

> cat fib.c
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t fib(uint64_t n, uint64_t p1, uint64_t p2) {
    if (n < 2)
        return p1 + p2;
    return fib(n - 1, p1 + p2, p1);
}

int main() {
    printf("fib(100, 1, 1) = %" PRIu64 "\n", fib(100, 1, 1));
    return 0;
}
> clang fib.c -o fib && ./fib
fib(100, 1, 1) = 5035488507601418376

Julia actually returns the same number:

>>> 0x45e1a61e5624f888
5035488507601418376

Using Python’s unbounded integers, we get the correct answer:

>>> def fib(n, p1, p2):
...     if n < 2: return p1 + p2
...     return fib(n-1, p1+p2, p1)
...     
>>> fib(100,1,1)
927372692193078999176
3 Likes
4

It is a feature of Julia. Relevant section of the manual:

I don’t know exactly the motivation of this feature, but I can imagine that since arithmetic operations on integers are everywhere in any program, not having to check overflow allows faster computations. If you want safe integers there is a very lightweight package that provides them:

2 Likes
5

Oops mystery solved. Tysm!

1 Like
6

Note also that Rust also allows overflow if you compile with the --release flag.

3 Likes