Smallest square that begins with n: Difference between revisions
→{{trans|Julia}}: last improvement of {{trans|Julia}}
(→{{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:
===={{trans|Julia}}====
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.<br>
Improved version ->335 ms<br>
Stop searching as early as possible->minimize count of divisions (~ n*(1+3.
increment as long the testsqr didn't change in last digit. Divisions (~ n*(1+1.8662 )) -> 53 ms :-)
<syntaxhighlight lang="pascal">
program smsq;
Line 2,221 ⟶ 2,222:
tRes = array of Uint32;
var
maxTestVal : Uint32;
function smsq(n:Uint32):tRes;
// limit n is ~ 1.358E9
var
begin
setlength(result,n+1);
fillchar(result[0],length(result)*Sizeof(result[0]),#0);
found := 0;
Pow10 := 1;
nxtSqr := 1;//sqr(n_run)+1;
while found < n do
begin
repeat
n_run +=1;
//bring k into the right place▼
while testSqr > n do
Begin
▲ k := k div 10;
pow10 *=10;
testSqr := testSqr div 10;
end;
//next square must increase by one digit
nxtSqr := (testSqr+1)*pow10;
repeat
//no need to test any more
//if found ex. 4567 than 456,45 and 4 already
if result[
BREAK;
result[
found += 1;
until
end;▼
maxTestVal := n_run;
▲ end
end;
Line 2,269 ⟶ 2,279:
end;
writeln;
writeln('Max test value : ',maxTestVal); ;
writeln;
n := 10*1000*1000;
// speed up cpu
Line 2,275 ⟶ 2,288:
smsq(n);
t0 := GetTickCount64-t0;
writeln('check 1..',n,' in ', T0,' ms. Max test value : ',maxTestVal);
END.
</syntaxhighlight>
Line 2,285 ⟶ 2,298:
3136 324 3364 3481 35344 36 3721 3844 3969 400
41209 4225 4356 441 45369 4624 4761 484 49
Max test value : 213
check 1..10000000 in 71 ms</pre>▼
....
check 1..1000000000 in 5174 ms. Max test value : 3162277656
</pre>
=={{header|Perl}}==
| |||