Multiplying very large Naturals panics

[redshirtrob]

I ran into this while porting an LLL library to Malachite. I'm not sure if it's expected or not. Here's the snippet of code that panics:

Natural::ONE.shl(100_000) * Natural::ONE.shl(100_000);

Here's the stacktrace:

thread 'blah::test::test_natural' panicked at 'assertion failed: `(left == right)`
  left: `1`,
 right: `0`', external/raze__malachite_nz__0_4_1/src/natural/arithmetic/mul/fft.rs:2297:13
stack backtrace:
   0: rust_begin_unwind
             at /rustc/90c541806f23a127002de5b4038be731ba1458ca/library/std/src/panicking.rs:578:5
   1: core::panicking::panic_fmt
             at /rustc/90c541806f23a127002de5b4038be731ba1458ca/library/core/src/panicking.rs:67:14
   2: core::panicking::assert_failed_inner
   3: core::panicking::assert_failed
   4: malachite_nz::natural::arithmetic::mul::fft::limbs_mul_greater_to_out_fft_with_cutoff
   5: malachite_nz::natural::arithmetic::mul::limbs_mul_same_length_to_out
   6: malachite_nz::natural::arithmetic::mul::limbs_mul_greater_to_out
   7: malachite_nz::natural::arithmetic::mul::limbs_mul_greater
   8: malachite_nz::natural::arithmetic::mul::<impl core::ops::arith::MulAssign for malachite_nz::natural::Natural>::mul_assign
   9: paranoid::rsa::test::test_natural
  10: core::ops::function::FnOnce::call_once
  11: core::ops::function::FnOnce::call_once
             at /rustc/90c541806f23a127002de5b4038be731ba1458ca/library/core/src/ops/function.rs:250:5

I took a quick look, but the fft code is beyond my ability to comprehend right now. This isn't a big deal for me. I mostly raise it because Malachite is a fantastic library.

I'd completely understand if this is expected behavior or a "won't fix" as multiplying two 100k bit numbers feels a bit ridiculous.

[mhogrefe]

Thanks for catching this! Malachite should absolutely be able to handle Naturals of this size. I would only expect problems when the number of bits reaches the billions, and memory allocation starts to fail.

The FFT code is indeed very convoluted, no pun intended. I did some print-debugging comparisons with the FLINT code that it's based on, and it turns out FLINT and Malachite were using different FFT tuning tables. These influence the recursion strategy that the FFT code uses, and the bad table led to the assumption violation that you saw. I've made the fix and will release a new version of Malachite in a few days.

I'll have to see if this impacts performance negatively, but of course correctness is more important.

[redshirtrob]

Awesome! Glad you were able to fix it so quickly.

FWIW, I just tested against Integer and I see the same issue. I'm guessing your fix will cover that as well, but though I'd mention it just in case.

[mhogrefe]

Yes, Integer mostly just delegates to Natural. I've added a test case for Integer too just for the sake of completeness.

[mhogrefe]

Fixed in 0.4.3.

The tuning tables were a red herring: the real issue was that I thought I had proved that a certain carry was no greater than 1, but I was mistaken, and sometimes it's greater than 1. That's handled correctly now. I have tested 2^n * 2^n for n up to 1,000,000, and it works correctly.

[mhogrefe]

Sorry, v0.4.3 had some wrong dependencies. Please use v0.4.4 instead.

[redshirtrob]

This is awesome to hear! Thank you so much!