Line data Source code
1 : /* Low-half short product (quadratic and Mulders' algorithms).
2 :
3 : Copyright 2003, 2005, 2006 Paul Zimmermann, Alexander Kruppa, Dave Newman.
4 :
5 : This file is part of the ECM Library.
6 :
7 : The ECM Library is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU Lesser General Public License as published by
9 : the Free Software Foundation; either version 3 of the License, or (at your
10 : option) any later version.
11 :
12 : The ECM Library is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 : or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15 : License for more details.
16 :
17 : You should have received a copy of the GNU Lesser General Public License
18 : along with the ECM Library; see the file COPYING.LIB. If not, see
19 : http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
20 : 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
21 :
22 : #include "ecm-impl.h"
23 :
24 : /* puts in {rp, n} the low part of {np, n} times {mp, n}, i.e. equivalent to:
25 :
26 : mp_ptr tp;
27 : TMP_DECL(marker);
28 : TMP_MARK(marker);
29 : tp = TMP_ALLOC_LIMBS (2 * n);
30 : mpn_mul_n (tp, np, mp, n);
31 : MPN_COPY (rp, tp, n);
32 : TMP_FREE(marker);
33 : */
34 : void
35 208666594 : ecm_mul_lo_basecase (mp_ptr rp, mp_srcptr np, mp_srcptr mp, mp_size_t n)
36 : {
37 208666594 : mpn_mul_1 (rp, np, n, mp[0]);
38 1729101329 : for (; --n;)
39 1520434735 : mpn_addmul_1 (++rp, np, n, (++mp)[0]);
40 208666594 : }
41 :
42 : #ifdef MPN_MUL_LO_THRESHOLD_TABLE
43 : size_t mpn_mul_lo_threshold[MPN_MUL_LO_THRESHOLD] = MPN_MUL_LO_THRESHOLD_TABLE;
44 : #else
45 : size_t mpn_mul_lo_threshold[MPN_MUL_LO_THRESHOLD];
46 : #endif
47 :
48 :
49 : void
50 2795502719 : ecm_mul_lo_n (mp_ptr rp, mp_srcptr np, mp_srcptr mp, mp_size_t n)
51 : {
52 : mp_size_t k;
53 :
54 2795502719 : if (n < MPN_MUL_LO_THRESHOLD)
55 : {
56 2795502719 : switch (k = mpn_mul_lo_threshold[n])
57 : {
58 1783627208 : case 0:
59 : {
60 1783627208 : mpn_mul_n (rp, np, mp, n);
61 1783627208 : return;
62 : }
63 208666594 : case 1:
64 : {
65 208666594 : ecm_mul_lo_basecase (rp, np, mp, n);
66 208666594 : return;
67 : }
68 : /* else go through */
69 : }
70 : }
71 : else
72 0 : k = (mp_size_t) (0.75 * (double) n);
73 :
74 803208917 : mpn_mul_n (rp, np, mp, k);
75 803208917 : rp += k;
76 803208917 : n -= k;
77 803208917 : ecm_mul_lo_n (rp + n, np + k, mp, n);
78 803208917 : mpn_add_n (rp, rp, rp + n, n);
79 803208917 : ecm_mul_lo_n (rp + n, np, mp + k, n);
80 803208917 : mpn_add_n (rp, rp, rp + n, n);
81 : }
|