How to make the code efficient?

2 views (last 30 days)
Ammy
Ammy on 8 Jun 2021
Answered: Steven Lord on 8 Jun 2021
I have made the following code .
x=[0:n-1];
y=[0:n-1];
k = 0;
for i=1:n
for j=1:n
if rem(((y(j))^2)-((x(i))^3)-2*(x(i))-3,n)==0
k = k+1;
xy_mtx(k,:) = [x(i) y(j)];
end
end
end
I want to make it efficient, as efficient as it can be. Is this possible

Answers (3)

David Hill
David Hill on 8 Jun 2021
n=10;
[x,y]=meshgrid(0:n-1);
idx=mod(y.^2-x.^3-2*x-3,n)==0;
xy_mtx=[x(idx),y(idx)];
  4 Comments
David Hill
David Hill on 8 Jun 2021
How large is your n? n cannot be much larger than 2e4 or else the matrices get too large (too much memory).
David Hill
David Hill on 8 Jun 2021
Edited: David Hill on 8 Jun 2021
You could try the help memory suggestions to try to increase memory, or you could add nested for-loop and do the meshgrids in batches of 2e4 (will be slower). Also keep in mind floating point limitations.
n=1e6;
xy_mtx=[];
for k=1:50
for j=1:50
[x,y]=meshgrid(0+(k-1)*2e4:min(2e4-1+(k-1)*2e4,n-1),0+(j-1)*2e4:min(2e4-1+(j-1)*2e4,n-1));
idx=mod(y.^2-x.^3-2*x-3,n)==0;
xy_mtx=[xy_mtx;x(idx),y(idx)];
end
end

Sign in to comment.


Joseph Cheng
Joseph Cheng on 8 Jun 2021
You can do things all at once cine you're not dependent on previous values.
n=4
n = 4
x=[0:n-1];
y=[0:n-1];
k = 0;
%%Orig_code
tic
for i=1:n
for j=1:n
if rem(((y(j))^2)-((x(i))^3)-2*(x(i))-3,n)==0
k = k+1;
xy_mtx(k,:) = [x(i) y(j)];
end
end
end
time1=toc;
tic
%%do everything at once
[X Y] = meshgrid(x,y); %generate combinations of x and y
REMmat = rem((Y.^2)-(X.^3)-2*(X)-3,n); %perform all rem calculations at once
[indexies]=find(REMmat==0); %find which index has a rem of 0
xy_mtxM = [X(indexies) Y(indexies)]; %put only the X and Y comb. where rem above is -
time2=toc;
disp([xy_mtx xy_mtxM])
3 0 3 0 3 2 3 2
disp(['time original:' num2str(time1) 's'])
time original:0.008312s
disp(['time new:' num2str(time2) 's'])
time new:0.016845s
disp(['time delta:' num2str(time1-time2) 's'])
time delta:-0.008533s
  2 Comments
Joseph Cheng
Joseph Cheng on 8 Jun 2021
hm... not sure why the time improvement above is worse but locally it appears much better

Sign in to comment.


Steven Lord
Steven Lord on 8 Jun 2021
Are you trying to find the points on an elliptic curve over F_n?
You could probably try a variant of the naive approach given on this Wikipedia page.

Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!