mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-07-12, 17:12   #12
RomanM
 
Jun 2021

41 Posts
Default

The sieve v 1.0
Ugly, non-elegant, Tea Time style.
This sieve is memory hungry and in spite of being exponentially fast on the really large upper bound (if you have plenty of memory)), and can be greatly improved. It's using the most obvious way to sieve, there is at least two more.
Code:
\p300
{p=233108530344407544527637656910680524145619812480305449042948611968495918245135782867888369318577116418213919268572658314913060672626911354027609793166341626693946596196427744273886601876896313468704059066746903123910748277606548649151920812699309766587514735456594993207;
c=ceil(sqrt(p));

v=vector(2000000);
S=vector(2000000);

for(n=1,200000, \\200000-upper bound of sieve, can be large)

u=c+n; 
b=lift(Mod(u^2,p));
a=lift(Mod(b^2,p));
t=ceil((b^2-a)^(1/2));
v[n]=t;);

v=vecsort(v,,8);

j=1;
for(k=1,300, \\dummy loop
vecmax(v,&z);
print(z);\\some digit on the screen
for(n=1,z,
u=v[n];
b=lift(Mod(u^2,p));
a=lift(Mod(b^2,p));
if(b<c,localprec(7);S[j]=b/c/1.;j=j+1;);
if(b>c,
t=ceil((b^2-a)^(1/2));
v[n]=t;
);
);
v=vecsort(v,,8); \\the "sieve" hiding here
);
S=vecsort(S,,8);
print(S);
}
RomanM is offline   Reply With Quote
Old 2021-07-14, 05:39   #13
RomanM
 
Jun 2021

1010012 Posts
Default

Hello. ~10x speedup, just feeding the "sieve" by other set of initial values. And you understand, that output subsqrt residuals means nothing but the way how we get them?
Attached Files
File Type: txt 1.txt (946 Bytes, 45 views)
RomanM is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NFS sqrt by hand henryzz Factoring 18 2010-09-26 00:55
127*Sqrt(62) XYYXF Math 2 2007-12-08 12:31
ggnfs sqrt problem hallstei Factoring 7 2007-05-01 12:51
SQRT Problem R.D. Silverman NFSNET Discussion 11 2006-07-20 17:04
P(n+1)<(sqrt(P(n))+1)^2 Crook Math 3 2005-10-26 21:29

All times are UTC. The time now is 04:42.


Thu Dec 2 04:42:00 UTC 2021 up 131 days, 23:11, 0 users, load averages: 1.19, 1.17, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.