1/* Implementation of the algorithm for Toom-Cook 4.5-way. 2 3 Contributed to the GNU project by Marco Bodrato. 4 5 THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE. IT IS ONLY 6 SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST 7 GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE. 8 9Copyright 2009, 2012 Free Software Foundation, Inc. 10 11This file is part of the GNU MP Library. 12 13The GNU MP Library is free software; you can redistribute it and/or modify 14it under the terms of either: 15 16 * the GNU Lesser General Public License as published by the Free 17 Software Foundation; either version 3 of the License, or (at your 18 option) any later version. 19 20or 21 22 * the GNU General Public License as published by the Free Software 23 Foundation; either version 2 of the License, or (at your option) any 24 later version. 25 26or both in parallel, as here. 27 28The GNU MP Library is distributed in the hope that it will be useful, but 29WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 30or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 31for more details. 32 33You should have received copies of the GNU General Public License and the 34GNU Lesser General Public License along with the GNU MP Library. If not, 35see https://www.gnu.org/licenses/. */ 36 37#include "gmp-impl.h" 38 39 40/* Toom-4.5, the splitting 5x4 unbalanced version. 41 Evaluate in: infinity, +4, -4, +2, -2, +1, -1, 0. 42 43 <--s-><--n--><--n--><--n--><--n--> 44 ____ ______ ______ ______ ______ 45 |_a4_|__a3__|__a2__|__a1__|__a0__| 46 |b3_|__b2__|__b1__|__b0__| 47 <-t-><--n--><--n--><--n--> 48 49*/ 50#define TOOM_54_MUL_N_REC(p, a, b, n, ws) \ 51 do { mpn_mul_n (p, a, b, n); \ 52 } while (0) 53 54#define TOOM_54_MUL_REC(p, a, na, b, nb, ws) \ 55 do { mpn_mul (p, a, na, b, nb); \ 56 } while (0) 57 58void 59mpn_toom54_mul (mp_ptr pp, 60 mp_srcptr ap, mp_size_t an, 61 mp_srcptr bp, mp_size_t bn, mp_ptr scratch) 62{ 63 mp_size_t n, s, t; 64 int sign; 65 66 /***************************** decomposition *******************************/ 67#define a4 (ap + 4 * n) 68#define b3 (bp + 3 * n) 69 70 ASSERT (an >= bn); 71 n = 1 + (4 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) / (size_t) 4); 72 73 s = an - 4 * n; 74 t = bn - 3 * n; 75 76 ASSERT (0 < s && s <= n); 77 ASSERT (0 < t && t <= n); 78 /* Required by mpn_toom_interpolate_8pts. */ 79 ASSERT ( s + t >= n ); 80 ASSERT ( s + t > 4); 81 ASSERT ( n > 2); 82 83#define r8 pp /* 2n */ 84#define r7 scratch /* 3n+1 */ 85#define r5 (pp + 3*n) /* 3n+1 */ 86#define v0 (pp + 3*n) /* n+1 */ 87#define v1 (pp + 4*n+1) /* n+1 */ 88#define v2 (pp + 5*n+2) /* n+1 */ 89#define v3 (pp + 6*n+3) /* n+1 */ 90#define r3 (scratch + 3 * n + 1) /* 3n+1 */ 91#define r1 (pp + 7*n) /* s+t <= 2*n */ 92#define ws (scratch + 6 * n + 2) /* ??? */ 93 94 /* Alloc also 3n+1 limbs for ws... mpn_toom_interpolate_8pts may 95 need all of them, when DO_mpn_sublsh_n usea a scratch */ 96 /********************** evaluation and recursive calls *********************/ 97 /* $\pm4$ */ 98 sign = mpn_toom_eval_pm2exp (v2, v0, 4, ap, n, s, 2, pp) 99 ^ mpn_toom_eval_pm2exp (v3, v1, 3, bp, n, t, 2, pp); 100 TOOM_54_MUL_N_REC(pp, v0, v1, n + 1, ws); /* A(-4)*B(-4) */ 101 TOOM_54_MUL_N_REC(r3, v2, v3, n + 1, ws); /* A(+4)*B(+4) */ 102 mpn_toom_couple_handling (r3, 2*n+1, pp, sign, n, 2, 4); 103 104 /* $\pm1$ */ 105 sign = mpn_toom_eval_pm1 (v2, v0, 4, ap, n, s, pp) 106 ^ mpn_toom_eval_dgr3_pm1 (v3, v1, bp, n, t, pp); 107 TOOM_54_MUL_N_REC(pp, v0, v1, n + 1, ws); /* A(-1)*B(-1) */ 108 TOOM_54_MUL_N_REC(r7, v2, v3, n + 1, ws); /* A(1)*B(1) */ 109 mpn_toom_couple_handling (r7, 2*n+1, pp, sign, n, 0, 0); 110 111 /* $\pm2$ */ 112 sign = mpn_toom_eval_pm2 (v2, v0, 4, ap, n, s, pp) 113 ^ mpn_toom_eval_dgr3_pm2 (v3, v1, bp, n, t, pp); 114 TOOM_54_MUL_N_REC(pp, v0, v1, n + 1, ws); /* A(-2)*B(-2) */ 115 TOOM_54_MUL_N_REC(r5, v2, v3, n + 1, ws); /* A(+2)*B(+2) */ 116 mpn_toom_couple_handling (r5, 2*n+1, pp, sign, n, 1, 2); 117 118 /* A(0)*B(0) */ 119 TOOM_54_MUL_N_REC(pp, ap, bp, n, ws); 120 121 /* Infinity */ 122 if (s > t) { 123 TOOM_54_MUL_REC(r1, a4, s, b3, t, ws); 124 } else { 125 TOOM_54_MUL_REC(r1, b3, t, a4, s, ws); 126 }; 127 128 mpn_toom_interpolate_8pts (pp, n, r3, r7, s + t, ws); 129 130#undef a4 131#undef b3 132#undef r1 133#undef r3 134#undef r5 135#undef v0 136#undef v1 137#undef v2 138#undef v3 139#undef r7 140#undef r8 141#undef ws 142} 143