Divisions-Algorithmus selbst schreiben... / Aber wie?
Der ARM Cortex-M0+ kann kein „DIV“... Oder?
Und GCC will ganz viele 32bit instructions aus seiner libgcc.a verwenden, die der STM32G030 überhaupt gar nicht verstehen kann...
Also habe ich mir selbst was gebastelt... ChatGPT findet mein Verfahren ungewöhnlich und vermutlich zu langsam und schlägt eine einzige Schleife vor, die immer genau 32 mal durchlaufen wird (allerdings sehe ich nicht, warum das dann eine Divison ergeben sollte (hab etwas Angst vor einer Art „Pentium FDIV bug“...)... aber ChatGPT meint, dass das das Standard-Vorgehen sei...)...
Wie findet ihr meinen Divisions-Algorithmus? Also den da (divmod(·,·)):
u32 lsb(const u8 l) { return (1U<<l)-1U; }
u64 divmodB(u32 N, u32 D, u32 B) {
for (; N>D && !(D&(lsb(8)<<24)); B<<=8)
{ u32 nD=D<<8; if (N<nD) break; D=nD; }
for (; N>D && !(D&(1U<<31)); B<<=1)
{ u32 nD=D<<1; if (N<nD) break; D=nD; }
u32 R; for (R=0; N!=0 && B!=0; D>>=1, B>>=1)
if (N>=D) { N-=D; R|=B; }
return (((u64)N)<<32) | R;
}
u64 divmod(u32 N, u32 D)
{ return (!D) ? -1ULL : divmodB(N,D,1); }
ChatGPT schlägt den da vor (ist der überhaupt korrekt? ChatGPT verarscht mich total oft und knickt dann auf Nachfrage sofort diametral ein...):
void divmod(u32 N, u32 D, u32& Q, u32& R) { s8 i;
if (D) for (Q=0, R=0, i=31; i>=0; i--) {
R <<= 1;
R |= (N >> i) & 1;
if (R >= D) {
R -= D;
Q |= (1U << i);
}
} else Q = R = -1UL;
}
also das da läuft mit GCC auf nem J5040 (-O3 -march=goldmont) für divmodA(meins) 6,2sec und für divmodB(ChatGPT) 12,7sec... korrekt scheinen beide zu sein (laut Monte-Carlo-Simulation...)...
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
u64 divmodA(u32 N, u32 D, u32 B) {
for (; N>D && !(D&(((1U<<8)-1U)<<24)); B<<=8)
{ u32 nD=D<<8; if (N<nD) break; D=nD; }
for (; N>D && !(D&(1U<<31)); B<<=1)
{ u32 nD=D<<1; if (N<nD) break; D=nD; }
u32 R; for (R=0; N!=0 && B!=0; D>>=1, B>>=1)
if (N>=D) { N-=D; R|=B; }
return (((u64)N)<<32) | R;
}
void divmodB(u32 N, u32 D, u32& Q, u32& R) { s32 i;
if (D) for (Q=0, R=0, i=31; i>=0; i--) {
R <<= 1;
R |= (N >> i) & 1;
if (R >= D) {
R -= D;
Q |= (1U << i);
}
} else Q = R = -1U;
}
u32 rnd(u32& R, u32& r, u32 l) {
u32 N = 0;
while (l > 0) {
if (!r) { r=31; R=random(); }
u32 L=l; if (L>r) L=r; l-=L; r-=L;
N<<=L; N|=(R&((1U<<L)-1)); R>>=L;
}
return N;
}
int main() {
u32 seed; read(0,&seed,sizeof(seed)); srandom(seed);
const u32 C = 32U*32U*100U*1000U;
u32 S = 0;
u32 R=0, r=0;
for (u32 i=C; i>0; i--) {
u8 lN=i%32, lD=1+(i/32)%31;
u32 N = rnd(R,r,lN);
u32 D; if (lD==1) D=1; else while (!(D=rnd(R,r,lD)));
u64 RA = divmodA(N,D,1); S+=RA; S+=(RA>>32);
//u32 Q,R; divmodB(N,D,Q,R); S+=Q; S+=R;
}
return S;
}
1 Antwort
Und GCC will ganz viele 32bit instructions aus seiner libgcc.a verwenden, die der STM32G030 überhaupt gar nicht verstehen kann...
Dann stimmt was an deinen GCC-Einstellungen nicht... Normalerweise sollten auch nur Bibliotheken geladen werden, die kompatibel zu einem Prozessor sind. Es wäre doch sehr sonderbar, wenn in gewöhnlichem C keine Division möglich wäre... Notfalls müsste es doch sogar Bibliotheken für ARM Thumb geben...
Das andere: Wenn Chat-GPT einen Algorithmus vorschlägt, wirst du ihn auch irgendwo finden... 32 Zyklen bei 32 Bit klingt für mich plausibel. Wäre bei Multiplikation auch so...
Deinen Quelltext finde ich nicht gut lesbar.
ist mein Algorithmus denn korrekt? oder ist die Lesbarkeit so schlimm, dass man das gar nich mehr beurteilen mag...? lol
Das ist aber noch sehr verharmlosend ausgedrückt.
Das ist ein Kandidat für den Obfuscated C Code Contest.