mersenne.ca - Page 54

James Heinrich · 2021-03-31, 22:46

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

LaurV · 2021-04-03, 08:00

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".

James Heinrich · 2021-04-03, 15:29

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.

kruoli · 2021-04-06, 12:37

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;

James Heinrich · 2021-04-06, 14:34

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?

chris2be8 · 2021-04-06, 15:35

A PM to bsquared asking how to do it will probably get you further. He wrote YAFU.

Chris

bsquared · 2021-04-07, 13:17

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.)

James Heinrich · 2021-04-07, 18:35

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!

bsquared · 2021-04-07, 19:30

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

SethTro · 2021-04-07, 21:51

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.

James Heinrich · 2021-04-07, 22:16

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;

2021-04-03, 08:00	#585
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 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-06, 14:34	#588
James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 110101001101₂ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Small inconsistencies between mersenne.org and mersenne.ca factor databases	GP2	mersenne.ca	44	2016-06-19 19:29
mersenne.ca (ex mersenne-aries.sili.net)	LaurV	mersenne.ca	8	2013-11-25 21:01
Gaussian-Mersenne & Eisenstein-Mersenne primes	siegert81	Math	2	2011-09-19 17:36
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods	optim	PrimeNet	13	2004-07-09 13:51

2021-04-06, 15:35	#589
chris2be8 Sep 2009 2×1,039 Posts	A PM to bsquared asking how to do it will probably get you further. He wrote YAFU. Chris