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 :-))
Line 2,210: Line 2,210:
</pre>
</pre>
===={{trans|Julia}}====
===={{trans|Julia}}====
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.<br>
Improved version<br>
// 355ms -> 335 ms
Stop searching as early as possible->minimize count of divisions.335 ms -> 71 ms :-)
<syntaxhighlight lang="pascal">program smsq;
<syntaxhighlight lang="pascal">
program smsq;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
uses
uses
Line 2,221: Line 2,223:
function smsq(n:Uint32):tRes;
function smsq(n:Uint32):tRes;
var
var
k : Uint64;
k,Pow10 : Uint64;
n_running,found : Uint32;
n_running,found : Uint32;


Line 2,229: Line 2,231:
found := 0;
found := 0;
n_running := 1;
n_running := 1;
Pow10 := 1;
while found < n do
while found < n do
begin
begin
k := sqr(n_running);
k := sqr(n_running);
while k > 0 do
//bring k into the right place
k := k div pow10;
begin
if (k <= n) AND (result[k] = 0) then
while k > n do
Begin
Begin
⚫
result[k] := n_running;
⚫
found += 1;
⚫
end;
k := k div 10;
k := k div 10;
pow10 *=10;
end;
end;
repeat
//no need to test any more
//if found ex. 4567 than 456,45 and 4 already marked before
if result[k] <> 0 then
⚫
BREAK;
⚫
result[k] := n_running;
⚫
found += 1;
k := k div 10;
until k = 0;
inc(n_running);
inc(n_running);
end
end
Line 2,275: Line 2,285:
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
check 1..10000000 in 335 ms
check 1..10000000 in 71 ms</pre>
</pre>


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