Smallest square that begins with n: Difference between revisions

Content added Content deleted
(→‎{{trans|Julia}}: speed up julia version. Stop searching as early as possible.Minimize divisions. 335 ms -> 71 ms :-))
(→‎{{trans|Julia}}: last improvement of {{trans|Julia}})
Line 2,211: Line 2,211:
===={{trans|Julia}}====
===={{trans|Julia}}====
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.<br>
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.<br>
Improved version<br>
Improved version ->335 ms<br>
Stop searching as early as possible->minimize count of divisions.335 ms -> 71 ms :-)
Stop searching as early as possible->minimize count of divisions (~ n*(1+3.162=sqrt(10)) ) -> 71 ms<br>
increment as long the testsqr didn't change in last digit. Divisions (~ n*(1+1.8662 )) -> 53 ms :-)
<syntaxhighlight lang="pascal">
<syntaxhighlight lang="pascal">
program smsq;
program smsq;
Line 2,221: Line 2,222:
tRes = array of Uint32;
tRes = array of Uint32;


var
maxTestVal : Uint32;
function smsq(n:Uint32):tRes;
function smsq(n:Uint32):tRes;
// limit n is ~ 1.358E9
var
var
k,Pow10 : Uint64;
square,nxtSqr,Pow10 : Uint64;
n_running,found : Uint32;
n_run,testSqr,found : Uint32;

begin
begin
setlength(result,n+1);
setlength(result,n+1);
fillchar(result[0],length(result)*Sizeof(result[0]),#0);
fillchar(result[0],length(result)*Sizeof(result[0]),#0);
found := 0;
found := 0;
n_running := 1;
square := 0;
Pow10 := 1;
n_run := 0;
Pow10 := 1;
nxtSqr := 1;//sqr(n_run)+1;
while found < n do
while found < n do
begin
begin
repeat
k := sqr(n_running);
n_run +=1;
⚫
//bring k into the right place
k := k div pow10;
square := sqr(n_run);
while k > n do
until square >= nxtSqr;
⚫
//bring square into the right place
⚫
testSqr := square div pow10;
while testSqr > n do
Begin
Begin
⚫
k := k div 10;
pow10 *=10;
pow10 *=10;
testSqr := testSqr div 10;
end;
end;
//next square must increase by one digit
nxtSqr := (testSqr+1)*pow10;
repeat
repeat
//no need to test any more
//no need to test any more
//if found ex. 4567 than 456,45 and 4 already marked before
//if found ex. 4567 than 456,45 and 4 already marsquareed
if result[k] <> 0 then
if result[testSqr] <> 0 then
BREAK;
BREAK;
result[k] := n_running;
result[testSqr] := n_run;
found += 1;
found += 1;
k := k div 10;
testSqr := testSqr div 10;
until k = 0;
until testSqr = 0;
⚫
end;
inc(n_running);
maxTestVal := n_run;
⚫
end
end;
end;


Line 2,269: Line 2,279:
end;
end;
writeln;
writeln;
writeln('Max test value : ',maxTestVal); ;
writeln;

n := 10*1000*1000;
n := 10*1000*1000;
// speed up cpu
// speed up cpu
Line 2,275: Line 2,288:
smsq(n);
smsq(n);
t0 := GetTickCount64-t0;
t0 := GetTickCount64-t0;
writeln('check 1..',n,' in ', T0,' ms');
writeln('check 1..',n,' in ', T0,' ms. Max test value : ',maxTestVal);
END.
END.
</syntaxhighlight>
</syntaxhighlight>
Line 2,285: Line 2,298:
3136 324 3364 3481 35344 36 3721 3844 3969 400
3136 324 3364 3481 35344 36 3721 3844 3969 400
41209 4225 4356 441 45369 4624 4761 484 49
41209 4225 4356 441 45369 4624 4761 484 49
Max test value : 213
⚫
check 1..10000000 in 71 ms</pre>

⚫
check 1..10000000 in 53 ms. Max test value : 31622776
....
check 1..1000000000 in 5174 ms. Max test value : 3162277656
</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Smallest_square_that_begins_with_n"