1 /* 2 Copyright (C) 2015 Fredrik Johansson 3 4 This file is part of Arb. 5 6 Arb is free software: you can redistribute it and/or modify it under 7 the terms of the GNU Lesser General Public License (LGPL) as published 8 by the Free Software Foundation; either version 2.1 of the License, or 9 (at your option) any later version. See <http://www.gnu.org/licenses/>. 10 */ 11 12 #include "acb_modular.h" 13 14 void acb_modular_fill_addseq(slong * tab,slong len)15acb_modular_fill_addseq(slong * tab, slong len) 16 { 17 slong i, j; 18 19 for (i = 2; i < len; i++) 20 { 21 if (tab[i] == -1) 22 { 23 /* prefer doubling (squaring) */ 24 if ((i % 2) == 0 && tab[i / 2] != 0) 25 { 26 tab[i] = i / 2; 27 } 28 else 29 { 30 /* check if it can be written as a sum */ 31 /* prefer unbalanced, because one power will have low precision */ 32 #if 1 33 for (j = 1; 2 * j <= i; j++) 34 #else 35 for (j = i / 2; j >= 1; j--) 36 #endif 37 { 38 if (tab[j] != 0 && tab[i-j] != 0) 39 { 40 tab[i] = j; 41 break; 42 } 43 } 44 45 /* extend and start over */ 46 if (tab[i] == -1) 47 { 48 tab[i] = i / 2; 49 50 if (tab[i / 2] == 0) 51 tab[i / 2] = -1; 52 53 if (tab[i - i / 2] == 0) 54 tab[i - i / 2] = -1; 55 56 i = 1; 57 } 58 } 59 } 60 } 61 62 /* prefer squaring (extra entries may have been inserted) */ 63 for (i = 2; i < len; i += 2) 64 { 65 if (tab[i] != 0 && tab[i] != i / 2) 66 { 67 if (tab[i / 2] != 0) 68 tab[i] = i / 2; 69 } 70 } 71 } 72 73