Hướng dẫn integer square root python

Inspired by all answers, decided to implement in pure C++ several best methods from these answers. As everybody knows C++ is always faster than Python.

To glue C++ and Python I used Cython. It allows to make out of C++ a Python module and then call C++ functions directly from Python functions.

Also as complementary I provided not only Python-adopted code, but pure C++ with tests too.

Here are timings from pure C++ tests:

Test           'GMP', bits     64, time  0.000001 sec
Test 'AndersKaseorg', bits     64, time  0.000003 sec
Test    'Babylonian', bits     64, time  0.000006 sec
Test  'ChordTangent', bits     64, time  0.000018 sec

Test           'GMP', bits  50000, time  0.000118 sec
Test 'AndersKaseorg', bits  50000, time  0.002777 sec
Test    'Babylonian', bits  50000, time  0.003062 sec
Test  'ChordTangent', bits  50000, time  0.009120 sec

and same C++ functions but as adopted Python module have timings:

Bits 50000
         math.isqrt:   2.819 ms
        gmpy2.isqrt:   0.166 ms
          ISqrt_GMP:   0.252 ms
ISqrt_AndersKaseorg:   3.338 ms
   ISqrt_Babylonian:   3.756 ms
 ISqrt_ChordTangent:  10.564 ms

My Cython-C++ is nice in a sence as a framework for those people who want to write and test his own C++ method from Python directly.

As you noticed in above timings as example I used following methods:

1. math.isqrt, implementation from standard library.

2. gmpy2.isqrt, GMPY2 library's implementation.

3. ISqrt_GMP - same as GMPY2, but using my Cython module, there I use C++ GMP library () directly.

4. ISqrt_AndersKaseorg, code taken from answer of @AndersKaseorg.

5. ISqrt_Babylonian, method taken from Wikipedia article, so-called Babylonian method. My own implementation as I understand it.

6. ISqrt_ChordTangent, it is my own method that I called Chord-Tangent, because it uses chord and tangent line to iteratively shorten interval of search. This method is described in moderate details in my other article. This method is nice because it searches not only square root, but also K-th root for any K. I drew a small picture showing details of this algorithm.

Regarding compiling C++/Cython code, I used GMP library. You need to install it first, under Linux it is easy through sudo apt install libgmp-dev.

Under Windows easiest is to install really great program VCPKG, this is software Package Manager, similar to APT in Linux. VCPKG compiles all packages from sources using Visual Studio (don't forget to install Community version of Visual Studio). After installing VCPKG you can install GMP by vcpkg install gmp. Also you may install MPIR, this is alternative fork of GMP, you can install it through vcpkg install mpir.

After GMP is installed under Windows please edit my Python code and replace path to include directory and library file. VCPKG at the end of installation should show you path to ZIP file with GMP library, there are .lib and .h files.

You may notice in Python code that I also designed special handy cython_compile() function that I use to compile any C++ code into Python module. This function is really good as it allows for you to easily plug-in any C++ code into Python, this can be reused many times.

If you have any questions or suggestions, or something doesn't work on your PC, please write in comments.

Below first I show code in Python, afterwards in C++. See Try it online! link above C++ code to run code online on GodBolt servers. Both code snippets I fully runnable from scratch as they are, nothing needs to be edited in them.

def cython_compile(srcs):
    import json, hashlib, os, glob, importlib, sys, shutil, tempfile
    srch = hashlib.sha256(json.dumps(srcs, sort_keys = True, ensure_ascii = True).encode('utf-8')).hexdigest().upper()[:12]
    pdir = 'cyimp'
    
    if len(glob.glob(f'{pdir}/cy{srch}*')) == 0:
        class ChDir:
            def __init__(self, newd):
                self.newd = newd
            def __enter__(self):
                self.curd = os.getcwd()
                os.chdir(self.newd)
                return self
            def __exit__(self, ext, exv, tb):
                os.chdir(self.curd)

        os.makedirs(pdir, exist_ok = True)
        with tempfile.TemporaryDirectory(dir = pdir) as td, ChDir(str(td)) as chd:
            os.makedirs(pdir, exist_ok = True)
                
            for k, v in srcs.items():
                with open(f'cys{srch}_{k}', 'wb') as f:
                    f.write(v.replace('{srch}', srch).encode('utf-8'))

            import numpy as np
            from setuptools import setup, Extension
            from Cython.Build import cythonize

            sys.argv += ['build_ext', '--inplace']
            setup(
                ext_modules = cythonize(
                    Extension(
                        f'{pdir}.cy{srch}', [f'cys{srch}_{k}' for k in filter(lambda e: e[e.rfind('.') + 1:] in ['pyx', 'c', 'cpp'], srcs.keys())],
                        depends = [f'cys{srch}_{k}' for k in filter(lambda e: e[e.rfind('.') + 1:] not in ['pyx', 'c', 'cpp'], srcs.keys())],
                        extra_compile_args = ['/O2', '/std:c++latest',
                            '/ID:/dev/_3party/vcpkg_bin/gmp/include/',
                        ],
                    ),
                    compiler_directives = {'language_level': 3, 'embedsignature': True},
                    annotate = True,
                ),
                include_dirs = [np.get_include()],
            )
            del sys.argv[-2:]
            for f in glob.glob(f'{pdir}/cy{srch}*'):
                shutil.copy(f, f'./../')

    print('Cython module:', f'cy{srch}')
    return importlib.import_module(f'{pdir}.cy{srch}')

def cython_import():
    srcs = {
        'lib.h': """
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 

#pragma comment(lib, "D:/dev/_3party/vcpkg_bin/gmp/lib/gmp.lib")

#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " + std::to_string(__LINE__) + "! Msg '" + std::string(msg) + "'."); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
#define LN { std::cout << "LN " << __LINE__ << std::endl; }

using u32 = uint32_t;
using u64 = uint64_t;

template 
size_t BitLen(T n) {
    if constexpr(std::is_same_v, mpz_class>)
        return mpz_sizeinbase(n.get_mpz_t(), 2);
    else {
        size_t cnt = 0;
        while (n >= (1ULL << 32)) {
            cnt += 32;
            n >>= 32;
        }
        while (n >= (1 << 8)) {
            cnt += 8;
            n >>= 8;
        }
        while (n) {
            ++cnt;
            n >>= 1;
        }
        return cnt;
    }
}

template 
T ISqrt_Babylonian(T const & y) {
    // https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
    if (y <= 1)
        return y;
    T x = T(1) << (BitLen(y) / 2), a = 0, b = 0, limit = 3;
    while (true) {
        size_t constexpr loops = 3;
        for (size_t i = 0; i < loops; ++i) {
            if (i + 1 >= loops)
                a = x;
            b = y;
            b /= x;
            x += b;
            x >>= 1;
        }
        if (b < a)
            std::swap(a, b);
        if (b - a > limit)
            continue;
        ++b;
        for (size_t i = 0; a <= b; ++a, ++i)
            if (a * a > y) {
                if (i == 0)
                    break;
                else
                    return a - 1;
            }
        ASSERT(false);
    }
}

template 
T ISqrt_AndersKaseorg(T const & n) {
    // https://stackoverflow.com/a/53983683/941531
    if (n > 0) {
        T y = 0, x = T(1) << ((BitLen(n) + 1) >> 1);
        while (true) {
            y = (x + n / x) >> 1;
            if (y >= x)
                return x;
            x = y;
        }
    } else if (n == 0)
        return 0;
    else
        ASSERT_MSG(false, "square root not defined for negative numbers");
}

template 
T ISqrt_GMP(T const & y) {
    // https://gmplib.org/manual/Integer-Roots
    mpz_class r, n;
    bool constexpr is_mpz = std::is_same_v, mpz_class>;
    if constexpr(is_mpz)
        n = y;
    else {
        static_assert(sizeof(T) <= 8);
        n = u32(y >> 32);
        n <<= 32;
        n |= u32(y);
    }
    mpz_sqrt(r.get_mpz_t(), n.get_mpz_t());
    if constexpr(is_mpz)
        return r;
    else
        return (u64(mpz_get_ui(mpz_class(r >> 32).get_mpz_t())) << 32) | u64(mpz_get_ui(mpz_class(r & u32(-1)).get_mpz_t()));
}

template 
T KthRoot_ChordTangent(T const & n, size_t k = 2) {
    // https://i.stack.imgur.com/et9O0.jpg
    if (n <= 1)
        return n;
    auto KthPow = [&](auto const & x){
        T y = x * x;
        for (size_t i = 2; i < k; ++i)
            y *= x;
        return y;
    };
    auto KthPowDer = [&](auto const & x){
        T y = x * u32(k);
        for (size_t i = 1; i + 1 < k; ++i)
            y *= x;
        return y;
    };
    size_t root_bit_len = (BitLen(n) + k - 1) / k;
    T   hi = T(1) << root_bit_len,
        x_begin = hi >> 1, x_end = hi,
        y_begin = KthPow(x_begin), y_end = KthPow(x_end),
        x_mid = 0, y_mid = 0, x_n = 0, y_n = 0, tangent_x = 0, chord_x = 0;
    for (size_t icycle = 0; icycle < (1 << 30); ++icycle) {
        if (x_end <= x_begin + 2)
            break;
        if constexpr(0) { // Do Binary Search step if needed
            x_mid = (x_begin + x_end) >> 1;
            y_mid = KthPow(x_mid);
            if (y_mid > n) {
                x_end = x_mid; y_end = y_mid;
            } else {
                x_begin = x_mid; y_begin = y_mid;
            }
        }
        // (y_end - y_begin) / (x_end - x_begin) = (n - y_begin) / (x_n - x_begin) ->
        x_n = x_begin + (n - y_begin) * (x_end - x_begin) / (y_end - y_begin);
        y_n = KthPow(x_n);
        tangent_x = x_n + (n - y_n) / KthPowDer(x_n) + 1;
        chord_x = x_n + (n - y_n) * (x_end - x_n) / (y_end - y_n);
        //ASSERT(chord_x <= tangent_x);
        x_begin = chord_x; x_end = tangent_x;
        y_begin = KthPow(x_begin); y_end = KthPow(x_end);
        //ASSERT(y_begin <= n);
        //ASSERT(y_end > n);
    }
    for (size_t i = 0; x_begin <= x_end; ++x_begin, ++i)
        if (x_begin * x_begin > n) {
            if (i == 0)
                break;
            else
                return x_begin - 1;
        }
    ASSERT(false);
    return 0;
}

mpz_class FromLimbs(uint64_t * limbs, uint64_t * cnt) {
    mpz_class r;
    mpz_import(r.get_mpz_t(), *cnt, -1, 8, -1, 0, limbs);
    return r;
}

void ToLimbs(mpz_class const & n, uint64_t * limbs, uint64_t * cnt) {
    uint64_t cnt_before = *cnt;
    size_t cnt_res = 0;
    mpz_export(limbs, &cnt_res, -1, 8, -1, 0, n.get_mpz_t());
    ASSERT(cnt_res <= cnt_before);
    std::memset(limbs + cnt_res, 0, (cnt_before - cnt_res) * 8);
    *cnt = cnt_res;
}

void ISqrt_GMP_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(ISqrt_GMP(FromLimbs(limbs, cnt)), limbs, cnt);
}

void ISqrt_AndersKaseorg_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(ISqrt_AndersKaseorg(FromLimbs(limbs, cnt)), limbs, cnt);
}

void ISqrt_Babylonian_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(ISqrt_Babylonian(FromLimbs(limbs, cnt)), limbs, cnt);
}

void ISqrt_ChordTangent_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(KthRoot_ChordTangent(FromLimbs(limbs, cnt), 2), limbs, cnt);
}
        """,
        'main.pyx': r"""
# distutils: language = c++
# distutils: define_macros=NPY_NO_DEPRECATED_API=NPY_1_7_API_VERSION

import numpy as np
cimport numpy as np
cimport cython
from libc.stdint cimport *

cdef extern from "cys{srch}_lib.h" nogil:
    void ISqrt_ChordTangent_Py(uint64_t * limbs, uint64_t * cnt);
    void ISqrt_GMP_Py(uint64_t * limbs, uint64_t * cnt);
    void ISqrt_AndersKaseorg_Py(uint64_t * limbs, uint64_t * cnt);
    void ISqrt_Babylonian_Py(uint64_t * limbs, uint64_t * cnt);

@cython.boundscheck(False)
@cython.wraparound(False)
def ISqrt(method, n):
    mask64 = (1 << 64) - 1
    def ToLimbs():
        return np.copy(np.frombuffer(n.to_bytes((n.bit_length() + 63) // 64 * 8, 'little'), dtype = np.uint64))
        
        words = (n.bit_length() + 63) // 64
        t = n
        r = np.zeros((words,), dtype = np.uint64)
        for i in range(words):
            r[i] = np.uint64(t & mask64)
            t >>= 64
        return r
    def FromLimbs(x):
        return int.from_bytes(x.tobytes(), 'little')
        
        n = 0
        for i in range(x.shape[0]):
            n |= int(x[i]) << (i * 64)
        return n
    n = ToLimbs()
    cdef uint64_t[:] cn = n
    cdef uint64_t ccnt = len(n)
    cdef uint64_t cmethod = {'GMP': 0, 'AndersKaseorg': 1, 'Babylonian': 2, 'ChordTangent': 3}[method]
    with nogil:
        (ISqrt_GMP_Py if cmethod == 0 else ISqrt_AndersKaseorg_Py if cmethod == 1 else ISqrt_Babylonian_Py if cmethod == 2 else ISqrt_ChordTangent_Py)(
            &cn[0], &ccnt
        )
    return FromLimbs(n[:ccnt])
        """,
    }
    return cython_compile(srcs)

def main():
    import math, gmpy2, timeit, random
    mod = cython_import()
    fs = [
        ('math.isqrt', math.isqrt),
        ('gmpy2.isqrt', gmpy2.isqrt),
        ('ISqrt_GMP', lambda n: mod.ISqrt('GMP', n)),
        ('ISqrt_AndersKaseorg', lambda n: mod.ISqrt('AndersKaseorg', n)),
        ('ISqrt_Babylonian', lambda n: mod.ISqrt('Babylonian', n)),
        ('ISqrt_ChordTangent', lambda n: mod.ISqrt('ChordTangent', n)),
    ]
    times = [0] * len(fs)
    ntests = 1 << 6
    bits = 50000
    for i in range(ntests):
        n = random.randrange(1 << (bits - 1), 1 << bits)
        ref = None
        for j, (fn, f) in enumerate(fs):
            timeit_cnt = 3
            tim = timeit.timeit(lambda: f(n), number = timeit_cnt) / timeit_cnt
            times[j] += tim
            x = f(n)
            if j == 0:
                ref = x
            else:
                assert x == ref, (fn, ref, x)
    print('Bits', bits)
    print('\n'.join([f'{fs[i][0]:>19}: {round(times[i] / ntests * 1000, 3):>7} ms' for i in range(len(fs))]))

if __name__ == '__main__':
    main()

and C++:

Try it online!

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 

#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " + std::to_string(__LINE__) + "! Msg '" + std::string(msg) + "'."); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
#define LN { std::cout << "LN " << __LINE__ << std::endl; }

using u32 = uint32_t;
using u64 = uint64_t;

template 
size_t BitLen(T n) {
    if constexpr(std::is_same_v, mpz_class>)
        return mpz_sizeinbase(n.get_mpz_t(), 2);
    else {
        size_t cnt = 0;
        while (n >= (1ULL << 32)) {
            cnt += 32;
            n >>= 32;
        }
        while (n >= (1 << 8)) {
            cnt += 8;
            n >>= 8;
        }
        while (n) {
            ++cnt;
            n >>= 1;
        }
        return cnt;
    }
}

template 
T ISqrt_Babylonian(T const & y) {
    // https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
    if (y <= 1)
        return y;
    T x = T(1) << (BitLen(y) / 2), a = 0, b = 0, limit = 3;
    while (true) {
        size_t constexpr loops = 3;
        for (size_t i = 0; i < loops; ++i) {
            if (i + 1 >= loops)
                a = x;
            b = y;
            b /= x;
            x += b;
            x >>= 1;
        }
        if (b < a)
            std::swap(a, b);
        if (b - a > limit)
            continue;
        ++b;
        for (size_t i = 0; a <= b; ++a, ++i)
            if (a * a > y) {
                if (i == 0)
                    break;
                else
                    return a - 1;
            }
        ASSERT(false);
    }
}

template 
T ISqrt_AndersKaseorg(T const & n) {
    // https://stackoverflow.com/a/53983683/941531
    if (n > 0) {
        T y = 0, x = T(1) << ((BitLen(n) + 1) >> 1);
        while (true) {
            y = (x + n / x) >> 1;
            if (y >= x)
                return x;
            x = y;
        }
    } else if (n == 0)
        return 0;
    else
        ASSERT_MSG(false, "square root not defined for negative numbers");
}

template 
T ISqrt_GMP(T const & y) {
    // https://gmplib.org/manual/Integer-Roots
    mpz_class r, n;
    bool constexpr is_mpz = std::is_same_v, mpz_class>;
    if constexpr(is_mpz)
        n = y;
    else {
        static_assert(sizeof(T) <= 8);
        n = u32(y >> 32);
        n <<= 32;
        n |= u32(y);
    }
    mpz_sqrt(r.get_mpz_t(), n.get_mpz_t());
    if constexpr(is_mpz)
        return r;
    else
        return (u64(mpz_get_ui(mpz_class(r >> 32).get_mpz_t())) << 32) | u64(mpz_get_ui(mpz_class(r & u32(-1)).get_mpz_t()));
}

template 
std::string IntToStr(T n) {
    if constexpr(std::is_same_v, mpz_class>)
        return n.get_str();
    else {
        std::ostringstream ss;
        ss << n;
        return ss.str();
    }
}

template 
T KthRoot_ChordTangent(T const & n, size_t k = 2) {
    // https://i.stack.imgur.com/et9O0.jpg
    if (n <= 1)
        return n;
    auto KthPow = [&](auto const & x){
        T y = x * x;
        for (size_t i = 2; i < k; ++i)
            y *= x;
        return y;
    };
    auto KthPowDer = [&](auto const & x){
        T y = x * u32(k);
        for (size_t i = 1; i + 1 < k; ++i)
            y *= x;
        return y;
    };
    size_t root_bit_len = (BitLen(n) + k - 1) / k;
    T   hi = T(1) << root_bit_len,
        x_begin = hi >> 1, x_end = hi,
        y_begin = KthPow(x_begin), y_end = KthPow(x_end),
        x_mid = 0, y_mid = 0, x_n = 0, y_n = 0, tangent_x = 0, chord_x = 0;
    for (size_t icycle = 0; icycle < (1 << 30); ++icycle) {
        //std::cout << "x_begin, x_end = " << IntToStr(x_begin) << ", " << IntToStr(x_end) << ", n " << IntToStr(n) << std::endl;
        if (x_end <= x_begin + 2)
            break;
        if constexpr(0) { // Do Binary Search step if needed
            x_mid = (x_begin + x_end) >> 1;
            y_mid = KthPow(x_mid);
            if (y_mid > n) {
                x_end = x_mid; y_end = y_mid;
            } else {
                x_begin = x_mid; y_begin = y_mid;
            }
        }
        // (y_end - y_begin) / (x_end - x_begin) = (n - y_begin) / (x_n - x_begin) ->
        x_n = x_begin + (n - y_begin) * (x_end - x_begin) / (y_end - y_begin);
        y_n = KthPow(x_n);
        tangent_x = x_n + (n - y_n) / KthPowDer(x_n) + 1;
        chord_x = x_n + (n - y_n) * (x_end - x_n) / (y_end - y_n);
        //ASSERT(chord_x <= tangent_x);
        x_begin = chord_x; x_end = tangent_x;
        y_begin = KthPow(x_begin); y_end = KthPow(x_end);
        //ASSERT(y_begin <= n);
        //ASSERT(y_end > n);
    }
    for (size_t i = 0; x_begin <= x_end; ++x_begin, ++i)
        if (x_begin * x_begin > n) {
            if (i == 0)
                break;
            else
                return x_begin - 1;
        }
    ASSERT(false);
    return 0;
}

mpz_class FromLimbs(uint64_t * limbs, uint64_t * cnt) {
    mpz_class r;
    mpz_import(r.get_mpz_t(), *cnt, -1, 8, -1, 0, limbs);
    return r;
}

void ToLimbs(mpz_class const & n, uint64_t * limbs, uint64_t * cnt) {
    uint64_t cnt_before = *cnt;
    size_t cnt_res = 0;
    mpz_export(limbs, &cnt_res, -1, 8, -1, 0, n.get_mpz_t());
    ASSERT(cnt_res <= cnt_before);
    std::memset(limbs + cnt_res, 0, (cnt_before - cnt_res) * 8);
    *cnt = cnt_res;
}

void ISqrt_ChordTangent_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(KthRoot_ChordTangent(FromLimbs(limbs, cnt), 2), limbs, cnt);
}

void ISqrt_GMP_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(ISqrt_GMP(FromLimbs(limbs, cnt)), limbs, cnt);
}

void ISqrt_AndersKaseorg_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(ISqrt_AndersKaseorg(FromLimbs(limbs, cnt)), limbs, cnt);
}

void ISqrt_Babylonian_Py(uint64_t * limbs, uint64_t * cnt) {
    ToLimbs(ISqrt_Babylonian(FromLimbs(limbs, cnt)), limbs, cnt);
}

// Testing

#include 
#include 
#include 
#include 

inline double Time() {
    static auto const gtb = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast>(std::chrono::high_resolution_clock::now() - gtb)
        .count();
}

template 
std::vector Test0(std::string const & test_name, size_t bits, size_t ntests, F && f) {
    std::mt19937_64 rng{123};
    std::vector nums;
    for (size_t i = 0; i < ntests; ++i) {
        T n = 0;
        for (size_t j = 0; j < bits; j += 32) {
            size_t const cbits = std::min(32, bits - j);
            n <<= cbits;
            n ^= u32(rng()) >> (32 - cbits);
        }
        nums.push_back(n);
    }
    auto tim = Time();
    for (auto & n: nums)
        n = f(n);
    tim = Time() - tim;
    std::cout << "Test " << std::setw(15) << ("'" + test_name + "'")
        << ", bits " << std::setw(6) << bits << ", time "
        << std::fixed << std::setprecision(6) << std::setw(9) << tim / ntests << " sec" << std::endl;
    return nums;
}

void Test() {
    auto f = [](auto ty, size_t bits, size_t ntests){
        using T = std::decay_t;
        auto tim = Time();
        auto a = Test0("GMP",           bits, ntests, [](auto const & x){ return ISqrt_GMP(x); });
        auto b = Test0("AndersKaseorg", bits, ntests, [](auto const & x){ return ISqrt_AndersKaseorg(x); });
        ASSERT(b == a);
        auto c = Test0("Babylonian",    bits, ntests, [](auto const & x){ return ISqrt_Babylonian(x); });
        ASSERT(c == a);
        auto d = Test0("ChordTangent",  bits, ntests, [](auto const & x){ return KthRoot_ChordTangent(x); });
        ASSERT(d == a);
        std::cout << "Bits " << bits << " nums " << ntests << " time " << std::fixed << std::setprecision(1) << (Time() - tim) << " sec" << std::endl;
    };
    for (auto p: std::vector>{{15, 1 << 19}, {30, 1 << 19}})
        f(u64(), p.first, p.second);
    for (auto p: std::vector>{{64, 1 << 15}, {8192, 1 << 10}, {50000, 1 << 5}})
        f(mpz_class(), p.first, p.second);
}

int main() {
    try {
        Test();
        return 0;
    } catch (std::exception const & ex) {
        std::cout << "Exception: " << ex.what() << std::endl;
        return -1;
    }
}