flint-sys 0.9.0

Bindings to the FLINT C library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

/*
    Copyright (C) 2009, 2016 William Hart

    This file is part of FLINT.

    FLINT is free software: you can redistribute it and/or modify it under
    the terms of the GNU Lesser General Public License (LGPL) as published
    by the Free Software Foundation; either version 3 of the License, or
    (at your option) any later version.  See <https://www.gnu.org/licenses/>.
*/

#include "test_helpers.h"
#include "ulong_extras.h"

TEST_FUNCTION_START(n_xgcd, state)
{
    int i, result;

    for (i = 0; i < 10000 * flint_test_multiplier(); i++)
    {
        ulong a, b, c, g, bits1, bits2, bits3, ph, pl, qh, ql;
        ulong s, t;

        bits1 = n_randint(state, FLINT_BITS - 1) + 2;
        bits2 = n_randint(state, bits1) + 1;
        bits3 =
            bits1 == FLINT_BITS ? 0 : n_randint(state, FLINT_BITS - bits1) + 1;

        do
        {
            a = n_randtest_bits(state, bits1);
            b = n_randtest_bits(state, bits2);
        } while (n_gcd(a, b) != UWORD(1) || b > a);

        c = bits3 == 0 ? 1 : n_randtest_bits(state, bits3);

        g = n_xgcd(&s, &t, a * c, b * c);

        /* s*ac + t*bc */
        umul_ppmm(ph, pl, a * c, s);
        umul_ppmm(qh, ql, b * c, t);
        sub_ddmmss(ph, pl, ph, pl, qh, ql);

        result = (s <= b * c || b * c == 0);
        if (!result)
            TEST_FUNCTION_FAIL(
                    "s >= b*c\n"
                    "a = %wu, b = %wu, c = %wu, g = %wu, s = %wu, t = %wu\n",
                    a, b, c, g, s, t);

        result = (t <= a * c || a * c == 0);
        if (!result)
            TEST_FUNCTION_FAIL(
                    "t >= a*c\n"
                    "a = %wu, b = %wu, c = %wu, g = %wu, s = %wu, t = %wu\n",
                    a, b, c, g, s, t);

        result = (g == c && ph == UWORD(0) && pl == c);
        if (!result)
            TEST_FUNCTION_FAIL(
                    "g != c or s*ac + t*bc != c\n"
                    "a = %wu, b = %wu, c = %wu, g = %wu, s = %wu, t = %wu\n",
                    a, b, c, g, s, t);
    }

    /* a = 0, b = 0 */
    {
        ulong g, s, t;

        g = n_xgcd(&s, &t, 0, 0);

        result = (g == 0 && s == 1 && t == 0);
        if (!result)
            TEST_FUNCTION_FAIL(
                    "Case a = 0, b = 0\n"
                    "g = %wu, s = %wu, t = %wu\n",
                    g, s, t);
    }

    /* b = 0 */
    {
        ulong a, g, s, t;

        a = n_randtest(state);

        g = n_xgcd(&s, &t, a, 0);

        result = (g == a && s == 1 && t == 0);
        if (!result)
            TEST_FUNCTION_FAIL(
                    "Case a = 0\n"
                    "a = %wu, g = %wu, s = %wu, t = %wu\n",
                    a, g, s, t);
    }

    TEST_FUNCTION_END(state);
}