Smallest square that begins with n: Difference between revisions

=={{header|Pascal}}==

==={{header|Free Pascal}}===

Changed search not one by one.<br>Instead using multiples of trunc(sqrt(n) * sqrt(10)^i)+ [0,1].<br>

Extreme reduced runtime.

<pre>

45 -> sqrtN = sqrt(45* 1) = 6,7082039 ; sqrtN_10 = sqrt(45* 10) = 21,21320344

6 -> 36,7 -> 49 ; 21 -> 441,22 ->484

sqrtN *10 ;sqrtN_10 * 10

67 ->4489,68 -> 4624 ; 212 -> 44944, 213 -> 45369 (BINGO)

</pre>

<syntaxhighlight lang="perl">

program LowSquareStartN;

uses

sysutils;

function LowSquareStartN(N: Uint32): Uint32;

const

dez = 10.0;

{Find lowest square that matches N}

var

sqrtN,sqrtN_10 : double;

mySqr : Uint64;

begin

sqrtN := sqrt(n);

//to stay more accurate, instead *sqrt(10);

sqrtN_10 := sqrt(n*dez);

repeat

result := Trunc(sqrtN);

mySqr := result*result;

while mySqr > n do mySqr := mySqr DIV 10;

if mySqr = n then EXIT;

//test only next number

inc(result);

mySqr := (result*result);

while mySqr > n do mySqr := mySqr DIV 10;

if mySqr = n then EXIT;

result := Trunc(sqrtN_10);

mySqr := result*result;

while mySqr > n do mySqr := mySqr DIV 10;

if mySqr = n then EXIT;

inc(result);

mySqr := result*result;

while mySqr > n do mySqr := mySqr DIV 10;

if mySqr = n then EXIT;

sqrtN *= dez;

sqrtN_10 *=dez;

until sqrtN > dez*n;

exit(0);

readln;

end;

procedure SquareStartsN();

{Find smallest square that begins with N}

var

T : Uint64;

i : Uint32;

begin

writeln('Test 1 .. 49');

for I:=1 to 49 do //1*1000*1000 do

begin

T:=LowSquareStartN(I);

write(T*T:7); if i mod 10 = 0 then writeln;

end;

writeln;

writeln;

writeln('Test 999,991 .. 1,000,000');

for I:= 999991 to 1000*1000 do //1000*1000 do

begin

T:=LowSquareStartN(I);

writeln(i:10,':',T:10,'->',t*t:14);

end;

writeln;

end;

BEGIN

SquareStartsN();

END.

</syntaxhighlight>

{{out|@home}}

<pre>

Test 1 .. 49

1 25 36 4 529 64 729 81 9 100

1156 121 1369 144 1521 16 1764 1849 196 2025

2116 225 2304 2401 25 2601 2704 289 2916 3025

3136 324 3364 3481 35344 36 3721 3844 3969 400

41209 4225 4356 441 45369 4624 4761 484 49

Test 999,991 .. 1,000,000

999991: 3162264-> 9999913605696

999992: 999996-> 999992000016

999993: 3162267-> 9999932579289

999994: 999997-> 999994000009

999995: 316227-> 99999515529

999996: 999998-> 999996000004

999997: 3162273-> 9999970526529

999998: 999999-> 999998000001

999999: 3162277-> 9999995824729

1000000: 1000-> 1000000

real 0m0,001s

</pre>