Repository navigation
Suggested changes for yafu 3.12 code #82
Description
===
This message is to bsquared with cc to EdH.
Date: 29 Apr 26
Subject: Suggested changes for yafu 3.12 code
As before, gemini is doing a lot of the work that is reported here,
and gemini is also helping with the writing of this message.
After many days of work with gemini, I can now use yafu to factor rsa-100.
Here is what happened:
time yafu
With yafu compiled with clang
Total factoring time = 138.3387 seconds
factors found
P50 = 37975227936943673922808872755445627854565536638199
P50 = 40094690950920881030683735292761468389214899724061
ans = 1
real 2m18.357s
user 38m41.911s
sys 1m0.304s
With yafu compiled with gcc
Total factoring time = 157.7464 seconds
factors found
P50 = 37975227936943673922808872755445627854565536638199
P50 = 40094690950920881030683735292761468389214899724061
ans = 1
real 2m37.760s
user 39m5.464s
sys 1m4.615s
===
I am sitting in the yafu directory. Here is the command
followed by what got written to the screen:
find . -name '*_orig' | grep ".c"
./factor/gmp-ecm/tinyecm.c_orig
./factor/qs/SIQS.c_orig
./factor/factor_common.c_orig
./top/cmdParser/cmdOptions.c_orig
./ysieve/wrapper.c_orig
./ysieve/soe.c_orig
./ytools/util.c_orig
By far the file factor/qs/SIQS.c was the most difficult to get right. Both
ASan and valgrind were used to investigate what was going on. It took a very
long time [= 4 days [maybe more]] to get yafu to work properly. Here are the
relevant diff commands followed by what was written to the screen:
===
diff ./factor/gmp-ecm/tinyecm.c_orig ./factor/gmp-ecm/tinyecm.c
149c149
< __inline void copy128(uint64_t *src, uint64_t *dest)
void copy128(uint64_t *src, uint64_t *dest)
156c156
< __inline void swap128(uint64_t *a, uint64_t *b)
void swap128(uint64_t *a, uint64_t *b)
168c168
< __inline void rot128(uint64_t *a, uint64_t *b, uint64_t *c)
void rot128(uint64_t *a, uint64_t *b, uint64_t *c)
===
diff ./factor/qs/SIQS.c_orig ./factor/qs/SIQS.c | wc -l [= 11853]
===
diff ./factor/factor_common.c_orig ./factor/factor_common.c
234c234,235
< fobj->nfs_obj.timeout = 1<<31; //default, not used
// fobj->nfs_obj.timeout = 1<<31; <--- not quite right fobj->nfs_obj.timeout = 1u << 31; //default, not used
===
diff ./top/cmdParser/cmdOptions.c_orig ./top/cmdParser/cmdOptions.c
1392c1392,1393
< options->nfs_timeout = 1 << 31;
// options->nfs_timeout = 1 << 31; <--- not quite right options->nfs_timeout = 1u << 31;
===
diff ./ysieve/wrapper.c_orig ./ysieve/wrapper.c
13c13,14
< The above copyright notice and this permission notice shall be included in all
The above copyright notice and this permission notice shall be included in
all
44,45c45,46
< // something is wrong. compared to numclasses=48, which seems normal. same
< // number of candidates in both cases... weird. Could be a threading thing;
// something is wrong. compared to numclasses=48, which seems normal. same
// number of candidates in both cases... weird. Could be a threading thing;
81d81
<
319c319
<
341c341
< if (sdata->VFLAG > 1)
if (sdata->VFLAG > 1)
382d381
< retval = (mpz_cmp(a, b) > 0);
383a383
retval = (mpz_cmp(a, b) > 0);
395d394
< //primes in the interval
414c413
< if (sdata->VFLAG > 1)
if (sdata->VFLAG > 1)
494a494
mpz_clear(offset);
539d538
< // primes in the interval
638c637
< // threading structures
// threading structures
643a643
649a650
682,683c683,684
< mpz_t tmpz;
< mpz_init(tmpz);
mpz_t tmpz_local; mpz_init(tmpz_local);
689c690
< mpz_add_ui(tmpz, offset, values[range - 1]);
mpz_add_ui(tmpz_local, offset, values[range - 1]);
693c694
< if ((mpz_sizeinbase(tmpz, 2) < 104) && (sdata->analysis == 1))
if ((mpz_sizeinbase(tmpz_local, 2) < 104) && (sdata->analysis == 1))
707c708
< int j;
int k;
709c710
< for (j = 0; j < 8; j++)
for (k = 0; k < 8; k++)
711c712
< mpz_add_ui(tmpz, offset, values[i + j]);
mpz_add_ui(tmpz_local, offset, values[i + k]);
713,715c714,716
< n8[j] = mpz_get_ui(tmpz) & 0xfffffffffffffull;
< mpz_tdiv_q_2exp(tmpz, tmpz, 52);
< n8[j + 8] = mpz_get_ui(tmpz) & 0xfffffffffffffull;
n8[k] = mpz_get_ui(tmpz_local) & 0xfffffffffffffull; mpz_tdiv_q_2exp(tmpz_local, tmpz_local, 52); n8[k + 8] = mpz_get_ui(tmpz_local) & 0xfffffffffffffull;
742c743
< if (mpz_sizeinbase(tmpz, 2) < 128)
if (mpz_sizeinbase(tmpz_local, 2) < 128)
744,745c745,746
< mpz_add_ui(tmpz, offset, values[i]);
< if ((mpz_cmp(tmpz, lowlimit) >= 0) && (mpz_cmp(highlimit, tmpz) >= 0))
mpz_add_ui(tmpz_local, offset, values[i]); if ((mpz_cmp(tmpz_local, lowlimit) >= 0) && (mpz_cmp(highlimit, tmpz_local) >= 0))
748c749
< //if (mpz_extrastrongbpsw_prp(t->tmpz))
750,752c751,753
< n64[0] = mpz_get_ui(tmpz);
< mpz_tdiv_q_2exp(tmpz, tmpz, 64);
< n64[1] = mpz_get_ui(tmpz);
n64[0] = mpz_get_ui(tmpz_local); mpz_tdiv_q_2exp(tmpz_local, tmpz_local, 64); n64[1] = mpz_get_ui(tmpz_local);
758,759c759,760
< mpz_add_ui(tmpz, tmpz, 2);
< if (mpz_probab_prime_p(tmpz, num_witnesses))
mpz_add_ui(tmpz_local, tmpz_local, 2); if (mpz_probab_prime_p(tmpz_local, num_witnesses))
773,774c774,775
< mpz_add_ui(tmpz, offset, values[i]);
< if ((mpz_cmp(tmpz, lowlimit) >= 0) && (mpz_cmp(highlimit, tmpz) >= 0))
mpz_add_ui(tmpz_local, offset, values[i]); if ((mpz_cmp(tmpz_local, lowlimit) >= 0) && (mpz_cmp(highlimit, tmpz_local) >= 0))
777,778c778,779
< //if (mpz_extrastrongbpsw_prp(t->tmpz))
< if (mpz_probab_prime_p(tmpz, num_witnesses))
if (mpz_probab_prime_p(tmpz_local, num_witnesses))
783,784c784,785
< mpz_add_ui(tmpz, tmpz, 2);
< if (mpz_probab_prime_p(tmpz, num_witnesses))
mpz_add_ui(tmpz_local, tmpz_local, 2); if (mpz_probab_prime_p(tmpz_local, num_witnesses))
797c798
< mpz_clear(tmpz);
mpz_clear(tmpz_local);
826c827
< udata.sdata = &thread_data->sdata;
udata.sdata = sdata;
831c832
< thread_data->sdata.sync_count = 0;
sdata->sync_count = 0;
871c872
< uint64_t a;
uint64_t a_local;
873c874
< a = mpz_get_ui(tmpz);
a_local = mpz_get_ui(tmpz);
877c878
< values[i] -= a;
values[i] -= a_local;
902a904
919a922
935,936d937
<
<
===
diff ./ysieve/soe.c_orig ./ysieve/soe.c
126c126,127
< t->ddata.min_sieved_val = (1 << 31) - 1;
// t->ddata.min_sieved_val = (1 << 31) - 1; <--- not quite right t->ddata.min_sieved_val = (1u << 31) - 1;
154c155,156
< t->ddata.min_sieved_val = (1 << 31) - 1;
// t->ddata.min_sieved_val = (1 << 31) - 1; <--- not quite right t->ddata.min_sieved_val = (1u << 31) - 1;
===
diff ./ytools/util.c_orig ./ytools/util.c
1446c1446,1447
< *AVX512VL = (CPUInfo[1] & (1 << 31)) || 0;
// *AVX512VL = (CPUInfo[1] & (1 << 31)) || 0; <--- 1 << 31 is not quite right *AVX512VL = (CPUInfo[1] & (1u << 31)) || 0;
===
Changing '1 << 31' to '1u << 31' fixes an Undefined Behavior (UB) warning
regarding shifting into the sign bit of a signed integer. Making these
standards-compliant changes silenced the warnings in ASan and Valgrind,
which then allowed us to properly trace the harder memory issues.
Here is what I did next:
mkdir for_bsquared
cp -p factor/qs/SIQS.c for_bsquared
cp -p factor/qs/SIQS.c_orig for_bsquared
cd for_bsquared
I created the file SIQS.c_orig_reformatted
and created a read_me file.
cd ..
tar czf for_bsquared.tar.gz ./for_bsquared
ls -s -h for_bsquared.tar.gz
136K for_bsquared.tar.gz
I will try uploading this message, along with the gzipped tar file
for_bsquared.tar.gz to your github site:
Activity