Moin 😀
Auch wenn der Code etwas älter ist, freut es mich wenn ich da Denkanstöße geben konnte.
Aber eine Idee hab ich noch:
Falls du die Werte wirklich auf Bytes limitieren kannst, würde ich das einfach im voraus berechnen. Also bei Programmstart eine lookup table errechnen (alle gekürzten x/y Brüche mit x, y kleiner 256) und dann eine binäre Suche über das Verhältnis. Dann bekommst du immer das perfekte Ergebnis 😉
Die Tabelle dürfte max 392kB groß sein und sollte in jeden
RAM passen...
@jfheins:
Danke für den Hinweis.
Ich hab das realisiert, allerdings etwas anders als von dir (vermutlich) gedacht.
Ich hab eine Tabelle:
Delphi-Quellcode:
type
TTLEntry=Record
Numerator:Byte;
Denominator:Byte;
TL:Word;
End;
TTLTable=Array of TTLEntry;
Die Erstellung erfolgt so:
1) Alle unkürzbaren Brüche (GGT(Z,N)=1)) mit Z und N von 1..255, bei denen FLT*Z div N im Bereich 1..32761 ist, mit resultierender TL in die Tabelle stellen.
2) Mehrfachnennungen (gleiche TL) entfernen
3) Für alle TL von 1..32767 prüfen ob die TL in der Tabelle enthalten ist. Wenn nicht, dann vom nächstkleineren und nächstgrößeren Eintrag den besser geeigneten unter neuer TL hinzufügen.
4) Einen Dummy für TL 0 hinzufügen.
5) Tabelle nach TL aufsteigend sortieren.
Jetzt kann für jede TL im Bereich 1..32767 mit TLTable[TL].Numerator bzw. .Denominator der Zähler und Nenner geholt werden.
Die Tabelle hat während der Erstellung 262 und nach Fertigstellung 131 kB.
Die größte Abweichung zwischen TL und der aus FTL, und Zähler/Nenner resultierenden TL ist 2.28 %.
Die Erstellung dauert ca. 10 ms.
Da bei meinem Anwendungsfall während der Zeit, in der die Tabelle benötigt wird, die FTL konstant bleibt, ist die Erstellung "on demand" deshalb unkritisch.
Zu
Zitat:
Die Tabelle dürfte max 392kB groß sein und sollte in jeden
RAM passen
Mein Programm hält während der Laufzeit diverse Tabellen mit insgesamt ca. 200 MB im
RAM. Die paar Bytes dieser Tabelle sind da vernachlässigbar.
Was mich interessieren würde: Wie kamst Du auf max 392kB ?
Delphi-Quellcode:
type
TTLEntry=Record
Numerator:Byte;
Denominator:Byte;
TL:Word;
End;
TTLTable=Array
of TTLEntry;
var
TLTable:TTLTable;
PROCEDURE CreateTLTable(FTL:Word);
FUNCTION LCD(A,B:Byte):Byte;
var C:Byte;
begin
repeat
C:=A
mod B;
A:=B;
B:=C;
until C=0;
Result:=A;
end;
FUNCTION InitTable:Integer;
var N,D:Byte; XTL:Integer;
begin
SetLength(TLTable,256*256);
Result:=0;
for N:=1
to 255
do
for D:=1
to 255
do
if LCD(N,D)=1
then begin
XTL:=FTL*N
div D;
if InRange(XTL,1,$7FFF)
then
with TLTable[Result]
do begin
Numerator:=N;
Denominator:=D;
TL:=XTL;
Inc(Result);
end;
end;
end;
PROCEDURE SortTable(Count:Integer);
var M:Word; H:TTLEntry;
PROCEDURE QSort(First,Last:Integer);
var I,J:Integer;
begin
I:=First;
J:=Last;
M:=TLTable[(First+Last)
shr 1].TL;
repeat
while TLTable[I].TL<M
do Inc(I);
while TLTable[J].TL>M
do Dec(J);
if I<=J
then begin
H:=TLTable[I];
TLTable[I]:=TLTable[J];
TLTable[J]:=H;
Inc(I);
Dec(J);
end;
until I>J;
if J>First
then QSort(First,J);
if I<Last
then QSort(I,Last);
end;
begin
QSort(0,Count-1);
end;
FUNCTION MakeTableUnique(Count:Integer):Integer;
var I:Integer;
begin
SortTable(Count);
Result:=0;
for I:=1
to Count-1
do
if TLTable[I].TL<>TLTable[Result].TL
then begin
Inc(Result);
TLTable[Result]:=TLTable[I];
end;
Inc(Result);
end;
FUNCTION IsBetter(
const A,B:TTLEntry; TL:Word):Boolean;
begin
Result:=Abs(TL-A.TL)<Abs(TL-B.TL);
end;
PROCEDURE CompleteTable(Count:Integer);
var I,J,L:Integer; N:Word;
begin
L:=Count;
I:=0;
for N:=1
to $7FFF
do begin
while (I<L)
and (TLTable[I].TL<N)
do Inc(I);
// I auf ersten Eintrag mit TL>=N
if I>=L
then J:=L-1
// Letzten Eintrag hinzufügen
else if TLTable[I].TL=N
then J:=-1
// Nichts hinzufügen
else if I=0
then J:=I
// Eintrag I hinzufügen
else if IsBetter(TLTable[I],TLTable[I-1],N)
then J:=I
else J:=I-1;
if J>=0
then begin
TLTable[Count]:=TLTable[J];
TLTable[Count].TL:=N;
Inc(Count);
end;
end;
with TLTable[Count]
do begin
Numerator:=0;
Denominator:=1;
TL:=0;
end;
Inc(Count);
SetLength(TLTable,Count);
SortTable(Count);
end;
var Count:Integer;
begin
Count:=InitTable;
Count:=MakeTableUnique(Count);
CompleteTable(Count);
end;