Strassen peeling strategy

[fredrik-johansson]

Currently, if $n$ is odd, Strassen multiplication recurses with a block size of $(n-1)/2$ and then does some rank-1 corrections. When we recurse many times, the rank-1 updates may have to be applied at each level for unfavorable $n$ (i.e. with many trailing ones in the binary representation).

An alternative would be to write $n = b 2^d + r$ at the top level where $b$ is a chosen basecase block size, so that all Strassen blocks down from $n' = b 2^d$ split exactly. One then computes a rank $r$ correction.

Empirically, this always uses >= as many arithmetic operations as the current strategy (is there a nice proof of this?), usually by a very small amount, e.g. 1-3%. In practice, it could perform better since doing fewer, higher-rank operations generally reduces overheads and improves memory locality.

For reference, the following table shows the number of arithmetic operations for classical multiplication (C), Waksman multiplication (W), current Strassen S[m] with best casecase size m in brackets, and the alternative Strassen S2[m]. The final ratio is S2/S:

n    2  C:      12   W:      40   S[ 2]:      12   S2[ 2]:      12    1.0000
n    3  C:      45   W:      99   S[ 3]:      45   S2[ 3]:      45    1.0000
n    4  C:     112   W:     226   S[ 4]:     112   S2[ 4]:     112    1.0000
n    5  C:     225   W:     385   S[ 5]:     225   S2[ 5]:     225    1.0000
n    6  C:     396   W:     652   S[ 6]:     396   S2[ 6]:     396    1.0000
n    7  C:     637   W:     959   S[ 7]:     637   S2[ 7]:     637    1.0000
n    8  C:     960   W:    1414   S[ 8]:     960   S2[ 8]:     960    1.0000
n    9  C:    1377   W:    1917   S[ 9]:    1377   S2[ 9]:    1377    1.0000
n   10  C:    1900   W:    2608   S[10]:    1900   S2[10]:    1900    1.0000
n   11  C:    2541   W:    3355   S[11]:    2541   S2[11]:    2541    1.0000
n   12  C:    3312   W:    4330   S[ 6]:    3312   S2[ 6]:    3312    1.0000
n   13  C:    4225   W:    5369   S[ 6]:    4225   S2[ 6]:    4225    1.0000
n   14  C:    5292   W:    6676   S[ 7]:    5194   S2[ 7]:    5194    1.0000
n   15  C:    6525   W:    8055   S[ 7]:    6427   S2[ 7]:    6427    1.0000
n   16  C:    7936   W:    9742   S[ 8]:    7680   S2[ 8]:    7680    1.0000
n   17  C:    9537   W:   11509   S[ 8]:    9281   S2[ 8]:    9281    1.0000
n   18  C:   11340   W:   13624   S[ 9]:   10854   S2[ 9]:   10854    1.0000
n   19  C:   13357   W:   15827   S[ 9]:   12871   S2[ 9]:   12871    1.0000
n   20  C:   15600   W:   18418   S[10]:   14800   S2[10]:   14800    1.0000
n   21  C:   18081   W:   21105   S[10]:   17281   S2[10]:   17281    1.0000
n   22  C:   20812   W:   24220   S[11]:   19602   S2[11]:   19602    1.0000
n   23  C:   23805   W:   27439   S[11]:   22595   S2[11]:   22595    1.0000
n   24  C:   27072   W:   31126   S[ 6]:   25344   S2[ 6]:   25344    1.0000
n   25  C:   30625   W:   34925   S[ 6]:   28897   S2[ 6]:   28897    1.0000
n   26  C:   34476   W:   39232   S[ 6]:   32110   S2[ 7]:   32110    1.0000
n   27  C:   38637   W:   43659   S[ 6]:   36271   S2[ 7]:   36271    1.0000
n   28  C:   43120   W:   48634   S[ 7]:   39298   S2[ 7]:   39298    1.0000
n   29  C:   47937   W:   53737   S[ 7]:   44115   S2[ 7]:   44115    1.0000
n   30  C:   53100   W:   59428   S[ 7]:   48364   S2[ 8]:   48364    1.0000
n   31  C:   58621   W:   65255   S[ 7]:   53885   S2[ 8]:   53885    1.0000
n   32  C:   64512   W:   71710   S[ 8]:   57600   S2[ 8]:   57600    1.0000
n   33  C:   70785   W:   78309   S[ 8]:   63873   S2[ 8]:   63873    1.0000
n   34  C:   77452   W:   85576   S[ 8]:   69302   S2[ 9]:   69302    1.0000
n   35  C:   84525   W:   92995   S[ 8]:   76375   S2[ 9]:   76375    1.0000
n   36  C:   92016   W:  101122   S[ 9]:   80838   S2[ 9]:   80838    1.0000
n   37  C:   99937   W:  109409   S[ 9]:   88759   S2[ 9]:   88759    1.0000
n   38  C:  108300   W:  118444   S[ 9]:   95512   S2[10]:   95512    1.0000
n   39  C:  117117   W:  127647   S[ 9]:  104329   S2[10]:  104329    1.0000
n   40  C:  126400   W:  137638   S[10]:  109600   S2[10]:  109600    1.0000
n   41  C:  136161   W:  147805   S[10]:  119361   S2[10]:  119361    1.0000
n   42  C:  146412   W:  158800   S[10]:  127582   S2[11]:  127582    1.0000
n   43  C:  157165   W:  169979   S[10]:  138335   S2[11]:  138335    1.0000
n   44  C:  168432   W:  182026   S[11]:  144474   S2[11]:  144474    1.0000
n   45  C:  180225   W:  194265   S[11]:  156267   S2[11]:  156267    1.0000
n   46  C:  192556   W:  207412   S[11]:  166100   S2[12]:  166100    1.0000
n   47  C:  205437   W:  220759   S[11]:  178981   S2[12]:  178981    1.0000
n   48  C:  218880   W:  235054   S[ 6]:  186048   S2[ 6]:  186048    1.0000
n   49  C:  232897   W:  249557   S[ 6]:  200065   S2[ 6]:  200065    1.0000
n   50  C:  247500   W:  265048   S[ 6]:  211654   S2[13]:  211654    1.0000
n   51  C:  262701   W:  280755   S[ 6]:  226855   S2[13]:  226855    1.0000
n   52  C:  278512   W:  297490   S[ 6]:  234910   S2[ 7]:  234910    1.0000
n   53  C:  294945   W:  314449   S[ 6]:  251343   S2[ 7]:  251343    1.0000
n   54  C:  312012   W:  332476   S[ 6]:  264832   S2[14]:  264832    1.0000
n   55  C:  329725   W:  350735   S[ 6]:  282545   S2[14]:  282545    1.0000
n   56  C:  348096   W:  370102   S[ 7]:  286846   S2[ 7]:  286846    1.0000
n   57  C:  367137   W:  389709   S[ 7]:  305887   S2[ 7]:  305887    1.0000
n   58  C:  386860   W:  410464   S[ 7]:  321420   S2[ 7]:  325610    1.0130
n   59  C:  407277   W:  431467   S[ 7]:  341837   S2[ 7]:  346027    1.0123
n   60  C:  428400   W:  453658   S[ 7]:  352048   S2[ 8]:  352048    1.0000
n   61  C:  450241   W:  476105   S[ 7]:  373889   S2[ 8]:  373889    1.0000
n   62  C:  472812   W:  499780   S[ 7]:  391610   S2[16]:  396412    1.0123
n   63  C:  496125   W:  523719   S[ 7]:  414923   S2[16]:  419725    1.0116
n   64  C:  520192   W:  548926   S[ 8]:  418560   S2[ 8]:  418560    1.0000
n   65  C:  545025   W:  574405   S[ 8]:  443393   S2[ 8]:  443393    1.0000
n   66  C:  570636   W:  601192   S[ 8]:  463446   S2[ 8]:  469004    1.0120
n   67  C:  597037   W:  628259   S[ 8]:  489847   S2[ 8]:  495405    1.0113
n   68  C:  624240   W:  656674   S[ 8]:  502454   S2[ 9]:  502454    1.0000
n   69  C:  652257   W:  685377   S[ 8]:  530471   S2[ 9]:  530471    1.0000
n   70  C:  681100   W:  715468   S[ 8]:  553000   S2[ 9]:  559314    1.0114
n   71  C:  710781   W:  745855   S[ 8]:  582681   S2[ 9]:  588995    1.0108
n   72  C:  741312   W:  777670   S[ 9]:  585306   S2[ 9]:  585306    1.0000
n   73  C:  772705   W:  809789   S[ 9]:  616699   S2[ 9]:  616699    1.0000
n   74  C:  804972   W:  843376   S[ 9]:  641848   S2[ 9]:  648966    1.0111
n   75  C:  838125   W:  877275   S[ 9]:  675001   S2[ 9]:  682119    1.0105
n   76  C:  872176   W:  912682   S[ 9]:  690244   S2[10]:  690244    1.0000
n   77  C:  907137   W:  948409   S[ 9]:  725205   S2[10]:  725205    1.0000
n   78  C:  943020   W:  985684   S[ 9]:  753118   S2[10]:  761088    1.0106
n   79  C:  979837   W: 1023287   S[ 9]:  789935   S2[10]:  797905    1.0101
n   80  C: 1017600   W: 1062478   S[10]:  791200   S2[10]:  791200    1.0000
n   81  C: 1056321   W: 1102005   S[10]:  829921   S2[10]:  829921    1.0000
n   82  C: 1096012   W: 1143160   S[10]:  860742   S2[10]:  869612    1.0103
n   83  C: 1136685   W: 1184659   S[10]:  901415   S2[10]:  910285    1.0098
n   84  C: 1178352   W: 1227826   S[10]:  919534   S2[11]:  919534    1.0000
n   85  C: 1221025   W: 1271345   S[10]:  962207   S2[11]:  962207    1.0000
n   86  C: 1264716   W: 1316572   S[10]:  996080   S2[11]: 1005898    1.0099
n   87  C: 1309437   W: 1362159   S[10]: 1040801   S2[11]: 1050619    1.0094
n   88  C: 1355200   W: 1409494   S[11]: 1040358   S2[11]: 1040358    1.0000
n   89  C: 1402017   W: 1457197   S[11]: 1087175   S2[11]: 1087175    1.0000
n   90  C: 1449900   W: 1506688   S[11]: 1124244   S2[11]: 1135058    1.0096
n   91  C: 1498861   W: 1556555   S[11]: 1173205   S2[11]: 1184019    1.0092
n   92  C: 1548912   W: 1608250   S[11]: 1194440   S2[12]: 1194440    1.0000
n   93  C: 1600065   W: 1660329   S[11]: 1245593   S2[12]: 1245593    1.0000
n   94  C: 1652332   W: 1714276   S[11]: 1286002   S2[12]: 1297860    1.0092
n   95  C: 1705725   W: 1768615   S[11]: 1339395   S2[12]: 1351253    1.0089
n   96  C: 1760256   W: 1824862   S[ 6]: 1336896   S2[ 6]: 1336896    1.0000
n   97  C: 1815937   W: 1881509   S[ 6]: 1392577   S2[ 6]: 1392577    1.0000
n   98  C: 1872780   W: 1940104   S[ 6]: 1436470   S2[ 6]: 1449420    1.0090
n   99  C: 1930797   W: 1999107   S[ 6]: 1494487   S2[ 6]: 1507437    1.0087
n  100  C: 1990000   W: 2060098   S[ 6]: 1519078   S2[13]: 1519078    1.0000
n  101  C: 2050401   W: 2121505   S[ 6]: 1579479   S2[13]: 1579479    1.0000
n  102  C: 2112012   W: 2184940   S[ 6]: 1627000   S2[13]: 1641090    1.0087
n  103  C: 2174845   W: 2248799   S[ 6]: 1689833   S2[13]: 1703923    1.0083
n  104  C: 2238912   W: 2314726   S[ 6]: 1684930   S2[ 7]: 1684930    1.0000
n  105  C: 2304225   W: 2381085   S[ 6]: 1750243   S2[ 7]: 1750243    1.0000
n  106  C: 2370796   W: 2449552   S[ 6]: 1801536   S2[ 7]: 1816814    1.0085
n  107  C: 2438637   W: 2518459   S[ 6]: 1869377   S2[ 7]: 1884655    1.0082
n  108  C: 2507760   W: 2589514   S[ 6]: 1897564   S2[14]: 1897564    1.0000
n  109  C: 2578177   W: 2661017   S[ 6]: 1967981   S2[14]: 1967981    1.0000
n  110  C: 2649900   W: 2734708   S[ 6]: 2023190   S2[14]: 2039704    1.0082
n  111  C: 2722941   W: 2808855   S[ 6]: 2096231   S2[14]: 2112745    1.0079
n  112  C: 2797312   W: 2885230   S[ 7]: 2054962   S2[ 7]: 2054962    1.0000
n  113  C: 2873025   W: 2962069   S[ 7]: 2130675   S2[ 7]: 2130675    1.0000
n  114  C: 2950092   W: 3041176   S[ 7]: 2189944   S2[ 7]: 2207742    1.0081
n  115  C: 3028525   W: 3120755   S[ 7]: 2268377   S2[ 7]: 2286175    1.0078
n  116  C: 3108336   W: 3202642   S[ 7]: 2300400   S2[15]: 2334014    1.0146
n  117  C: 3189537   W: 3285009   S[ 7]: 2381601   S2[15]: 2415215    1.0141
n  118  C: 3272140   W: 3369724   S[ 7]: 2445074   S2[15]: 2497818    1.0216
n  119  C: 3356157   W: 3454927   S[ 7]: 2529091   S2[15]: 2581835    1.0209
n  120  C: 3441600   W: 3542518   S[ 7]: 2518336   S2[ 8]: 2518336    1.0000
n  121  C: 3528481   W: 3630605   S[ 7]: 2605217   S2[ 8]: 2605217    1.0000
n  122  C: 3616812   W: 3721120   S[ 7]: 2673038   S2[ 8]: 2693548    1.0077
n  123  C: 3706605   W: 3812139   S[ 7]: 2762831   S2[ 8]: 2783341    1.0074
n  124  C: 3797872   W: 3905626   S[ 7]: 2798930   S2[16]: 2832544    1.0120
n  125  C: 3890625   W: 3999625   S[ 7]: 2891683   S2[16]: 2925297    1.0116
n  126  C: 3984876   W: 4096132   S[ 7]: 2963996   S2[16]: 3019548    1.0187
n  127  C: 4080637   W: 4193159   S[ 7]: 3059757   S2[16]: 3115309    1.0182
n  128  C: 4177920   W: 4292734   S[ 8]: 2991360   S2[ 8]: 2991360    1.0000

Note that there are also $n$ for which zero-padding should be more efficient than peeling, for example when $n$ is one less than a power of two for $n \ge 63$.

If we only count multiplications, and use Waksman instead of classical as the basecase for Strassen, then the alternative peeling strategy seems to be equal or better. Here are the brute forced multiplication counts:

n    2  C:       8   W:       7   S[ 2]:       7   S2[ 2]:       7    1.0000
n    3  C:      27   W:      23   S[ 3]:      23   S2[ 3]:      23    1.0000
n    4  C:      64   W:      46   S[ 4]:      46   S2[ 4]:      46    1.0000
n    5  C:     125   W:      93   S[ 5]:      93   S2[ 5]:      93    1.0000
n    6  C:     216   W:     141   S[ 6]:     141   S2[ 6]:     141    1.0000
n    7  C:     343   W:     235   S[ 7]:     235   S2[ 7]:     235    1.0000
n    8  C:     512   W:     316   S[ 8]:     316   S2[ 8]:     316    1.0000
n    9  C:     729   W:     473   S[ 9]:     473   S2[ 9]:     473    1.0000
n   10  C:    1000   W:     595   S[10]:     595   S2[10]:     595    1.0000
n   11  C:    1331   W:     831   S[11]:     831   S2[11]:     831    1.0000
n   12  C:    1728   W:    1002   S[ 6]:     987   S2[ 6]:     987    1.0000
n   13  C:    2197   W:    1333   S[13]:    1333   S2[13]:    1333    1.0000
n   14  C:    2744   W:    1561   S[14]:    1561   S2[14]:    1561    1.0000
n   15  C:    3375   W:    2003   S[15]:    2003   S2[15]:    2003    1.0000
n   16  C:    4096   W:    2296   S[ 8]:    2212   S2[ 8]:    2212    1.0000
n   17  C:    4913   W:    2865   S[17]:    2865   S2[17]:    2865    1.0000
n   18  C:    5832   W:    3231   S[18]:    3231   S2[18]:    3231    1.0000
n   19  C:    6859   W:    3943   S[19]:    3943   S2[19]:    3943    1.0000
n   20  C:    8000   W:    4390   S[10]:    4165   S2[10]:    4165    1.0000
n   21  C:    9261   W:    5261   S[21]:    5261   S2[21]:    5261    1.0000
n   22  C:   10648   W:    5797   S[22]:    5797   S2[22]:    5797    1.0000
n   23  C:   12167   W:    6843   S[23]:    6843   S2[23]:    6843    1.0000
n   24  C:   13824   W:    7476   S[ 6]:    6909   S2[ 6]:    6909    1.0000
n   25  C:   15625   W:    8713   S[ 6]:    8710   S2[ 6]:    8710    1.0000
n   26  C:   17576   W:    9451   S[13]:    9331   S2[13]:    9331    1.0000
n   27  C:   19683   W:   10895   S[27]:   10895   S2[27]:   10895    1.0000
n   28  C:   21952   W:   11746   S[14]:   10927   S2[14]:   10927    1.0000
n   29  C:   24389   W:   13413   S[14]:   13364   S2[14]:   13364    1.0000
n   30  C:   27000   W:   14385   S[15]:   14021   S2[15]:   14021    1.0000
n   31  C:   29791   W:   16291   S[31]:   16291   S2[31]:   16291    1.0000
n   32  C:   32768   W:   17392   S[ 8]:   15484   S2[ 8]:   15484    1.0000
n   33  C:   35937   W:   19553   S[ 8]:   18653   S2[ 8]:   18653    1.0000
n   34  C:   39304   W:   20791   S[17]:   20055   S2[ 8]:   19988    0.9967
n   35  C:   42875   W:   23223   S[35]:   23223   S2[ 8]:   22454    0.9669
n   36  C:   46656   W:   24606   S[18]:   22617   S2[18]:   22617    1.0000
n   37  C:   50653   W:   27325   S[18]:   26614   S2[18]:   26614    1.0000
n   38  C:   54872   W:   28861   S[19]:   27601   S2[19]:   27601    1.0000
n   39  C:   59319   W:   31883   S[39]:   31883   S2[ 9]:   31879    0.9999
n   40  C:   64000   W:   33580   S[10]:   29155   S2[10]:   29155    1.0000
n   41  C:   68921   W:   36921   S[10]:   34076   S2[10]:   34076    1.0000
n   42  C:   74088   W:   38787   S[21]:   36827   S2[10]:   36063    0.9793
n   43  C:   79507   W:   42463   S[21]:   42246   S2[10]:   39781    0.9417
n   44  C:   85184   W:   44506   S[22]:   40579   S2[22]:   40579    1.0000
n   45  C:   91125   W:   48533   S[22]:   46520   S2[22]:   46520    1.0000
n   46  C:   97336   W:   50761   S[23]:   47901   S2[23]:   47901    1.0000
n   47  C:  103823   W:   55155   S[23]:   54388   S2[11]:   53461    0.9830
n   48  C:  110592   W:   57576   S[ 6]:   48363   S2[ 6]:   48363    1.0000
n   49  C:  117649   W:   62353   S[ 6]:   55420   S2[ 6]:   55420    1.0000
n   50  C:  125000   W:   64975   S[ 6]:   60970   S2[ 6]:   58187    0.9544
n   51  C:  132651   W:   70151   S[ 6]:   68621   S2[ 6]:   63413    0.9241
n   52  C:  140608   W:   72982   S[13]:   65317   S2[13]:   65317    1.0000
n   53  C:  148877   W:   78573   S[13]:   73586   S2[ 6]:   72038    0.9790
n   54  C:  157464   W:   81621   S[27]:   76265   S2[ 6]:   75243    0.9866
n   55  C:  166375   W:   87643   S[27]:   85176   S2[13]:   82867    0.9729
n   56  C:  175616   W:   90916   S[14]:   76489   S2[14]:   76489    1.0000
n   57  C:  185193   W:   97385   S[14]:   86066   S2[14]:   86066    1.0000
n   58  C:  195112   W:  100891   S[14]:   93548   S2[14]:   89741    0.9593
n   59  C:  205379   W:  107823   S[14]:  103815   S2[14]:   96731    0.9318
n   60  C:  216000   W:  111570   S[15]:   98147   S2[15]:   98147    1.0000
n   61  C:  226981   W:  118981   S[15]:  109128   S2[15]:  109128    1.0000
n   62  C:  238328   W:  122977   S[31]:  114037   S2[15]:  113305    0.9936
n   63  C:  250047   W:  130883   S[31]:  125756   S2[15]:  121273    0.9644
n   64  C:  262144   W:  135136   S[ 8]:  108388   S2[ 8]:  108388    1.0000
n   65  C:  274625   W:  143553   S[ 8]:  120869   S2[ 8]:  120869    1.0000
n   66  C:  287496   W:  148071   S[ 8]:  130571   S2[ 8]:  125580    0.9618
n   67  C:  300763   W:  157015   S[ 8]:  143838   S2[ 8]:  134590    0.9357
n   68  C:  314432   W:  161806   S[17]:  140385   S2[ 8]:  139580    0.9943
n   69  C:  328509   W:  171293   S[17]:  154462   S2[ 8]:  149135    0.9655
n   70  C:  343000   W:  176365   S[35]:  162561   S2[ 8]:  154412    0.9499
n   71  C:  357911   W:  186411   S[35]:  177472   S2[ 8]:  164528    0.9271
n   72  C:  373248   W:  191772   S[18]:  158319   S2[18]:  158319    1.0000
n   73  C:  389017   W:  202393   S[18]:  174088   S2[18]:  174088    1.0000
n   74  C:  405224   W:  208051   S[18]:  186298   S2[18]:  179963    0.9660
n   75  C:  421875   W:  219263   S[18]:  202949   S2[18]:  191249    0.9424
n   76  C:  438976   W:  225226   S[19]:  193207   S2[19]:  193207    1.0000
n   77  C:  456533   W:  237045   S[19]:  210764   S2[19]:  210764    1.0000
n   78  C:  474552   W:  243321   S[39]:  223181   S2[19]:  217269    0.9735
n   79  C:  493039   W:  255763   S[39]:  241668   S2[19]:  229789    0.9508
n   80  C:  512000   W:  262360   S[10]:  204085   S2[10]:  204085    1.0000
n   81  C:  531441   W:  275441   S[10]:  223526   S2[10]:  223526    1.0000
n   82  C:  551368   W:  282367   S[10]:  238532   S2[10]:  230693    0.9671
n   83  C:  571787   W:  296103   S[10]:  258951   S2[10]:  244511    0.9442
n   84  C:  592704   W:  303366   S[21]:  257789   S2[10]:  252021    0.9776
n   85  C:  614125   W:  317773   S[21]:  279210   S2[10]:  266512    0.9545
n   86  C:  636056   W:  325381   S[21]:  295722   S2[10]:  274373    0.9278
n   87  C:  658503   W:  340475   S[21]:  318169   S2[10]:  289553    0.9101
n   88  C:  681472   W:  348436   S[22]:  284053   S2[22]:  284053    1.0000
n   89  C:  704969   W:  364233   S[22]:  307550   S2[22]:  307550    1.0000
n   90  C:  729000   W:  372555   S[22]:  325640   S2[22]:  316137    0.9708
n   91  C:  753571   W:  389071   S[22]:  350211   S2[22]:  332743    0.9501
n   92  C:  778688   W:  397762   S[23]:  335307   S2[23]:  335307    1.0000
n   93  C:  804357   W:  415013   S[23]:  360976   S2[11]:  360028    0.9974
n   94  C:  830584   W:  424081   S[23]:  380716   S2[11]:  369373    0.9702
n   95  C:  857375   W:  442083   S[23]:  407507   S2[11]:  387469    0.9508
n   96  C:  884736   W:  451536   S[ 6]:  338541   S2[ 6]:  338541    1.0000
n   97  C:  912673   W:  470305   S[ 6]:  366478   S2[ 6]:  366478    1.0000
n   98  C:  941192   W:  480151   S[ 6]:  387940   S2[ 6]:  376613    0.9708
n   99  C:  970299   W:  499703   S[ 6]:  417047   S2[ 6]:  396263    0.9502
n  100  C: 1000000   W:  509950   S[ 6]:  426790   S2[ 6]:  406805    0.9532
n  101  C: 1030301   W:  530301   S[ 6]:  457091   S2[ 6]:  427256    0.9347
n  102  C: 1061208   W:  540957   S[ 6]:  480347   S2[ 6]:  438213    0.9123
n  103  C: 1092727   W:  562123   S[ 6]:  511866   S2[ 7]:  459481    0.8977
n  104  C: 1124864   W:  573196   S[13]:  457219   S2[13]:  457219    1.0000
n  105  C: 1157625   W:  595193   S[13]:  489980   S2[13]:  489980    1.0000
n  106  C: 1191016   W:  606691   S[13]:  515102   S2[13]:  501791    0.9742
n  107  C: 1225043   W:  629535   S[13]:  549129   S2[13]:  524741    0.9556
n  108  C: 1259712   W:  641466   S[27]:  533855   S2[ 6]:  526701    0.9866
n  109  C: 1295029   W:  665173   S[27]:  569172   S2[13]:  560806    0.9853
n  110  C: 1331000   W:  677545   S[27]:  596232   S2[13]:  573503    0.9619
n  111  C: 1367631   W:  702131   S[27]:  632863   S2[13]:  598199    0.9452
n  112  C: 1404928   W:  714952   S[14]:  535423   S2[14]:  535423    1.0000
n  113  C: 1442897   W:  740433   S[14]:  573392   S2[14]:  573392    1.0000
n  114  C: 1481544   W:  753711   S[14]:  602462   S2[14]:  587007    0.9743
n  115  C: 1520875   W:  780103   S[14]:  641793   S2[14]:  613513    0.9559
n  116  C: 1560896   W:  793846   S[14]:  654836   S2[14]:  627599    0.9584
n  117  C: 1601613   W:  821165   S[14]:  695553   S2[14]:  655034    0.9417
n  118  C: 1643032   W:  835381   S[14]:  726705   S2[14]:  669599    0.9214
n  119  C: 1685159   W:  863643   S[14]:  768832   S2[14]:  697979    0.9078
n  120  C: 1728000   W:  878340   S[15]:  687029   S2[15]:  687029    1.0000
n  121  C: 1771561   W:  907561   S[15]:  730590   S2[15]:  730590    1.0000
n  122  C: 1815848   W:  922747   S[15]:  763896   S2[15]:  746137    0.9768
n  123  C: 1860867   W:  952943   S[15]:  808915   S2[15]:  776455    0.9599
n  124  C: 1906624   W:  968626   S[31]:  798259   S2[15]:  792505    0.9928
n  125  C: 1953125   W:  999813   S[31]:  844760   S2[15]:  823816    0.9752
n  126  C: 2000376   W: 1016001   S[31]:  880292   S2[15]:  840377    0.9547
n  127  C: 2048383   W: 1048195   S[31]:  928299   S2[15]:  872697    0.9401
n  128  C: 2097152   W: 1064896   S[ 8]:  758716   S2[ 8]:  758716    1.0000

For example, at $n = 102, 103$ this should give nearly a 10% speedup over a multiplication-constrained ring (zero-padding would be very slightly better yet for $n = 103$, but not for $n = 102$).