OutOfMemoryError() when calculating Fibonacci numbers of the order of 10^20 using the `fibonaccinum` function

jriveraa · February 11, 2022, 8:24pm

Using the fibonaccinum function of the Combinatorics library - installed in its latest version - on an HPC using a Linux distribution, I get an OutOfMemoryError().
The code is:

using Combinatorics
fibonaccinum(BigInt(10)^18)

The function, whose code is available in its GitHub repository, is defined as:

function fibonaccinum(n::Integer)
    if n < 0
        throw(DomainError(n, "n must be nonnegative"))
    end
    z = Ref{BigInt}(0)
    ccall((:__gmpz_fib_ui, :libgmp), Cvoid, (Ref{BigInt}, UInt), z, UInt(n))
    return z[]
end

However, when I run exactly the same code on a computer using Windows the problem disappears and it is able to run. To check that it was not related to my computer, I tried it on other computers also running Windows - reinstalling Julia - and got no problem. I wonder if the problem lies in how Windows manages memory and not in the program itself. As far as I know, Windows uses “tree” data management while Linux uses a linked list. Anyway, I would appreciate any kind of indication on how to solve the problem.

Edit: It is related to this discussion.

Oscar_Smith · February 11, 2022, 8:39pm

Storing the result would take over 700 petabytes of ram. This doesn’t error on windows, because windows bigints have 32 bit length, so you are sing the computation overflow a bigint.

jriveraa · February 11, 2022, 8:43pm

Thank you for your answer, but how can I fix it? By defining another data type for the result?

Oscar_Smith · February 11, 2022, 8:45pm

You can’t. The number is just too big to store all the digits of.

jriveraa · February 11, 2022, 8:47pm

And couldn’t the memory in Linux be configured similarly to Windows to avoid the error?

Oscar_Smith · February 11, 2022, 8:55pm

Windows isn’t avoiding the error. It just isn’t telling you that it ran into an error.

jriveraa · February 11, 2022, 8:58pm

So it is not performing the calculations correctly? Is there a way to calculate the Fibonacci for such large numbers?

jling · February 11, 2022, 9:03pm

No, come back in 100 years maybe /jk

Oscar_Smith · February 11, 2022, 9:13pm

The biggest numbers computers can store are around 2^(2^40) (2^(2^35) is 4GB, 2^(2^45) is 4TB). fib(10^18) is approximately 1.61^(10^18) ≈ 2^(2^60)

nilshg · February 11, 2022, 9:34pm

WolframAlpha tells me that fib(10^15) is

2.4226142638072665895512781785852365306378154520893 × 10^208987640249978

What do you want to do with the result OP?

jriveraa · February 12, 2022, 1:44pm

I want to check if a condition is satisfied in a larger program, but I need to get the Fibonacci to start the program. It is not necessary to print the number on the screen.

stevengj · February 12, 2022, 2:11pm

It doesn’t matter whether you want to print the number. You can’t even store all of the digits in memory. You really need to re-think what you are trying to do.

If you only need to compute the Fibonacci number approximately, then maybe you can compute the log of the Fibonacci number instead and work with that. A good approximation of this, for large n, can be found using Binet’s formula. The following should be fast and accurate to double precision for all n:

using Combinatorics
logfib(n) = n < 40 ? log(fibonaccinum(n)) : n * log(MathConstants.golden) - 0.5log(5)

e.g.

julia> logfib(10^15)
4.812118250596027e14

julia> logfib(1e100)
4.812118250596035e99

jriveraa · February 12, 2022, 2:22pm

Thank you very much for your comments. However, I need the exact value of the Fibonacci. We need it because it is the first step in verifying a condition - specifically, the one that is proposed by a conjecture. I am working with really very powerful computers, with a power of 13.9 Petaflops. Is there really no way to accumulate these values? Maybe by converting it to a file and working with it? Sorry, but this is my first time working with such “monstrous” numbers.

lawless-m · February 12, 2022, 2:32pm

Just install over 700 petabytes of ram - problem solved

Oscar_Smith · February 12, 2022, 2:35pm

for about 23 million dollars, you could buy enough hard drives to sure the number. (although you would also need another couple 10s of millions of dollars for for the drives to store the intermediate computations)

cjdoris · February 12, 2022, 2:51pm

Can you say what the conjecture is, or what you need to do with the number?

For example if it is sufficient to compute it modulo a bunch of large primes, so that one can (in principle) recover the number using the Chinese Remainder Theorem, then I think it is doable on a machine that big.

I think it’s unlikely you can compute the whole number explicitly though.

jriveraa · February 12, 2022, 4:24pm

A bit silly of me, the truth is that I had not realized how Fibonacci can grow to such vertiginous limits. Of course, each iteration supposes to increase one bit so … Well, thanks for the idea - I’ll talk to funding /jk

Palli · February 13, 2022, 5:45pm

I realize your joking, but that wouldn’t solve your problem in practice (only in theory). To put the number in perspective:

Even if you could install than much RAM (you can’t), then scanning that much memory (even once) would take 178 days (by one CPU, so you need many, and a cluster and/or a grid), assuming 819.2 GB/s for HBM3 memory, and much longer for commodity memory, but actually you would be working on network speed not RAM speed.

I couldn’t immediate see how much flash RAM or flash memory is manufactured per year, what you would need, so just buying it or waiting for it to be manufactured in nontrivial.

64-bit CPUs might seem like they can address enough memory, but they can’t address that much, not 2^64. RISC-V has 128-bit defined, but I’m not sure yet manufactured, and I ignore that as I think addressing may be similar for that and their 64-bit RISC-V and other CPUs.

“Current AMD64 processors support a physical address space of up to 2^48 bytes of RAM, or 256 TiB.[18] However, as of 2020, there were no known x86-64 motherboards that support 256 TiB of RAM”

I’m not sure how much memory you can install, I have 128 GB in my desktop (and 512 GB in some server I ran years back). But you need to be able to address all of the memory, and that’s a problem, or avoid that issue in (parallel/MPI) software, slowing down even more.

“Intel has implemented a scheme with a 5-level page table, which allows Intel 64 processors to support a 57-bit virtual address space”

That’s only 128 PB you can address, so a single computer is not enough. You need a cluster of 4 such large computers, or more smaller, likely a grid. So you will be working at network speed.

I’m not sure if something changed with (what I just discovered) regarding addressing:

“In 2020, through a cross-vendor collaboration, a few microarchitecture levels were defined, x86-64-v2, x86-64-v3 and x86-64-v4.[38]”

Fugaku, the most powerful supercomputer has:

“1.6 TB NVMe SSD/16 nodes (L1)
150 PB shared Lustre FS (L2)[1]
Cloud storage services (L3)”

so you need 4 such, ignoring the cloud capabilities, working of much slower disks. Or a gird of ordinary (desktop) computers.

I’m not sure what’s the capacity of BOINC the largest grid (in RAM or storage). But assuming a generous 128 GB RAM (and not using the disks) you only need a grid of 408.000 such computers desktop computers.

IBM mainframes had the most memory (in a single address space), last time I checked, and claimed recently (before Apple M1) fastest CPUs for single-threaded and multi-threaded (maybe not floating-point, also not relevant here), and for z15:

the “L4 Cache increased from 672MB to 960MB, or +43%” with the new add-on chip System Controller (SC) SCM. Both it and all levels of cache in the main processor from level 1 use eDRAM, instead of the traditionally used SRAM. “A five-CPC drawer system has 4800 MB (5 x 960 MB) of shared L4 cache.”

The L4 cache is tiny (for this) so ineffective. As I wrote, you’ll be running at RAM speed, at best.