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)15 acb_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