Gapful numbers: Difference between revisions
Fix pascal version to run in delphi
MaiconSoft (talk | contribs) (Fix pascal version to run in delphi) |
|||
Line 1,559:
Only recognizable for huge amounts of tests 100|74623687 ( up to 1 billion )-> takes 1.845s instead of 11.25s
<lang pascal>program gapful;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
Line 1,566 ⟶ 1,568:
uses
sysutils
{$IFDEF FPC}
,strUtils
{$ENDIF};
const
cIdx = 5;
starts
1000 * 1000
counts
//100| 74623687 => 1000*1000*1000
//100| 746236131 => 10*1000*1000*1000
//100|7462360431 =>100*1000*1000*1000
Base
var
ModsHL
Pow10
countLmt
{$IFNDEF FPC}
function Numb2USA(const S: string): string;
var
i, NA: Integer;
begin
i := Length(S);
Result := S;
NA := 0;
while (i > 0) do
begin
if ((Length(Result) - i + 1 - NA) mod 3 = 0) and (i <> 1) then
insert(',', Result, i);
inc(NA);
end;
Dec(i);
end;
end;
{$ENDIF}
procedure OutHeader(i: NativeInt);
begin
writeln('First ', counts[i], ', gapful numbers starting at ', Numb2USA(IntToStr
end;
procedure OutNum(n: Uint64);
begin
write(' ', n);
end;
procedure InitMods(n: Uint64; H_dgt: NativeUint);
//calculate first mod of n, when it reaches n
var
i,
begin
j := H_dgt; //= H_dgt+i
ModsHL[j] := n
inc(n);
inc(j);
Line 1,607 ⟶ 1,634:
end;
procedure InitMods2(n: Uint64; H_dgt, L_Dgt: NativeUint);
//calculate first mod of n, when it reaches n
//beware, that the lower n are reached in the next base round
var
i,
begin
j := H_dgt;
n := n - L_Dgt;
ModsHL[j] := (n + base)
inc(n);
inc(j);
end;
ModsHL[j] := n
inc(n);
inc(j);
Line 1,629 ⟶ 1,656:
end;
procedure Main(TestNum: Uint64; Cnt: NativeUint);
var
LmtNextNewHiDgt: Uint64;
tmp, LowDgt,
begin
countLmt :=
Pow10 := Base * Base;
LmtNextNewHiDgt := Base * Pow10;
while LmtNextNewHiDgt <= TestNum do
Pow10 := LmtNextNewHiDgt;
LmtNextNewHiDgt
end;
LowDgt := TestNum
GapNum
LmtNextNewHiDgt := (GapNum + 1) * Pow10;
GapNum := Base * GapNum;
InitMods2(TestNum, GapNum, LowDgt)
else
InitMODS(TestNum, GapNum);
GapNum
repeat
// if TestNum MOD (GapNum) = 0 then
if ModsHL[GapNum] = 0 then
tmp := countLmt - 1;
OutNum(TestNum);
countLmt := tmp;
// Test and BREAK only if something has changed
BREAK;
end;
Line 1,668 ⟶ 1,695:
//bad branch prediction :-(
//if tmp >= GapNum then tmp -= GapNum;
tmp
ModsHL[GapNum] := tmp;
TestNum
tmp := LowDgt + 1;
inc(GapNum
▲ Begin
begin
tmp := 0;
GapNum
end;
LowDgt := tmp;
//next Hi Digit
if TestNum >= LmtNextNewHiDgt then
LowDgt := 0;
GapNum
LmtNextNewHiDgt
//next power of 10
if GapNum >= Base * Base then
Pow10
LmtNextNewHiDgt := 2 * Pow10;
GapNum := Base;
end;
initMods(TestNum, GapNum);
end;
until false;
Line 1,699 ⟶ 1,727:
var
i
begin
for i := 0 to High(starts) do
OutHeader(i);
Main(starts[i], counts[i]);
writeln(#13#10);
end;
{$IFNDEF LINUX} readln; {$ENDIF}
end.</lang>
{{out}}
| |||