mersenneforum.org > Data mersenne.ca
 Register FAQ Search Today's Posts Mark Forums Read

2021-03-31, 22:46   #584
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

3,361 Posts

I still don't understand how I get from the data I have (non-bold) to the summary line (bold):
Quote:
 fac: t15: 426.42 fac: t20: 246.52 fac: t25: 55.00 fac: t30: 8.75 fac: t35: 1.09 fac: t40: 0.11 fac: sum of completed work is t35.56

Last fiddled with by James Heinrich on 2021-03-31 at 22:46

 2021-04-03, 08:00 #585 LaurV Romulan Interpreter     Jun 2011 Thailand 5×1,889 Posts The one where the score is (or would be) 1.00 (interpolation is good enough). Those with larger scores are done "too much", those with smaller are done "not enough". Last fiddled with by LaurV on 2021-04-03 at 08:06
2021-04-03, 15:29   #586
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

1101001000012 Posts

Quote:
 Originally Posted by LaurV The one where the score is (or would be) 1.00 (interpolation is good enough). Those with larger scores are done "too much", those with smaller are done "not enough".
That seems obvious enough, but doesn't help me in my attempt to calculate the overall value as described above. If someone who understands it can run though some example numbers to point me in the right direction I'd appreciate it.

2021-04-06, 12:37   #587
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

32·5·11 Posts

Quote:
 Originally Posted by James Heinrich I still don't understand how I get from the data I have (non-bold) to the summary line (bold): […]
You cannot, at least not with this six data points. An algorithm would look somthing like this:
Code:
// first, calculate the first tXX level that has a value of less than 1
int t_level;
double value = -1;
for (t_level = 5; t_level < max_t_level; t_level += 5)
{
value = getValueOfTLevel(t_level);
if (value < 1)
{
break;
}
}
// then perform binary search
double lower_limit = t_level - 5, upper_limit = t_level, mid, epsilon = 1e-3;
do
{
mid = (lower_limit + upper_limit) / 2;
value = getValueOfTLevel(mid);
if (value > 1)
{
lower_limit = mid;
}
else
{
upper_limit = mid;
}
}
while (abs(value - 1) > epsilon);
return mid;

Last fiddled with by kruoli on 2021-04-06 at 13:12 Reason: Corrected pseudo code.

 2021-04-06, 14:34 #588 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 3,361 Posts The concept of the binary search algorithm I understand. The sticking point is getValueOfTLevel. Supposing I have data from M2083 (also attached for reference). Do I have sufficient data to somehow calculate an overall T-level? Attached Thumbnails
 2021-04-06, 15:35 #589 chris2be8     Sep 2009 2×1,021 Posts A PM to bsquared asking how to do it will probably get you further. He wrote YAFU. Chris
2021-04-07, 13:17   #590
bsquared

"Ben"
Feb 2007

343810 Posts

Quote:
 Originally Posted by YAFU: factor_common.c double compute_ecm_work_done(factor_work_t *fwork, int disp_levels, FILE *log, int VFLAG, int LOGFLAG) { // there is probably a more elegant way to do this involving dickman's function // or something, but we can get a reasonable estimate using empirical data // for our fixed set of B1/B2 values. ... }
YAFU essentially uses table lookup. The data table is at the top of factor_common.c. It was gathered by A. Schindel running ecm with -v -v -v and recording how many curves gmp-ecm says are needed for each t-level and B1 combination with otherwise default gmp-ecm settings. I just track how many curves were run at each B1 value and sum the ratio of completed curves over rows of that table. The "sum" displayed at the end is computed on line 1653:
Code:
return ecm_levels[i - 1] + 5 * tlevels[i];
Which is the last ecm level completed (specified in the table in increments of 5 digits) plus the current uncompleted ratio (first ratio < 1) times 5 (the table increment). Basically interpolating between table entries for the last incomplete level.

As the source code comment says, I'm sure there is a better/more accurate way to compute this, but my todo list is already too long. (Especially now that yafu uses AVX-ECM which needs an entirely different table.)

Last fiddled with by bsquared on 2021-04-07 at 13:22 Reason: table details/assumptions

2021-04-07, 18:35   #591
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

3,361 Posts

Quote:
 Originally Posted by bsquared Which is the last ecm level completed (specified in the table in increments of 5 digits) plus the current uncompleted ratio (first ratio < 1) times 5 (the table increment). Basically interpolating between table entries for the last incomplete level.
Oh wow, that's so simple. Thank you!

2021-04-07, 19:30   #592
bsquared

"Ben"
Feb 2007

2×32×191 Posts

Quote:
 Originally Posted by James Heinrich Oh wow, that's so simple. Thank you!
You're welcome, but I'll just re-emphasize that the table in yafu's source was collected many years ago, for generic non-Mersenne inputs, and using default parameters. It's likely that a table for today's gmp-ecm, using Mersenne inputs, and other custom parameters (B2=100*B1 maybe?, non-default settings for Brent-Suyama maybe?), would be substantially different.

For example, using default settings including B2, I see that it wants only 17462 curves at B1=110M, versus the 46500 specified in your table for t55 on M2083.

Code:
Input number is 2^2083-1 (628 digits)
Using special division for factor of 2^2083-1
Using B1=110000000, B2=900514153782, polynomial Dickson(30), sigma=0:12421973142589397170
dF=199680, k=2, d=2081310, d2=13, i0=40
Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
34      133     600     3065    17462   108584  733594  5340128 4.2e+07 3.5e+08

2021-04-07, 21:51   #593
SethTro

"Seth"
Apr 2019

27310 Posts

Quote:
 Originally Posted by bsquared YAFU essentially uses table lookup. The data table is at the top of factor_common.c. It was gathered by A. Schindel running ecm with -v -v -v and recording how many curves gmp-ecm says are needed for each t-level and B1 combination with otherwise default gmp-ecm settings. I just track how many curves were run at each B1 value and sum the ratio of completed curves over rows of that table. The "sum" displayed at the end is computed on line 1653: Code: return ecm_levels[i - 1] + 5 * tlevels[i]; Which is the last ecm level completed (specified in the table in increments of 5 digits) plus the current uncompleted ratio (first ratio < 1) times 5 (the table increment). Basically interpolating between table entries for the last incomplete level. As the source code comment says, I'm sure there is a better/more accurate way to compute this, but my todo list is already too long. (Especially now that yafu uses AVX-ECM which needs an entirely different table.)
@James The table lookup is what our code already does. Maybe a good next step would be for you to produce the 100 most common B1/B2 pairs (rounding B2 down to the nearest million for large values) and I can produce the curve counts (using ecm -v -v -v) for each of those B1/B2 pairs. This would help large curves get counted more accurately.

2021-04-07, 22:16   #594
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

3,361 Posts

Data just from 2020 (I could get from other years if that's needed):

Code:
+------------+-----------------+----------------+
| b1         | b2              | sum_num_curves |
+------------+-----------------+----------------+
|     250000 |        25000000 |        3829660 |
|      50000 |         5000000 |        3655642 |
|    1000000 |       100000000 |         504342 |
|    3000000 |       300000000 |         486270 |
|   11000000 |      1100000000 |         209350 |
|    1000000 |         1000000 |         137799 |
|    1000000 |        10000000 |         106007 |
|   11000000 |     36578884662 |          43200 |
|  110000000 |     11000000000 |          31768 |
|   11000000 |     30114149530 |          21351 |
|      50000 |           50000 |          15349 |
|    3000000 |         3000000 |          10600 |
|     500000 |          500000 |          10000 |
|      50000 |        14400000 |           9540 |
|   43000000 |    198654756318 |           5000 |
|  160000000 |   1288647750406 |           3696 |
|  113000000 |     11300000000 |           3300 |
|   44000000 |      4400000000 |           2888 |
|    3000000 |      4592487916 |           2756 |
|      50000 |         6750000 |           2735 |
|  111000000 |     11100000000 |           2720 |
|   48000000 |    297984687018 |           2646 |
|  110000000 |       110000000 |           2630 |
|  107000000 |     10700000000 |           2600 |
|  110000000 |    776278396540 |           2420 |
|   48000000 |    279380917212 |           2097 |
|     445657 |        50000000 |           1984 |
|      50000 |        50000000 |           1979 |
|  800000000 |     80000000000 |           1942 |
|  109000000 |     10900000000 |           1900 |
|  110000000 |   1000000000000 |           1826 |
|      76620 |        24176890 |           1515 |
|      76620 |        10000000 |           1445 |
|        120 |        50000000 |           1150 |
|      60000 |         6000000 |           1103 |
|      50000 |        11760000 |           1080 |
|   23000000 |        23000000 |           1000 |
|   23000000 |     81050459506 |           1000 |
|   44000000 |        44000000 |           1000 |
|    3000000 |      1000000000 |           1000 |
|   41000000 |      4100000000 |            900 |
|   48000000 |    251426235076 |            847 |
|      50000 |         6800000 |            775 |
|      76620 |        23259610 |            645 |
|  260000000 |     26000000000 |            603 |
|     250000 |        30000000 |            600 |
|   42000000 |      4200000000 |            600 |
|   43000000 |      4300000000 |            600 |
|   48000000 |    298483725556 |            584 |
|      50000 |         6350000 |            539 |
|   44000000 |    100000000000 |            500 |
|   11000000 |    100000000000 |            500 |
|   11000000 |        11000000 |            500 |
|   44000000 |    223505479902 |            455 |
|  190000000 |   2383889958466 |            434 |
|      80000 |         8000000 |            432 |
|     250000 |        32616915 |            427 |
|     250000 |        30050537 |            427 |
|  260000000 |  10000000000000 |            422 |
|     250000 |        38357144 |            420 |
|     250000 |        30419426 |            420 |
|      65000 |         5000000 |            420 |
|     250000 |        38141102 |            420 |
|     250000 |        38123960 |            420 |
|     250000 |        38317896 |            420 |
|     250000 |        37170685 |            416 |
|      50000 |         4750000 |            406 |
|      76620 |        26954350 |            406 |
|     250000 |        38104631 |            400 |
|     250000 |        38172094 |            400 |
|     250000 |        38075084 |            400 |
|     250000 |        38750000 |            392 |
|      50000 |         6450000 |            356 |
|     250000 |        38299066 |            350 |
|     250000 |        38060828 |            350 |
|  260000000 |       260000000 |            350 |
|     250000 |        38253153 |            350 |
|      50000 |        13428460 |            350 |
|      50000 |        13775590 |            350 |
|      74000 |         7400000 |            319 |
|  999999999 |     99999999900 |            309 |
|    6000000 |       600000000 |            300 |
|      50000 |         6650000 |            251 |
|      49000 |         4900000 |            250 |
|      47000 |         4700000 |            238 |
|      50000 |         4550000 |            234 |
|     100000 |        14200000 |            224 |
|      50000 |         6700000 |            210 |
|      51000 |         5100000 |            210 |
|      50000 |         5100000 |            200 |
|      65000 |         6500000 |            200 |
|     199900 |        19990000 |            200 |
|       1000 |         1000000 |            200 |
|    2100100 |       200100100 |            200 |
|      70000 |         7300000 |            199 |
|     250000 |        38500000 |            175 |
|   30000000 |      3000000000 |            160 |
|   11000000 |       110000000 |            151 |
|  900000000 |     90000000000 |            150 |
|   25000000 |      2500000000 |            150 |
|    4000000 |       400000000 |            150 |
|  260000000 |   1000000000000 |            150 |
|    2500000 |       250000000 |            150 |
|    3000000 |       100000000 |            150 |
|     250000 |        50000000 |            140 |
|  850000000 |  14142901172416 |            135 |
|  110000000 |    100000000000 |            134 |
|     100000 |        13600000 |            133 |
|      76620 |        15000000 |            129 |
|      51000 |         5000000 |            123 |
|      50000 |          500000 |            110 |
|     250000 |       129632592 |            108 |
|      50000 |         6400000 |            104 |
|     100000 |        10000000 |            103 |
|   11000000 |      2500000000 |            100 |
|  850000000 |       850000000 |            100 |
| 2147483648 |      2147483648 |            100 |
|   10000000 |       250000000 |            100 |
|      45000 |         4500000 |            100 |
|  850000000 |  10000000000000 |            100 |
|      50000 |         5000001 |             96 |
|      50000 |         6500000 |             90 |
|       1000 |           65000 |             90 |
|    3000000 |      3000000000 |             90 |
|      76620 |        30000000 |             83 |
|      50000 |        10000000 |             78 |
|      75000 |         7500000 |             77 |
|     500000 |        50000000 |             65 |
|      50000 |         5400000 |             62 |
| 6000000000 |      6000000000 |             60 |
|  500000000 |   6704868340188 |             60 |
|     250000 |       183032866 |             59 |
|  110000000 |    900514153782 |             58 |
|    1000000 |       974637522 |             58 |
|      70000 |         7100000 |             52 |
|   23359695 |      2335969500 |             50 |
|  850000000 | 100000000000000 |             50 |
|  850000000 |     10000000000 |             50 |
|      10000 |         1000000 |             48 |
|   44000000 |    251421670516 |             43 |
|      50000 |               0 |             42 |
|   10000000 |      1000000000 |             36 |
|      50000 |         4650000 |             36 |
|     200000 |        20000000 |             36 |
|      50000 |         4850000 |             36 |
|     100000 |        13800000 |             35 |
|  260000000 |   3079973376496 |             33 |
|  180000000 |       180000000 |             32 |
| 1000000000 |    100000000000 |             30 |
|      50000 |         5200000 |             30 |
|      50000 |         4900000 |             28 |
|     100000 |        12700000 |             28 |
|    3000000 |       528000000 |             28 |
|  110000000 |      2500000000 |             26 |
|   10000000 |       100000000 |             26 |
|      25000 |         5000000 |             25 |
| 2900000000 | 100000000000000 |             22 |
|     150000 |        20550000 |             21 |
|     100000 |        11893855 |             21 |
|     100000 |        14413889 |             21 |
|     250000 |        36500000 |             21 |
|  850000000 |     85000000000 |             20 |
|     250000 |       145000000 |             20 |
|      50000 |         6300000 |             20 |
|      50000 |         5900000 |             19 |
|      50000 |         4150000 |             18 |
|      75000 |        10500000 |             18 |
|     250000 |       124922710 |             18 |
|   11000000 |       310000000 |             15 |
|      50000 |         6050000 |             15 |
|     100000 |        11125212 |             14 |
|     100000 |        12625951 |             14 |
|     100000 |        12255006 |             14 |
|     100000 |        10500000 |             14 |
|     235000 |        23500000 |             13 |
| 1200000000 |      1200000000 |             13 |
| 1500000000 |      1500000000 |             13 |
|      50000 |         6646918 |             12 |
|      10000 |         5000000 |             12 |
| 1600000000 |      1600000000 |             12 |
|   10100100 |       900100100 |             12 |
|      50000 |         5750000 |             12 |
|  880000000 |      1320000000 |             11 |
| 2900000000 |      2900000000 |             10 |
|  110000000 |    110000000000 |             10 |
|  850000000 |  15716618487586 |             10 |
|  880000000 |       880000000 |              9 |
| 1320000000 |      1320000000 |              9 |
|      50000 |         5270912 |              8 |
|      50000 |    219716459349 |              7 |
|     250000 |        37569102 |              7 |
|     100000 |        12277371 |              7 |
|     100000 |        13725214 |              7 |
|      50000 |         6470424 |              7 |
|      50000 |         5630013 |              7 |
|     100000 |        12600602 |              7 |
|     250000 |        35880562 |              7 |
|      50000 |         6606829 |              7 |
|      50000 |         6180426 |              7 |
|     100000 |        13585673 |              7 |
+------------+-----------------+----------------+
200 rows in set (14.43 sec)
Quote:
 mysql> SELECT b1, b2, SUM(num_curves) AS sum_num_curves FROM (SELECT SUBSTRING_INDEX(SUBSTRING_INDEX(message, " ", 1), " ", -1) AS num_curves, b1, b2 FROM primenet_results_archive_2020 WHERE (result_type = "NF-ECM") AND (message REGEXP "^[0-9]+ curves?,")) AS a GROUP BY b1, b2 ORDE R BY sum_num_curves DESC LIMIT 200;

Last fiddled with by James Heinrich on 2021-04-07 at 22:17

 Similar Threads Thread Thread Starter Forum Replies Last Post GP2 mersenne.ca 44 2016-06-19 19:29 LaurV mersenne.ca 8 2013-11-25 21:01 siegert81 Math 2 2011-09-19 17:36 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 15:57.

Thu May 13 15:57:18 UTC 2021 up 35 days, 10:38, 2 users, load averages: 2.54, 2.43, 2.27